caminho hamiltoniano

caminho hamiltoniano (Redirecionado do teorema de Bondy-Hvátal) Ir para a navegação Ir para a pesquisa Este artigo é sobre a natureza dos caminhos hamiltonianos. Para a questão da existência de um caminho ou ciclo hamiltoniano em um determinado grafo, veja o problema do caminho hamiltoniano. A Hamiltonian cycle around a network of six vertices In the mathematical field of graph theory, um caminho hamiltoniano (ou caminho rastreável) é um caminho em um grafo direcionado ou não direcionado que visita cada vértice exatamente uma vez. Um ciclo hamiltoniano (ou circuito hamiltoniano) é um ciclo que visita cada vértice exatamente uma vez. Um caminho hamiltoniano que começa e termina em vértices adjacentes pode ser completado adicionando mais uma aresta para formar um ciclo hamiltoniano, e remover qualquer aresta de um ciclo hamiltoniano produz um caminho hamiltoniano. Determinando se tais caminhos e ciclos existem em gráficos (o problema do caminho hamiltoniano e o problema do ciclo hamiltoniano) são NP-completos.

Caminhos e ciclos hamiltonianos são nomeados após William Rowan Hamilton que inventou o jogo icosiano, agora também conhecido como quebra-cabeça de Hamilton, que envolve encontrar um ciclo hamiltoniano no grafo de arestas do dodecaedro. Hamilton resolveu este problema usando o cálculo icosiano, uma estrutura algébrica baseada em raízes de unidade com muitas semelhanças com os quatérnions (também inventado por Hamilton). Esta solução não se generaliza para grafos arbitrários.

Apesar de ter o nome de Hamilton, Ciclos hamiltonianos em poliedros também haviam sido estudados um ano antes por Thomas Kirkman, quem, em particular, deu um exemplo de um poliedro sem ciclos hamiltonianos.[1] Ainda mais cedo, Ciclos e caminhos hamiltonianos no gráfico do cavalo do tabuleiro de xadrez, o passeio do cavaleiro, tinha sido estudado no século 9 em matemática indiana por Rudrata, e na mesma época na matemática islâmica por al-Adli ar-Rumi. Na Europa do século XVIII, passeios do cavaleiro foram publicados por Abraham de Moivre e Leonhard Euler.[2] Conteúdo 1 Definições 2 Exemplos 3 Propriedades 4 Bondy - Teorema Agarrado 5 Existência de ciclos hamiltonianos em grafos planares 6 O polinômio do ciclo hamiltoniano 7 Veja também 8 Notas 9 Referências 10 External links Definitions A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once. Um grafo que contém um caminho hamiltoniano é chamado de grafo rastreável. Um grafo é hamiltoniano-conectado se para cada par de vértices existe um caminho hamiltoniano entre os dois vértices.

Um ciclo hamiltoniano, circuito hamiltoniano, passeio de vértice ou ciclo de grafo é um ciclo que visita cada vértice exatamente uma vez. Um grafo que contém um ciclo hamiltoniano é chamado de grafo hamiltoniano.

Noções semelhantes podem ser definidas para gráficos direcionados, onde cada borda (arco) de um caminho ou ciclo só pode ser rastreado em uma única direção (ou seja, os vértices são conectados com setas e as arestas traçadas "cauda a cabeça").

Uma decomposição hamiltoniana é uma decomposição de aresta de um grafo em circuitos hamiltonianos.

Um labirinto de Hamilton é um tipo de quebra-cabeça lógico no qual o objetivo é encontrar o único ciclo hamiltoniano em um determinado grafo.[3][4] Exemplos Projeções ortográficas e diagramas de Schlegel com ciclos hamiltonianos dos vértices dos cinco sólidos platônicos – apenas o octaedro tem um caminho ou ciclo euleriano, estendendo seu caminho com o pontilhado vte Um grafo completo com mais de dois vértices é Hamiltoniano Todo grafo de ciclo é Hamiltoniano Todo torneio tem um número ímpar de caminhos hamiltonianos (É seu 1934) Cada sólido platônico, considerado como um gráfico, é hamiltoniano[5] O gráfico de Cayley de um grupo Coxeter finito é Hamiltoniano (Para obter mais informações sobre caminhos hamiltonianos em gráficos de Cayley, veja a conjectura de Lovász.) Os gráficos de Cayley em grupos nilpotentes com subgrupo de comutador cíclico são hamiltonianos.[6] O flip chart de um polígono convexo ou equivalente, o gráfico de rotação de árvores binárias, é Hamiltoniano.[7][8] Propriedades O grafo de Herschel é o menor grafo poliédrico possível que não possui um ciclo hamiltoniano. Um possível caminho hamiltoniano é mostrado.

Qualquer ciclo hamiltoniano pode ser convertido em um caminho hamiltoniano removendo uma de suas arestas, mas um caminho hamiltoniano pode ser estendido ao ciclo hamiltoniano somente se seus pontos finais forem adjacentes.

Todos os grafos hamiltonianos são biconectados, mas um grafo biconectado não precisa ser hamiltoniano (Vejo, por exemplo, o gráfico de Petersen).[9] Um grafo euleriano G (um grafo conexo em que cada vértice tem grau par) necessariamente tem um tour de Euler, um passeio fechado passando por cada aresta de G exatamente uma vez. Este passeio corresponde a um ciclo hamiltoniano no gráfico de linha L(G), então o gráfico de linha de todo gráfico euleriano é hamiltoniano. Os gráficos de linha podem ter outros ciclos hamiltonianos que não correspondem aos passeios de Euler, e em particular o gráfico de linha L(G) de todo grafo hamiltoniano G é ele próprio hamiltoniano, independentemente de o grafo G ser euleriano.[10] Um torneio (com mais de dois vértices) é hamiltoniano se e somente se for fortemente conexo.

O número de diferentes ciclos hamiltonianos em um grafo não direcionado completo em n vértices é (n - 1)! / 2 e em um grafo dirigido completo em n vértices é (n - 1)!. Essas contagens assumem que os ciclos que são iguais fora do ponto de partida não são contados separadamente.

Bondy–Chvátal theorem The best vertex degree characterization of Hamiltonian graphs was provided in 1972 pelo teorema de Bondy-Grab, que generaliza resultados anteriores por G. UMA. Dirac (1952) e minério de Øystein. Tanto o teorema de Dirac quanto o de Ore também podem ser derivados do teorema de Pósa (1962). A Hamiltonicidade tem sido amplamente estudada em relação a vários parâmetros, como a densidade do gráfico, dureza, subgrafos proibidos e distância entre outros parâmetros.[11] Os teoremas de Dirac e Ore basicamente afirmam que um grafo é hamiltoniano se tiver arestas suficientes.

O teorema de Bondy-Chvátal opera no fechamento cl(G) de um grafo G com n vértices, obtido pela adição repetida de uma nova aresta uv conectando um par não adjacente de vértices u e v com deg(v) + grau(você) ≥ n até que não sejam encontrados mais pares com esta propriedade.

Bondy – Agarrado pelo Teorema (1976) — A graph is Hamiltonian if and only if its closure is Hamiltonian.

Como os grafos completos são hamiltonianos, todos os grafos cujo fechamento é completo são hamiltonianos, que é o conteúdo dos seguintes teoremas anteriores de Dirac e Ore.

Teorema de Dirac (1952) — A simple graph with n vertices ( {ngeq de estilo de exibição 3} ) é hamiltoniano se todo vértice tem grau {estilo de exibição {tfrac {n}{2}}} ou melhor.

Teorema de Ore (1960) — A simple graph with n vertices ( {ngeq de estilo de exibição 3} ) é hamiltoniano se, para cada par de vértices não adjacentes, a soma de seus graus é n ou maior.

Os seguintes teoremas podem ser considerados como versões dirigidas: Ghouila–Houiri (1960) — A strongly connected simple directed graph with n vertices is Hamiltonian if every vertex has a full degree greater than or equal to n.

Meiniel (1973) — A strongly connected simple directed graph with n vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to {estilo de exibição 2n-1} O número de vértices deve ser dobrado porque cada aresta não direcionada corresponde a dois arcos direcionados e, portanto, o grau de um vértice no grafo direcionado é o dobro do grau no grafo não direcionado.

Rahman-Kaykobad (2005) — A simple graph with n vertices has a Hamiltonian path if, para cada par de vértices não adjacentes a soma de seus graus e seu comprimento de caminho mais curto é maior que n.[12] O teorema acima só pode reconhecer a existência de um caminho hamiltoniano em um grafo e não um ciclo hamiltoniano.

Muitos desses resultados têm análogos para gráficos bipartidos balanceados, em que os graus dos vértices são comparados com o número de vértices em um único lado da bipartição em vez do número de vértices em todo o grafo.[13] Existence of Hamiltonian cycles in planar graphs Theorem — A 4-connected planar triangulation has a Hamiltonian cycle.[14] Theorem — A 4-connected planar graph has a Hamiltonian cycle.[15] The Hamiltonian cycle polynomial An algebraic representation of the Hamiltonian cycles of a given weighted digraph (cujos arcos são atribuídos pesos de um determinado campo de terra) é o polinômio do ciclo hamiltoniano de sua matriz de adjacência ponderada definida como a soma dos produtos dos pesos dos arcos dos ciclos hamiltonianos do dígrafo. Este polinômio não é identicamente zero como uma função nos pesos do arco se e somente se o dígrafo for hamiltoniano. A relação entre as complexidades computacionais de computá-lo e computar o permanente foi mostrada por Grigoriy Kogan.[16] Veja também a conjectura de Barnette, um problema aberto sobre Hamiltonicidade de grafos poliédricos bipartidos cúbicos caminho Euleriano, um caminho através de todas as arestas em um grafo teorema de Fleischner, em quadrados hamiltonianos de grafos Código de Gray Teorema de Grinberg dando uma condição necessária para grafos planares terem um ciclo hamiltoniano Problema de caminho hamiltoniano, o problema computacional de encontrar caminhos hamiltonianos Grafo hipohamiltoniano, um grafo não-hamiltoniano no qual cada subgrafo deletado de vértices é o tour de Hamiltonian Knight, um ciclo hamiltoniano no gráfico do cavaleiro notação LCF para gráficos cúbicos hamiltonianos. Conjectura de Lovász de que grafos transitivos de vértices são grafos pancíclicos hamiltonianos, gráficos com ciclos de todos os comprimentos, incluindo um ciclo hamiltoniano Sete pontes de Königsberg Expoente de curta duração, uma medida numérica de quão longe do Hamiltoniano os gráficos em uma família podem ser Snake-in-the-box, o caminho induzido mais longo em um algoritmo de Steinhaus-Johnson-Trotter hipercubo para encontrar um caminho hamiltoniano em um grafo subhamiltoniano permutohedron, um subgrafo de um grafo hamiltoniano planar Conjectura de Tait (agora conhecido falso) que os grafos poliédricos tri-regulares são problema do caixeiro viajante Hamiltoniano Notas ^ Biggs, N. eu. (1981), "T. P. Kirkman, matemático", O Boletim da Sociedade Matemática de Londres, 13 (2): 97-120, doi:10.1112/blms/13.2.97, SENHOR 0608093. ^ Watkins, John J. (2004), "Capítulo 2: Passeios de Cavaleiro", De maneira geral: A matemática dos problemas do tabuleiro de xadrez, Imprensa da Universidade de Princeton, pp. 25-38, ISBN 978-0-691-15498-5. ^ o cavaleiro, João (2017). Hamilton Mazes - O Guia do Iniciante. ^ Friedman, Eric (2009). "Labirintos Hamiltonianos". Palácio do enigma de Erich. Arquivado a partir do original em 16 abril 2016. Recuperado 27 Poderia 2017. ^ Gardner, M. "Jogos Matemáticos: Sobre a notável semelhança entre o Jogo Icosiano e as Torres de Hanói." Sci. América. 196, 150-156, Poderia 1957 ^ Ghaderpour, E.; Morris, D. C. (2014). "Os gráficos de Cayley em grupos nilpotentes com subgrupo de comutador cíclico são hamiltonianos". Ars Mathematica Contemporânea. 7 (1): 55-72. arXiv:1111.6216. doi:10.26493/1855-3974.280.8d3. ^ Lucas, Joan M. (1987), "O gráfico de rotação de árvores binárias é Hamiltoniano", Diário de Algoritmos, 8 (4): 503-535, doi:10.1016/0196-6774(87)90048-4 ^ Hurtado, Ferran; Noy, Marco (1999), "Gráfico de triangulações de um polígono convexo e árvore de triangulações", Geometria Computacional, 13 (3): 179-188, doi:10.1016/S0925-7721(99)00016-4 ^ Eric Weinstein. "Gráfico biconectado". Wolfram MathWorld. ^ Balakrishnan, R.; Ranganatã, K. (2012), "Corolário 6.5.5", Um livro de teoria dos grafos, Springer, p. 134, ISBN 9781461445296. ^ Gould, Ronald J. (Julho 8, 2002). "Avanços no Problema Hamiltoniano - Uma Pesquisa" (PDF). Universidade de Emory. Recuperado 2012-12-10. ^ Rahman, M. S.; Kaykobad, M. (abril 2005). "Sobre ciclos hamiltonianos e caminhos hamiltonianos". Cartas de Processamento de Informações. 94: 37-41. doi:10.1016/j.ipl.2004.12.002. ^ Lua, J.; Moser, eu. (1963), "Em grafos bipartidos hamiltonianos", Jornal de Matemática de Israel, 1 (3): 163-165, doi:10.1007/BF02759704, SENHOR 0161332 ^ Whitney, Hassler (1931), "Um teorema sobre gráficos", Anais da Matemática, Segunda Série, 32 (2): 378-390, doi:10.2307/1968197, JSTOR 1968197, SENHOR 1503003 ^ Tutte, C. T. (1956), "Um teorema em grafos planares", Trans. América. Matemática. Soc., 82: 99-116, doi:10.1090/s0002-9947-1956-0081471-8 ^ Kogan, Gregório (1996), "Calculando permanentes sobre campos de características 3: onde e por que se torna difícil", 37º Simpósio Anual de Fundamentos da Ciência da Computação (FOGO '96): 108-114, doi:10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2 Referências Berge, Claude; Ghouila-Houiri, UMA. (1962), Programação, jogos e redes de transporte, Nova york: Filhos, Inc. DeLeon, Melissa (2000), "Um estudo de condições suficientes para ciclos hamiltonianos" (PDF), Revista de Matemática de Graduação Rose-Hulman, 1 (1), arquivado a partir do original (PDF) sobre 2012-12-22, recuperado 2005-11-28. Dirac, G. UMA. (1952), "Alguns teoremas sobre gráficos abstratos", Anais da Sociedade Matemática de Londres, 3Sér., 2: 69-81, doi:10.1112/plms/s3-2.1.69, SENHOR 0047308. Hamilton, William Rowan (1856), "Memorando respeitando um novo sistema de raízes da unidade", Revista Filosófica, 12: 446. Hamilton, William Rowan (1858), "Conta do Cálculo Icosiano", Anais da Academia Real Irlandesa, 6: 415-416. Meiniel, M. (1973), "Uma condição suficiente para a existência de um circuito hamiltoniano em um grafo direcionado", Jornal de Teoria Combinatória, Série B, 14 (2): 137-147, doi:10.1016/0095-8956(73)90057-9, SENHOR 0317997. Minério, Øystein (1960), "Nota sobre circuitos de Hamilton", O American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928, SENHOR 0118683. chique, eu. (1962), "Um teorema sobre linhas de Hamilton", Tud húngaro. Atrasos. Esteira. Pesquisa Internacional. Com., 7: 225-226, SENHOR 0184876. Weissstein esquerdo externo, Eric W. "Ciclo Hamiltoniano". MathWorld. Tour de Euler e ciclos de Hamilton Categorias: Problemas computacionais em teoria dos grafosProblemas NP-completosObjetos da teoria dos grafosCaminhos e ciclos hamiltonianosWilliam Rowan Hamilton