Grafo cúbico

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.
O grafo de Petersen é um grafo cúbico.
O grafo bipartido completo K_{3,3} é um exemplo de grafo bicúbico
O grafo Frucht, o menor grafo cúbico assimétrico.

No campo da matemática da teoria dos grafos, um grafo cúbico é um grafo regular no qual todos os vértices tem grau três[1] . Em outras palavras um grafo cúbico é um grafo 3-regular. Grafos cúbicos são também chamados grafos trivalentes.

Um grafo bicúbico é um grafo bipartido cúbico.

Simetria[editar | editar código-fonte]

Em 1932, Ronald M. Foster começou a recolher exemplos de grafos simétricos cúbicos, formando o início do censo de Foster[2] . Muitos grafos individuais conhecidos são cúbicos e simétricos, incluindo o grafo de Petersen, o grafo de Nauru, o grafo de Coxeter, o grafo de Tutte–Coxeter, o grafo de Dyck, o grafo de Foster e o grafo de Biggs-Smith.

W. T. Tutte classificou os grafos simétricos cúbicos pelo menor número inteiro s tal que cada dois caminhos orientados de comprimento s podem ser mapeados entre si por exatamente uma simetria do grafo. Ele mostrou que s é no máximo 5, e deu exemplos de grafos com cada valor possível de s de 1 a 5[3] .

Grafoos cúbicos semi-simétrico incluem o grafo de Gray ( o menor grafo cúbico semi-simétrico), o grafo de Ljubljana, e o gaiola-12 de Tutte.

O grafo de Frucht é o menor grafo cúbico sem qualquer simetria: possui apenas um único automorfismo de grafos, o automorfismo identidade.

Coloração e conjuntos independentes[editar | editar código-fonte]

De acordo com o teorema de Brooks todo grafo cúbico com exceção do grafo completo K4 pode ser colorido com no máximo três cores. Portanto, todo grafo cúbico diferente de K 4 tem um conjunto independente de pelo menos n/3 vértices, onde n é o número de vértices no grafo: por exemplo, a maior classe de cor em uma 3-coloração tem pelo menos estes vértices.

De acordo com o teorema de Vizing todo grafo cúbico necessita três ou quatro cores para uma coloração de arestas. Uma 3-aresta-coloração é conhecida como uma coloração Tait, e fgorma uma partição das arestas do grafo em três acoplamentos perfeitos. Pelo teorema de coloração de linhas de König todo grafo bicúbico tem uma coloração de Tait.

Os grafos cúbicos sem ponte que não tem uma coloração de Tait são conhecidos como snarks. Eles incluem o grafo de Petersen, grafo de Tietze, os snarks Blanuša, o snark flor, o snark dupla-estrela, o snark Szekeres e o snark Watkins.

Existe um número infinito de snarks distintos. [4]

Hamiltonicidade[editar | editar código-fonte]

Houve muita pesquisa sobre Hamiltonicidade de grafos cúbicos. Em 1880, P.G. Tait conjecturou que todo grafos poliédricos cúbicos tem um circuito Hamiltoniano. William Thomas Tutte forneceu um contra-exemplo para a conjectura de Tait, o grafo de Tutte de 46 vértices, em 1946. Em 1971, Tutte conjecturou que todos os grafos bicúbicos são hamiltonianos. No entanto, José Horton proporcionou um contra-exemplo com 96 vértices, o grafo de Horton[5] . Mais tarde Mark Ellingham, construíu mais dois contra-exemplos: os grafos de Ellingham-Horton[6] [7] . A conjectura de Barnette, uma combinação de conjecturas de Tait e Tutte ainda aberta, afirma que todo grafo bicúbico poliédrico é hamiltoniano. Quando um grafo cúbico é hamiltoniano, a notação LCF permite que ele seja representada de forma concisa.

Se um grafo cúbico é escolhido aleatoriamente entre todos os grafos cúbicos de n-vértices, então é bem provável que seja Hamiltoniano. a proporção de grafos cúbicos de n-vértices que são Hamiltonianos tende a um no limite a medida que n vai para o infinito[8] .

David Eppstein conjecturou que todo grafo cúbico de n-vértices tem no máximo 2n/3 (aproximadamente 1260n) ciclos hamiltonianos distintos, e exemplificou com grafos cúbicos com esta quantidade de ciclos[9] . O melhor limite superior que foi até agora comprovado no número de ciclos hamiltonianos distintos é 1,276n.[10]

Outras propriedades[editar | editar código-fonte]

O comprimento do caminho de quaisquer grafo cúbico de n-vértices é no máximo n/6. No entanto, o limite inferior melhor conhecido no comprimento do caminho de grafos cúbicos é menor, 0.082n.[11]

Se segue do lema do aperto de mãos, provado por Leonhard Euler em 1736 como parte do primeiro trabalho sobre teoria dos grafos, que todo grafo cúbico tem um número par de vértices.

Algoritmos e complexidade[editar | editar código-fonte]

Vários pesquisadores têm estudado a complexidade de tempo exponencial de algoritmos restritos a grafos cúbicos. Por exemplo, através da aplicação de programação dinâmica para a decomposição do caminho do grafo, Fomin e Høie mostraram como encontrar os seus conjuntos independentes máximos em tempo O(nn/6 + o(n)).[11]


História[editar | editar código-fonte]

  • 1971: William Tutte conjetura que todos os grafos bicúbicos são ciclos hamiltonianos. Entretanto, Horton proporciona un grafo de contra-exemplo, com 96-vértices.

Referências

  1. BOAVENTURA NETTO, Paulo Oswaldo. Grafos. São Paulo: Edgard Blücher, 2001. p. 20. ISBN 85-212-0292-X
  2. Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309-317, 1932
  3. TUTTE, W. T.. (1959). "On the symmetry of cubic graphs". Canad. J. Math 11: 621–624..
  4. ISAACS, R.. (1975). "Infinite families of nontrivial trivalent graphs which are not Tait colorable". American Mathematical Monthly 82 (3): 221–239. DOI:10.2307/2319844..
  5. Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
  6. Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
  7. Ellingham, M. N. and Horton, J. D. "Non-Hamiltonian 3-Connected Cubic Bipartite Graphs." J. Combin. Th. Ser. B 34, 350-353, 1983.
  8. Robinson, R.W.; Wormald, N.C.. (1994). "Almost all regular graphs are Hamiltonian". Random Structures and Algorithms 5 (2) p. 363–374. DOI:10.1002/rsa.3240050209..
  9. Eppstein, David (2007). "The traveling salesman problem for cubic graphs". Journal of Graph Algorithms and Applications 11 (1) p. 61–81. Arxiv.
  10. Gebauer, H. (2008). "On the number of Hamilton cycles in bounded degree graphs". Proce. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08). .
  11. a b Fomin, Fedor V.; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms", Information Processing Letters 97 (5): 191–196, doi:10.1016/j.ipl.2005.10.012 .
  12. O censo de Foster. Página visitada em 2010-11-13.
  13. Petr Hliněný (2003). Crossing Number Is Hard for Cubic Graphs 772-782 pp. MFCS 2004.