Definiçao de Ciclo e de Grafo Hamiltonianos [Raimundo]: Dado G, um ciclo em G é hamiltoniano se percorre todos os vértices de G (ciclo gerador de G). O grafo G é hamiltoniano se contém pelo menos um ciclo hamiltoniano.

Pergunta [Meidanis] Qual é a complexidade computacional de saber se um grafo é hamiltoniano?

Resposta [Meidanis] NP-difícil

Comentário [Meidanis] Diferença entre grafos Euleriano e Hamiltoniano: No primeiro procuramos "percorrer" todas as arestas; no segundo, os vértices.

Condição necessária: Proposição 7.2.3 [Schubert] Se G é hamiltoniano, então para cada S contido em v(G), temos que G-S tem como máximo tantas componentes como vértices em S.

Comentário [Meidanis] Dado que é preciso testar 2ⁿ subconjuntos de G, a condição tem analogias com outras. Por exemplo: Teorema de Tutte, Teorema de Hall (em menor medida)

Definição de Fecho Hamiltoniano [Vagner] C(G) (o fecho de G) é o grafo consistente em acrescentar, iteradamente, novas arestas em G, unindo sempre dois vértices não adjacentes u e v tal que d(u)+d(v)>=n.

Condição suficiente para um grafo Hamiltoniano: Proposição 7.2.11 [Vagner] G é hamiltoniano se e somente se C(G) é hamiltoniano.

Pergunta [Víctor, 31-10] A condição anterior parece ser "suficiente e necessária", isto é, uma caracterização.

Comentário [Meidanis, ante uma pergunta de Vinicius] Existe outra condição suficiente (Teorema de Dirac, 7.2.8). Porém, esta condição pode ser derivada da condiçao 7.2.11, considerando que, se vale :

delta (G)>=n/2, entao o fecho de G é completo.

Pergunta [Cláudio] Existe algum grafo G tal que o fecho de G não coincida com G, e que também o fecho não seja um grafo completo?

Resposta [Luciano] Existe, sendo um exemplo disso a estrela K1,5, com um vértice "v" adjacente a duas folhas de K1,5 somente. O fecho de tal grafo só acrescenta a aresta que une "v" com o centro de K1,5.

Definição Caminho Hamiltoniano [Vinicius]: Caminho em G que percorre todos os vértices de G (caminho gerador de G).

Relaçao entre Caminho e Ciclo Hamiltonianos [Vinicius] G tem caminhos hamiltonianos sse G "junção" K1 tem ciclos hamiltonianos.

Problemas [Sugeridos por Meidanis]

A) E possível resolver a existencia de Caminhos Hamiltonianos em grafos a partir do conhecimento da existencia de Ciclos Hamiltonianos em grafos?

Resposta [Meidanis] Trivial: E suficiente aplicar o teorema anterior, unindo um vértice novo a todos os vértices do grafo G

B) E possível resolver a existencia de Ciclos Hamiltonianos em grafos a partir do conhecimento da existencia de Caminhos Hamiltonianos em grafos?

Resposta [Vinicius-Meidanis] Considerar uma aresta e qualquer de G, com extremos u e v. Construir G’, como o grafo G-e, e com dois vértices "novos": u’, somente unido a u, e v’, somente unido a v. Logo, se G’ tem caminhos hamiltonianos com extremos em u’ e v’, implica que G tem ciclos hamiltonianos usando a aresta e.

Comentário [Meidanis]: A partir da resposta anterior, para responder a B) devemos aplicar o mesmo procedimento em todas as arestas.

Comentário [Vinicius]: Na verdade, é suficiente com aplicar o procedimento em todas as arestas do vértice com menor quantidade de vizinhos! (Pois a existencia de ciclos não depende do "começo" e o "final" do ciclo).

Definição Grafo orientado Estrito [Artur] Grafo orientado sem laços e sem arestas múltiplas com a mesma orientaçao.

Condição sufiente para grafos orientados: Teorema 7.2.22 [Artur] Se mín{delta+(G), delta-(G)}>=n/2, entao G é um grafo orientado hamiltoniano.

Comentário [Evandro] Um grafo orientado hamiltoniano é fortemente conexo.

Ementa extra: Jogo de Hamilton numa representação planar do dodecaedro: Meidanis vs. Alberto: Ganhou Alberto, 1 a 0.

Víctor Fernández

RA: 994992