Um gráfico
Conheça Larry. Ele tem a missão de visitar todas as casas de um bairro. Por que ele quer visitar todas as casas de um bairro? Ele quer que as pessoas saibam sobre um programa especial do qual ele faz parte, que oferece café da manhã e sapatos grátis para todas as crianças da vizinhança. Para que este programa seja um sucesso, Larry precisa de doações. Portanto, seu propósito em visitar todos é duplo. Por um lado, ele quer que as pessoas saibam sobre o programa para que possam tirar proveito dele e, segundo, ele quer ver se algumas delas estão dispostas a fazer doações para beneficiar este programa especial. Larry desenhou um diagrama do bairro usando pontos para as casas e linhas para as estradas que ligam as casas. Vemos que há dez casas neste bairro e vemos as linhas que ligam as casas umas às outras.
 |
Circuito de Hamilton
Para aproveitar o tempo, Larry quer encontrar um caminho onde visite cada casa apenas uma vez e termine onde começou. Na teoria dos grafos, esse caminho é chamado de circuito de Hamilton , um circuito que vai a cada vértice apenas uma vez e termina no ponto inicial. Um vértice é onde duas linhas retas se encontram para formar um ângulo.
Olhando para seu diagrama, Larry vê que se ele visitar todas as casas na periferia primeiro e depois visitar cada casa no interior da vizinhança, ele poderá visitar cada casa apenas uma vez e terminar onde começou. Por exemplo, se ele começa com a casa A, ele pode ir para as casas B, C, D e E. Então ele pode ir para as casas F, J, I, H e então G. Finalmente, voltar para a casa A o leva de volta para onde ele começou. Ele fez um circuito de Hamilton.
Caminho de Hamilton
Se Larry não se importou onde foi parar, ele pode escolher trilhar um caminho de Hamilton , um caminho que vai até cada vértice apenas uma vez, mas termina em um local diferente. Olhando para este gráfico, Larry vê que pode trilhar esse tipo de caminho de maneira semelhante ao circuito de Hamilton. Ele pode começar na casa A, então ir para as casas B, C, D e E. Então ele pode cortar nas casas internas e visitar as casas F, G, H, I e finalmente J. Ele percorreu um caminho de Hamilton e visitou cada casa apenas uma vez, terminando em algum lugar diferente de onde começou.
Mais circuitos e caminhos
Você deve ter notado que o caminho que Larry escolheu tanto para o circuito quanto para o caminho de Hamilton é apenas um caminho que ele poderia ter seguido. Existem outras rotas que ele poderia ter seguido. Por exemplo, outro circuito de Hamilton visitaria as casas começando com E, indo para J, D, I, C, H, B, G, A, F e de volta para E. Outro caminho de Hamilton poderia ser C, H, I , D, J, E, F, G, B e então A. Existem ainda mais rotas que Larry poderia ter seguido. Veja se você consegue identificá-los.
Resumo da lição
Agora, vamos revisar o que aprendemos. Aprendemos que um circuito de Hamilton é um circuito que vai para cada vértice apenas uma vez e termina no ponto inicial, e um caminho de Hamilton é um caminho que vai para cada vértice apenas uma vez, mas termina em um ponto diferente. É possível que os gráficos tenham mais de um circuito ou caminho. Como você pode ver, esses problemas se aplicam no mundo real a pessoas que precisam visitar vários locais e querem encontrar o melhor caminho a seguir.
Resultados de Aprendizagem
Ao concluir a vídeo-aula, teste sua capacidade de:
- Fornece definições para circuito e caminho de Hamilton
- Trabalhe com um exemplo do mundo real do circuito de Hamilton e do caminho de Hamilton