Acessar o Zé Moleza
ou
O que você está pesquisando?
Grafos: O Problema de Hamilton e a Questão das Pontes de Leonhard Euler
1134 visualizações
6514 palavras
Adicionar aos favoritos
Loading...- | |
Problema 2.2 Será possível obter um grafo hamiltoniano a partir de um tabuleiro de xadrez, associando cada um dos seus 64 quadrados um vértice de um grafo cujas arestas ligam os vértices associados a quadrados entre os quais é possível efetuar um movimento do cavalo?
Teorema de Ore (1960) Dado um grafo G de ordem n, se para quaisquer dois vértices não adjacentes a soma das valências é não inferior a n, então G é hamiltoniano.
Demonstração: A demonstração deste resultado não é tão simples como a do teorema de Euler e, como tal, não vai ser efetuada apresentada. No entanto, ela pode ser vista em [2].
Notemos que o teorema de Ore não é, como o teorema de Euler, uma condição necessária e suficiente. De fato, o teorema estabelece apenas uma condição suficiente para que um grafo seja hamiltoniano. Notemos ainda que, qualquer grafo nas hipóteses do teorema de Ore é um grafo conexo.
O teorema seguinte resulta imediatamente do anterior. Deixamos a demonstração ao cuidado do leitor.
Teorema de Dirac (1952) Seja G=(V,A) um grafo de ordem superior ou igual a 3 e x um vértice de G com valência mínima. Se vG(x) for superior ou igual a |V|/2 então G é hamiltoniano.
Vimos que, olhando para as valências dos vértices, é possível dizer se um grafo conexo admite ou não um circuito de Euler, mas não temos um método tão simples para nos dizer quando é que um grafo possui um ciclo de…
É esse o conteúdo que você precisa?
Faça seu login e saiba como ver o trabalho completo
Institucional
Saiba como fazer
Trabalhos Acadêmicos
O Zé Moleza facilita sua vida acadêmica ajudando você em suas pesquisas, e a economizar o seu tempo e o seu dinheiro nos seus trabalhos de faculdade. São mais de 26144 pesquisa acadêmicas entre elas, monografia, temas de monografias, TCC, modelos de monografias, trabalhos de universidades, resenha, Paper, Ensaio, Bibliografia, Trabalhos Escolares.
Dicas de como fazer: Capa de Monografia, capa de TCC, Regras da ABNT, como fazer monografia, como fazer Projeto Final, como fazer seminário, como fazer capas, referências bibliográficas, modelo de monografia.
O Zé Moleza NÃO faz a venda de monografia e É TOTALMENTE CONTRA a compra de monografia pronta e trabalhos prontos. O Zé Moleza NÃO auxilia a quem compra monografia, NÃO apóia a quem quer comprar Trabalhos Prontos, e NÃO APROVA a quem quer comprar TCC prontos, dando dicas de formatação, regras da ABNT, dando sugestões de temas para monografia, resumo de livros, projeto de pesquisa, projeto de mestrado, projeto de pós-graduação, trabalhos acadêmicos, incentivando o usuário a desenvolver por conta própria sua monografia.
