Neste trabalho abordaremos a an alise espectral de grafos por dois estudos: técnicas de probabilidade quântica e por polinômios ortogonais com valores em matrizes. No Capítulo 1, consideraremos a matriz de adjacência do grafo tal como um operador linear e sua decomposição quântica permitir a uma an alise espectral que produzir a um teorema do limite central para tal grafo. No Capítulo 2, consideraremos uma medida com valores em matrizes induzida por polinômios ortogonais com valores em matrizes. Sob certas condições, e possível exibir explicitamente uma expressão de tal medida. Algumas aplicações em teoria dos grafos são dadas quando nos restringimos as matrizes estoc asticas e com valores em 0-1. Do nosso conhecimento, os cálculos e exemplos obtidos nas seçõoes 0.3.2, 0.3.3, 2.4 e 2.5 são novos. / In this work we focus on the spectral analysis of graphs via two studies: quantum probabilistic techniques and by orthogonal matrix-valued polynomials. In Chapter 1 we consider the adjacency matrix of a graph as a linear operator, and its quantum decomposition will allow a spectral analysis that will produce a central limit theorem for such graph. In Chapter 2, we consider a matrix-valued measure induced by orthogonal matrix-valued polynomials. Under certain conditions, it is possible to display an explicit expression for such measure. Some applications to combinatorics and graph theory are given when we restrict to the stochastic and 0-1 matrices. Up to our knowledge, the calculations and examples obtained in sections 0.3.2, 0.3.3, 2.4 and 2.5 are new.

Cografos representam uma classe de grafos que pode ser de nida e caracterizada de diversas maneiras. A estrutura de relacionamento entre seus vértices, permite que um cografo possa ser construído de forma recursiva a partir de um único vértice. Neste trabalho estudamos algumas caracterizações clássicas de cografos, dentre as quais abordamos: livre de P4, formas recursivas utilizando união, complemento e junção, diâmetro de todo subgrafo induzido 2, vértices irmãos, propriedade CK(clique Kernel), e formas recusivas utilizando duplicação e coduplica ção de vértices. A principal contribuição foi relacionar algumas das diferentes formas de caracterizações de um cografo com a de nição de grafo complementar redutível. Apresentamos algumas formas de representar cografos, que podem ser encontradas em diversos trabalhos, como forma normalizada, coárvore e matriz de adjacência. Estudamos um algoritmo que auxilia na localização de autovalores em cografos, como contribuição apresentamos os detalhes teóricos sobre seu funcionamento através da Lei na Inércia de Sylvester, e da obtenção de matrizes congruentes à matriz A+xI, onde A é a matriz de adjacência de um cografo, x é um número real e I é a matriz identidade de mesma ordem de A. Com este algoritmo, estudamos alguns resultados clássicos sobre o espectro de um cografo, que são: a multiplicidade dos autovalores 1 e 0, e que um cografo não possui autovalores no intervalo (1; 0). Além disso, apresentaremos algumas aplicações para obter famílias de cografos com a mesma energia de grafos completos Kn. / Cographs are a class of graphs that can be de ned and characterized in several ways. The structure given in terms of vertices enable a cograph to be built by recursive form from a single vertice. In this work, we study some classical characterizations of cographs, among which: P4 - free, recursive form with union, complement and join, diameter of all induced subgraph connected 2, siblings vertices, property CK(cliqueKernel), and recursive form by duplication and coduplication of vertices. As main contribution, we establish a relationship between some characterizations of cographs, which is a complement reducible graph. We also show some ways to make a mathematical representation that can be found in various works, as normalized form, cotree and adjacency matrix. We study an algorithm that can help us to nd eigenvalues in cographs, as an additional contribution we provide the theoretical details about its operation through the Sylvester Law of Inertia and how to get congruent matrices from A+xI, where A is the adjacency matrix of a cograph, x is a real number and I is a identity matrix with the same order of A. Using the algorithm, we study some classical results about spectral set of a cograph, as the multiplicity of eigenvalues 1 and 0, and the statement of no cographs have eigenvalues in (1; 0). In addition, we show some applications to nd cograph families with the same energy of complete graphs Kn.

Nesta tese apresentamos solu c~oes de dois problemas de colora c~ao de grafos. Para as solu c~oes de ambos problemas, utilizamos ferramentas probabil sticas. Em um desses problemas de colora c~ao, consideramos o espa co de probabilidade Gk n;p dos grafos aleat orios coloridos. Provamos que, para cada k 3, o limiar para a propriedade de que um grafo aleat orio colorido cont em uma arvore geradora propriamente colorida e log n=n, que e precisamente o limiar para a conexidade. Para resolver esse problema, utilizamos uma cota para a cardinalidade de um emparelhamento m aximo em Gn;(1+ ) log n=n, provada por Frieze em 1986. Embora tal cota seja su ciente para resolver esse problema, investigamos o problema da cardinalidade de um emparelhamento m aximo no grafo aleat orio Gn;(1+ ) log n=n e obtivemos um resultado mais preciso. O outro problema de colora c~ao e um problema determin stico, por em, para a solu c~ao deste, utilizamos um resultado de enumera c~ao de grafos cuja demonstra c~ao apresenta argumentos probabil sticos. Dados r t 3 e ` 1, procuramos por grafos com n v ertices que admitem o maior n umero de r-colora c~oes tais que no m aximo t1 cores aparecem pelo menos ` vezes em arestas incidentes a cada v ertice, isto e, r-colora c~oes livres de St;`-arco- ris (estrelas com t` arestas coloridas com t cores distintas tal que cada cor e atribu da a exatamente ` arestas). Para n grande, mostramos que, o grafo completo Kn e o unico grafo extremal. / In this thesis, we obtain solutions for two graph coloring problems, both of which rely on probabilistic tools. In one of these coloring problems, we consider the probability space Gk n;p of edge-colored random graphs. We prove that, for all xed k 3, the threshold for the property that an edge-colored random graph contains a properly colored spanning tree is log n=n, precisely the threshold for connectivity. To solve this problem, we used a bound for the size of a maximum matching in Gn;(1+ ) log n=n, proved by Frieze in 1986. Although such bound is su cient to solve this problem, we investigated the problem of the size of a maximum matching in the random graph Gn;(1+ ) log n=n and we obtained a more precise result. Even though the other coloring problem is deterministic, we used a graph enumeration whose proof is probabilistic. Given r t 3 and ` 1, we look for n-vertex graphs that admit the maximum number of r-edge-colorings such that at most t 1 colors appear at least ` times in edges incident with each vertex, that is, r-edge-colorings avoiding rainbow-St;` (stars with t` edges colored with t distinct colors such that each color is assign to exactly ` edges). For large n, we show that, the complete graph Kn is always the unique extremal graph.

Neste trabalho tratamos de um problema clássico bem conhecido em Teoria dos Grafos: o problema da existência de um ciclo hamiltoniano. Um grafo é dito hamiltoniano se possui um ciclo hamiltoniano, ou seja, apresenta um ciclo que percorre todos os vértices do grafo. Estudamos problemas clássicos associados a este problema em termos do número de arestas, do grau mínimo e da sequência de graus dos vértices de um grafo. Além disso, estudamos resultados espectrais para o problema de hamiltonicidade referentes às matrizes de adjacências e laplaciana. A principal contribuição deste trabalho é a apresentação detalhada de condições suficientes e condições necessárias que garantem um ciclo hamiltoniano em um grafo já existentes na bibliografia. / In this work we study a well-known problem in Graph Theory: the existence of a Hamilton cycle, namely a cycle that goes through every vertex in the graph. We consider classical su cient conditions related with this problem in terms of the number of edges, the minimum degree and the vertex degree sequence of a graph. Furthermore, we study spectral results for the hamiltonian problem in terms of the adjacency and laplacian matrix. The main contribution of this work is our detailed presentation of necessary and su cient conditions for the existence of a Hamilton cycle in a graph.

Orientador: Candido Ferreira Xavier de Mendonça Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-11-01T12:49:48Z (GMT). No. of bitstreams: 1 Xavier_EricoFabricio_M.pdf: 2893754 bytes, checksum: 024785fd687ba8f119cb99c3faa86797 (MD5) Previous issue date: 1999 / Resumo: O splitting number de um grafo G consiste no número mínimo de operações de quebra de vértice que devem ser realizadas em G para produzir um grafo planar, onde uma operação de quebra de vértice em um determinado vértice u significa substituir algumas das arestas ( u, v) por arestas (u', v), onde u' é um novo vértice. O skewness de G é o número mínimo de arestas que devem ser removidas de G para torná-Io planar. O vertex deletion number de G é o menor inteiro k tal que existe um subgrafo induzido planar de G obtido através da remoção de k vértices de G.Neste trabalho, apr~sentamos valores exatos para o splitting number, o skewness e o vertex deletion number dos grafos Cn x Cm, onde Cn é o circuito simples com n vértices, e para o splitting number e o vertex deletion number de uma triangulação dos grafos Cn x Cm / Abstract: The splíttíng number of a graph G is the minimum number of splitting steps needed to turn G into a planar graph; where each step replaces some of the edges (u, v) incident to a selected vertex u by edges (u', v), where u' is a new vertex. The skewness of G is the minimum number of edges that need to be deleted from G to produce a planar graph. The vertex deletíon number of G is the smallest integer k such that there is a planar induced subgraph of G obtained by the removal of k vertices of G. In this work, we show exact values for the splíttíng number, skewness and vertex deletíon number of the graphs Cn x Cm, where Cn is the simple circuit on n vertices, and for the splíttíng number and vertex deletíon number of a triangulation of Cn x Cm / Mestrado / Mestre em Ciência da Computação

Tese de Mestrado. Informática. Faculdade de Ciências. Universidade do Porto. 2007

Definición de un grafo. Implementación de un grafo. Problemas resueltos con grafos. Algoritmos de la ruta más corta. Algoritmo de Dijkstra.

Algoritmo Ford Fulkerson para Flujo Máximo en un grafo.

Neste trabalho abordaremos a an alise espectral de grafos por dois estudos: técnicas de probabilidade quântica e por polinômios ortogonais com valores em matrizes. No Capítulo 1, consideraremos a matriz de adjacência do grafo tal como um operador linear e sua decomposição quântica permitir a uma an alise espectral que produzir a um teorema do limite central para tal grafo. No Capítulo 2, consideraremos uma medida com valores em matrizes induzida por polinômios ortogonais com valores em matrizes. Sob certas condições, e possível exibir explicitamente uma expressão de tal medida. Algumas aplicações em teoria dos grafos são dadas quando nos restringimos as matrizes estoc asticas e com valores em 0-1. Do nosso conhecimento, os cálculos e exemplos obtidos nas seçõoes 0.3.2, 0.3.3, 2.4 e 2.5 são novos. / In this work we focus on the spectral analysis of graphs via two studies: quantum probabilistic techniques and by orthogonal matrix-valued polynomials. In Chapter 1 we consider the adjacency matrix of a graph as a linear operator, and its quantum decomposition will allow a spectral analysis that will produce a central limit theorem for such graph. In Chapter 2, we consider a matrix-valued measure induced by orthogonal matrix-valued polynomials. Under certain conditions, it is possible to display an explicit expression for such measure. Some applications to combinatorics and graph theory are given when we restrict to the stochastic and 0-1 matrices. Up to our knowledge, the calculations and examples obtained in sections 0.3.2, 0.3.3, 2.4 and 2.5 are new.

Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. / Made available in DSpace on 2012-10-16T22:12:42Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-08T17:34:02Z : No. of bitstreams: 1 138806.pdf: 2193196 bytes, checksum: 2514d856661c8ebb3a9df581d2d6a7d3 (MD5)