• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 9
  • 1
  • 1
  • Tagged with
  • 12
  • 12
  • 9
  • 9
  • 9
  • 3
  • 3
  • 3
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.

Cycles in edge-coloured graphs and subgraphs of random graphs

White, M. D. 2011 (has links)
This thesis will study a variety of problems in graph theory. Initially, the focus will be on finding minimal degree conditions which guarantee the existence of various subgraphs. These subgraphs will all be formed of cycles, and this area of work will fall broadly into two main categories. First to be considered are cycles in edge-coloured graphs and, in particular, two questions of Li, Nikiforov and Schelp. It will be shown that a 2-edge-coloured graph with minimal degree at least 3n/4 either is isomorphic to the complete 4-partite graph with classes of order n/4, or contains monochromatic cycles of all lengths between 4 and n/2 (rounded up). This answers a conjecture of Li, Nikiforov and Schelp. Attention will then turn to the length of the longest monochromatic cycle in a 2-edge-coloured graph with minimal degree at least cn. In particular, a lower bound for this quantity will be proved which is asymptotically best possible. The next chapter of the thesis then shows that a hamiltonian graph with minimal degree at least (5-sqrt7)n/6 contains a 2-factor with two components. The thesis then concludes with a chapter about X_H, which is the number of copies of a graph H in the random graph G(n,p). In particular, it will be shown that, for a connected graph H, the value of X_H modulo k is approximately uniformly distributed, provided that k is not too large a function of n.

Circuit Bases of Strongly Connected Digraphs

Gleiss, Petra M., Leydold, Josef, Stadler, Peter F. 2001 (has links) (PDF)
The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined. (author's abstract) Series: Preprint Series / Department of Applied Statistics and Data Processing

Využití operačního výzkumu při navrhování linek v městské hromadné dopravě Application of Operations Research in Line Planning in Urban Public Transport

Fator, Jiří 2011 (has links)
This diploma thesis analyzes the problem of line planning in urban public transport as an object of Operations Research. It is based on the Theory of Graphs, building specific model network referring to a real existing network. Each line represents the flow through part of this network, respecting additional constraints. The goal is to optimize existing routing by decreasing the number of lines in service and making the routing easier to understand and remember. On the contrary to casual models, this one has been designed to perfectly describe a real existing network, tramway service in Prague, Czech Republic. Furthermore, no set of lines is given in advance. The flow is newly computed by optimizing software to fit the demand and the capacity of each branch. So the output should give the user a concrete route of each line in operation.

Um estudo introdutório da Teoria de Grafos através de matrizes

Gonçalves, Diego Rodrigues [UNESP] 31 March 2014 (has links)
Made available in DSpace on 2014-08-13T14:50:59Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-03-31Bitstream added on 2014-08-13T17:59:48Z : No. of bitstreams: 1 000773520.pdf: 599821 bytes, checksum: 0341b612274b313baef13dc8cdb71c59 (MD5) O objetivo deste trabalho é apresentar alguns resultados elementares de Álgebra Linear e relacioná-los com a Teoria de Grafos, por meio de exemplos, sempre que possível. A ferramenta básica para isso é a teoria de matrizes The aim of this work is to present some elementary results from Linear Algebra and to relate them with Graph Theory, making use of examples if possible

Formulação algébrica para a modelagem de algoritmos de roteamento multi-restritivo hop-by-hop. Algebraic formulation for modeling hop-by-hop multi-constrained routing algorithms.

Walmara de Paula Herman 4 April 2008 (has links)
Este trabalho apresenta uma nova estrutura matemática para a álgebra de caminhos, que permite analisar a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop e, sob o ponto de vista da engenharia de tráfego e da Qualidade de Serviço (QoS) na arquitetura Generalized Multiprotocol Label Switching (GMPLS), garantir de maneira confiável a incorporação de novas métricas de roteamento aos algoritmos de roteamento baseados em múltiplas restrições. Baseando-se nessa nova álgebra de caminhos, são analisadas as propriedades de monotonicidade, isotonicidade e liberdade, conhecidas por garantir a convergência dos algoritmos de roteamento e, ao contrário do indicado na literatura até o momento, verifica-se que a propriedade de monotonicidade não e condição necessária e nem suficiente para garantir a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop. Sendo assim, este trabalho propõe uma nova propriedade, denominada coerência, para a garantia da convergência do roteamento hop-by-hop e um novo algoritmo de roteamento hop-by-hop com convergência garantida. Para avaliar os resultados teóricos obtidos, s~ao analisados dois estudos de casos de aplicação do roteamento multi-restritivos hop-by-hop com o uso de uma ferramenta de simulação desenvolvida em MATLAB e baseada no algoritmo Eliminação de Loop pelo Nó de Destino (ELND) também proposto. Como resultado das simulações desses estudos de casos, verifica-se que as diferentes estratégias de otimização, necessárias as redes (GMPLS), impõem a necessidade de trabalhar com algoritmos de roteamento que permitam a definição de mais de duas métricas de roteamento com diferentes critérios de otimização para cada uma delas, comprovando, portanto, a necessidade do desenvolvimento e da continuação deste trabalho. This work presents a new mathematical structure for paths algebra that allows the convergence analysis of hop-by-hop multi-constrained routing algorithms and, under the traffic engineering and quality of service perspectives in the Generalized Multiprotocol Label Switching (GMPLS) architecture, trustily ensures the aggregation of new routing metrics in a constrained-based routing. Based on this new paths algebra, we analyze the monotonicity, isotonicity and freeness properties, known as ensuring routing algorithms convergence, and despite of what has been indicated in the literature, we verified that the monotonicity property is not sufficient to ensure the hop-by-hop routing convergence. Therefore, this work proposes a new property, called coherence, as a necessary and sufficient condition to ensure it, as well as, a new multi-constrained hop-by-hop routing algorithm with ensured convergence. In order to evaluate the theoretical results obtained, two study cases of the hop-by-hop multi-constrained routing applications are analyzed in the present thesis by using the Eliminação de Loop pelo Nó de Destino (ELND) simulation tool, developed in MATLAB and also presented as a product of this work. As result of these study cases simulations, we verified that different optimization strategies, requested by the (GMPLS) networks, compel the use of routing algorithms that allow the specification of more than two routing metrics with different optimization criteria for each one of them, thus proving the necessity of this work and its continuation.

O Teorema de Euler para poliedros e a topologia dos grafos no ensino básico THE EULER THEORY FOR POLYESTERS AND TOPOLOGY OF GRAPHS IN BASIC EDUCATION

FREITAS, Janderson dos Santos de 8 May 2017 (has links)
Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-08-25T20:24:28Z No. of bitstreams: 1 JandersonFreitas.pdf: 2087995 bytes, checksum: e49b1008df3093f81aeb841870a06df9 (MD5) Made available in DSpace on 2017-08-25T20:24:28Z (GMT). No. of bitstreams: 1 JandersonFreitas.pdf: 2087995 bytes, checksum: e49b1008df3093f81aeb841870a06df9 (MD5) Previous issue date: 2017-05-08 The paper presents problem solving using Graph Theory and Euler’s Theorem. The research performs specific activities in high school involving graphs in various applications of the Euler relation as a problem solving method with Graph Theory. The relationship of Euler is presented in a Geometric view and by the graphs planning. The research proposes a link between the students ’daily problems with the modeling of problem situations by the Graph Theory, specifically the planar graphs solved with the implementation of Euler’ s Theorem focused on the teaching of basic mathematics. Applications of Graph Theory are shown in solving problems with the bridges of the city of Barra do Corda and the students’ school life. O trabalho apresenta a resolução de problemas utilizando a Teoria dos Grafos e o Teorema de Euler. Uma pesquisa que executa atividades específicas no ensino médio envolvendo grafos em várias aplicações da relação de Euler como método de resolução de problemas com Teoria dos Grafos. A relação de Euler é apresentada em uma visão Geométrica e pela planificação dos grafos. Propondo um elo entre os problemas do cotidiano dos alunos com a modelagem de situações problema pela Teoria dos Grafos, especificamente os grafos planares resolvidos com a implementação do Teorema de Euler voltado ao ensino de matemática básica. São mostradas aplicações da Teoria dos Grafos na resolução de problemas com as pontes da cidade de Barra do Corda e da vida escolar dos alunos.

Ensino de sintaxe no 8ºano do ensino Fundamental: uso da teoria dos grafos.

LOPES, Epitácio Silva. 17 November 2016 (has links)
Submitted by Denize Lourenço (biblicfp@cfp.ufcg.edu.br) on 2018-01-02T13:56:35Z No. of bitstreams: 1 EPITÁCIO SILVA LOPES - DISSERTAÇÃO PROFLETRAS 2016.pdf: 1320308 bytes, checksum: b62d818b4bc33dbceef15819251da066 (MD5) Made available in DSpace on 2018-01-02T13:56:35Z (GMT). No. of bitstreams: 1 EPITÁCIO SILVA LOPES - DISSERTAÇÃO PROFLETRAS 2016.pdf: 1320308 bytes, checksum: b62d818b4bc33dbceef15819251da066 (MD5) Previous issue date: 2016-11-17 A sintaxe constitui um campo de estudo que diz respeito à combinação entre as palavras para a construção da frase. O ensino de sintaxe da língua portuguesa é inerente à capacidade de compreensão e elaboração de textos orais e escritos, embora encontre dificuldades no ensino atual. A partir disso, foi realizada uma pesquisa sobre as principais correntes da sintaxe, a disposição dos componentes sintáticos nos livros didáticos com o objetivo geral de propor estratégias de utilização de múltiplos usos da Teoria dos Grafos no ensino de sintaxe com o período simples no 8º ano do Ensino Fundamental. Alguns estudiosos vêm apresentando propostas para a melhoria desse estudo a partir dessa modalidade de ensino. Para compreender o ensino de sintaxe, de acordo com as diretrizes dos Parâmetros Curriculares Nacionais (PCN), a teoria em voga sobre os tipos de sintaxe e a forma como esta está presente nas escolas, observa-se um distanciamento entre o que se propõe pelas teorias e o que é vivenciado nas salas de aula através do livro didático, disseminando a ideia de que aprender sintaxe é difícil. A Teoria dos Grafos, método que permite ao aluno visualizar a estrutura da frase, compreender a sua organização e auxiliar como um facilitador para a sua produção, melhorando o processo comunicativo tanto no aspecto da escrita como da oralidade, colabora para melhor assimilação do conteúdo ensinado. Trata-se de uma pesquisa baseada em estudos bibliográficos com fins de reflexão sobre o ensino do componente sintático presente no livro didático adotado pela escola, visto de forma fragmentada e isolada, o que justifica propor meios para melhoria do ensino e compreensão da sintaxe, fundamentada, principalmente, nas produções de Borba (1979), Franchi (2013), Borgatto (2012), Cereja (2015), para construção de um guia didático que aborda o ensino de sintaxe com a Teoria dos Grafos. La sintaxis es un campo Lingüística Área de estudio que está relacionada con la combinación de las palabras para la construcción de la frase. La sintaxis de la educación de la lengua portuguesa es inherente a lo que se dice a la capacidad de comprensión y la preparación de textos orales y escritos, aunque tienen dificultades en los problemas educativos actuales. De esto, se realizó un estudio de las principales corrientes de la sintaxis, con el objetivo general de la propuesta de los múltiples usos de la Teoría de Grafos en la sintaxis simplemente periodo en el octavo grado de la escuela primaria la enseñanza. Algunos estudiosos han presentado propuestas para la mejora de este estudio de este tipo de educación. Para entender la sintaxis de la educación, de acuerdo con las directrices de los Parámetros Curriculares Nacionales (PCN) y la teoría en boga en los tipos de sintaxis y la forma en que esto está presente en las escuelas, hay una brecha entre lo que se propone teorías y lo que se vive en las aulas a través de los libros de texto, la difusión de la idea de que es difícil aprender la sintaxis. La teoría de grafos, método que permite a los estudiantes a visualizar la estructura de la oración, para comprender su organización y ayudar como facilitador para su producción, mejorando el proceso de comunicación, tanto en el aspecto de la escritura como la oralidad, contribuye a una mejor asimilación de los contenidos impartidos. Esta es una encuesta sobre la base de los estudios publicados con fines de reflexión sobre la enseñanza de componente sintáctico presente en el libro de texto adoptado por la escuela, como una forma fragmentada y aislada, lo que explica proponer formas de mejorar la enseñanza y la comprensión de la sintaxis, basadas, principalmente, en Borba productions (1979), Franchi (2013), Borgatto (2012), Cereja (2015), para la construcción de una guía didáctica que se ocupa de la sintaxis de la enseñanza con la Teoría de Grafos.

Planaridade em grafos: o teorema de Kuratowski Planarity in graphs : Kuratowski’s theorem

Santos, Emanoel Lázaro de Santana 26 August 2017 (has links)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES The present dissertation aims to introduce the basic concepts of graph theory to explore the concept of planarity and present a beautiful theorem connected to this theme. Graph theory is a very effective tool for solving problems involving several areas of knowledge. Some of these problems are related to planarity of graphs. Thus, this work presents Kuratowski’s theorem, with the beauty of its demonstration, which provides a necessary and sufficient condition for a graph to be planar, observing if it contains a specific type of subgraph related to complete and split graphs. A presente dissertaçãoo tem como objetivo introduzir os conceitos básicos da teoria dos grafos para explorar o conceito de planaridade e apresentar um belo teorema ligado a esse tema. A teoria dos grafos é uma ferramenta muito eficaz na resolução de problemas que envolvem diversas áreas de conhecimento. Alguns destes problemas estão relacionados `a planaridade de grafos. Dessa forma, este trabalho apresenta o teorema de Kuratowski, com a beleza de sua demonstra¸c˜ao, que fornece uma condição necessária e suficiente para um grafo ser planar, observando se o mesmo contém um tipo específico de subgrafo relacionado a grafos completos e bipartidos. São Cristóvão, SE

Caracterização de grafos de genealogia acadêmica por meio de métricas topológicas

Rossi, Luciano 2015 (has links)
Orientador: Prof. Dr. Jesús Pascual Mena-Chalco Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015. A busca pela origem de indivíduos apresenta-se como uma tentativa recorrente em obter respostas que expliquem o presente, com base no passado e permitam traçar os caminhos do futuro. A origem de um indivíduo esta ligada à algum tipo de relacionamento que possibilite identicar outro que o precedeu. Este modelo de estruturação de grupos sociais é objeto de estudo da genealogia. A genealogia acadêmica utiliza os relacionamentos de orientação entre professores (orientadores) e alunos (orientados) para criar a estrutura social que, comumente, é representada por um grafo de genealogia. O grafo descreve seus vértices como orientadores e orientados e suas arestas direcionadas descrevem as orientações acadêmicas existentes entre eles. Nesta dissertação de mestrado busca-se caracterizar os vértices de um grafo de genealogia considerando somente seus relacionamentos de orientação acadêmica. A caracterização dos vértices é realizada por meio do desenvolvimento e/ou adaptação de um conjunto de métricas topológicas. O conjunto é composto por 22 métricas, sendo 13 de composição descendente ((i) largura, (ii) número de folhas, (iii) profundidade, (iv) fecundidade, (v) fecundidade ponderada, (vi) maior largura, (vii) índice h genealógico, (viii) impacto, (ix) distância média, (x) média dos menores caminhos, (xi) pagerank inverso, (xii) pagerank inverso ponderado e (xiii) balanceamento pela fecundidade), 8 de composição ascendente ((xiv) fecundidade inversa, (xv) fecundidade média do território inverso, (xvi) fecundidade ponderada média do território inverso, (xvii) número de origens, (xviii) largura inversa, (xix) profundidade inversa, (xx) pagerank e (xxi) pagerank ponderado) e 1 de composição mista ((xxii) balanceamento global ). Acreditamos que todas as métricas propostas possam servir de insumo para analisar computacionalmente qualquer grafo de genealogia. Em particular, as métricas propostas foram calculadas para o conjunto de doutores em matemática cadastrados na plataforma do Mathematics Genealogy Project (MGP), que em Abril de 2014 contava com mais de 178 mil registros de 185 países, e permitiu realizar análises para: (i) observar características especícas dos vértices do grafo, (ii) estudar o efeito da abrangência das métricas (janela) na caracterização dos vértices e (iii) classicar os vértices em função dos conjuntos de valores de suas métricas. The search for the origin of individuals is presented as a recurrent attempt to get answers to explain the present, based on the past and to retrace the paths of the future. The origin of a subject is linked to some kind of relationship that allows identify others that preceded it. The academic genealogy uses the orientation relationships between professors (advisors) and students (advisees) to create a social structure that, commonly, is represented by a genealogy graph. The graph describes its vertices as advisors/advisees and the directed edges describe their existing academic guidelines between them. In this master thesis we present a characterization of a genealogy graph considering only their academic guindance relationships. The characterization of the vertices is performed through the development and / or adaptation of a set of topological metrics. The set consists of 22 metrics. The first 13 descending composition metrics are related with: (i) width, (ii) leaf number, (iii) depth, (iv) fecundity, (v) weighted fecundity, (vi) max width, (vii) genealogical h-index, (viii) impact, (ix) average distance (x) average of the shortest paths, (xi) reverse pagerank, (xii) reverse pagerank weighted and (xiii) balanced fecundity. Eight ascending composition metrics related with: (xiv) reverse fecundity, (xv) fecundity of the reverse territory, (xvi) weighted average fecundity of the reverse territory, (xvii) number of origins, (xviii) reverse width, (xix) reverse depth, (xx) pagerank and (xxi) weighted pagerank. Finally, one mixed composition metrics called (xxii) overall balance. We believe that all proposed metrics can serve as input to analyze genealogy graphs. The proposed metrics were calculated for all PhDs in mathematics registered on Mathematics Genealogy Project (MGP), which in April 2014 had more than 178,000 records from 185 countries, and allowed to perform analysis in order: (i) to observe specic characteristics of the graph vertices, (ii) to study the eect of coverage metrics (i.e, window size) in the characterization of vertices and, (iii) to classify the vertices according to the sets of values of their metrics.

Um modelo multiperspectiva para avaliação de desempenho de plataformas de processamento de grafos A multiperspective model for performance evaluation of graph processing platforms

Silva, Daniel Nascimento Ramos da 21 February 2017 (has links)
Submitted by Maria Cristina (library@lncc.br) on 2017-05-02T19:25:42Z No. of bitstreams: 1 dissertacao Daniel.pdf: 13436496 bytes, checksum: e52ea76aa8685ff28f62aea6a22f98cf (MD5) Approved for entry into archive by Maria Cristina (library@lncc.br) on 2017-05-02T19:25:53Z (GMT) No. of bitstreams: 1 dissertacao Daniel.pdf: 13436496 bytes, checksum: e52ea76aa8685ff28f62aea6a22f98cf (MD5) Made available in DSpace on 2017-05-02T19:26:02Z (GMT). No. of bitstreams: 1 dissertacao Daniel.pdf: 13436496 bytes, checksum: e52ea76aa8685ff28f62aea6a22f98cf (MD5) Previous issue date: 2017-02-21 Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Many emerging challenges currently arising in science relate to understanding the dynamics and structure of complex systems consisting of interacting components. People on online social networks, power grids, air transportation networks, human brain connections, and agents in the financial market are some examples of network systems present in many domains. These systems, given their scale and non-trivial connectivity patterns, are called complex networks. In this sense, the dimension of these networks turns imperative the adoption of computing systems in support to their analysis. In this case, graphs are the usual tool for the representation of complex networks. Moreover, as the scientific investigation for these graphs is of great significance for many domains, the researcher and developer communities have proposed many computing platforms for their processing. However, the multitude of graph processing platforms brings up questions about the implications of their adoption, given the analysis, network and computing environment characteristics of the analysts. Therefore, in this dissertation, we propose a multi-perspective model for the performance evaluation of graph processing platforms which differs from related works in simultaneously approaching the topic from four perspectives: algorithms, computing environment, networks, and platforms. Additionally, we carry out a performance evaluation study that follows the directives indicated by the proposed model for a representative set of algorithms, platforms, and networks, demonstrating the proposed model applicability as exhibits the relationship between algorithms, networks and platforms efficiency. Alguns dos desafios mais relevantes que surgem no cenário científico atual envolvem a compreensão da dinâmica e estrutura de sistemas complexos constituídos por componentes em interação. Pessoas em redes sociais online, sistemas de distribuição de energia, malhas aéreas, conexões no cérebro humano ou mesmo agentes no mercado financeiro são apenas alguns exemplos de tais sistemas em rede oriundos de diversas áreas. Esses sistemas, por causa de sua escala e da não trivialidade de seus padrões de conectividade, são chamados de redes complexas. Nesse contexto, a dimensão dessas redes torna imprescindível a utilização de sistemas computacionais em apoio às suas análises, sendo grafos a ferramenta típica de representação de redes complexas para sua modelagem computacional e estudo. Mais ainda, como a análise de grafos em diversos domínios é de grande relevância, muitas plataformas computacionais para o seu processamento têm sido propostas recentemente; o que provoca questionamentos pertinentes de quais as implicações da escolha de uma delas, dadas as características de análise, rede e ambiente computacional dos interessados. Portanto, esta dissertação propõe um modelo multiperspectiva de avaliação de desempenho de plataformas de processamento de grafos, o qual se distingue da literatura ao abordar o problema considerando simultaneamente quatro perspectivas: algoritmos, arquitetura computacional, plataformas e redes. Além disso, um estudo de avaliação de desempenho de um conjunto diverso e representativo de algoritmos, plataformas computacionais e redes é realizado utilizando as diretivas indicadas pelo modelo, demonstrando sua aplicabilidade ao expor o relacionamento entre as características de redes complexas e algoritmos com a eficiência computacional das plataformas.

Page generated in 0.027 seconds