Circuitos de Hamilton

Páginas: 3 (717 palavras) Publicado: 22 de outubro de 2013

Circuitos de Hamilton


Tarefa 1

Considere o grafo da figura.




a) Como classifica este grafo, tendo em atenção o grau dos seusvértices?
b) Consegue encontrar algum circuito de Hamilton?
c) Quantos circuitos conseguiu encontrar na questão anterior?



Tarefa 2

Uma empresa internacional vai abrir cinco novas sucursais emcinco cidades portuguesas: Porto, Viseu, Coimbra, Lisboa e Faro.

A empresa pretende colocar a sede nacional numa das cinco cidades e, periodicamente, fazer uma visita às restantes sucursais. Sendolimitado o orçamento, é preciso que tal vistoria seja feita numa única viagem, de modo a que o circuito que parta da sede e passe por todas as sucursais tenha uma quilometragem total mínima.Atendendo às distâncias, em quilómetros, entre cada uma das cidades indicada na tabela seguinte, encontre a solução ótima para o problema proposto.


Porto
Viseu
Coimbra
Lisboa
Faro
Porto
0
133
114332
607
Viseu
133
0
90
308
629
Coimbra
114
90
0
218
493
Lisboa
332
308
218
0
315
Faro
607
629
493
315
0




Tarefa 1

Como organizar a contagem do número de circuitosde Hamilton num grafo completo de 4 vértices - K4?

Consideramos, por exemplo, todos os circuitos que começam no vértice A.

- A partir de A, podemos escolher um dos restantes 3 vértices:


-Para cada um desses, restam ainda duas opções possíveis para qualquer um deles:

-Finalmente regressemos ao vértice A, e o esquema completo de todos os circuitos possíveis será:



Numa primeiraanálise parecem existir 6 circuitos possíveis (3 x 2 x 1 = 6).

Mas são apenas 3 os circuitos distintos, uma vez que os últimos 3 são os mesmos apenas por ordem inversa!!

Se começarmos noutrovértice qualquer, vamos encontrar exatamente os mesmos circuitos!

Note que ABCDA é o mesmo que BCDAB ou CDABC.


Generalizando…

- Num grafo completo k5, teremos circuitos, mas apenas...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • TRABALHO HAMILTON
  • Hamilton Moreira
  • ARTIGO HAMILTON
  • Richard hamilton
  • PETIÇÃO HAMILTON
  • circuitos
  • Circuitos
  • Circuitos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!