GrafosHamiltonianos

Matemática Discreta – if670
Anjolina Grisi de Oliveira
Ciência da Computação
Colaboração: lnpa e ljacs

Teoria dos Grafos
Caminhos e Noção de Grafos com pesos

Caminhos e Isomorfismo


A existência de circuitos simples com um tamanho n é uma invariante.

Caminhos e Isomorfismo


Além disso, caminhos podem ser usados para construir mapeamentos, que podem ser isomorfismos. Caminho 1: u1, u4, u3, u2, u5 Caminho 2: v3, v2, v1, v5, v4

Cortando caminhos entre vértices


Teorema:
– Seja G um grafo cuja matriz de adjacência A usa a seguinte ordem nos vértices: v1, v2, …, vn. A quantidade de caminhos diferentes de tamanho r de vi para vj, onde r é um inteiro positivo é igual a ai,j entrada da matriz Ar . a,b,a,b,d a,b,a,c,d a,b,d,b,d a,b,d,c,d a,c,a,b,d a,c,a,c,d a,c,d,b,d a,c,d,c,d

Circuito Euleriano


Um circuito euleriano em um grafo G é um circuito simples que contem cada aresta de G.

Teorema (Euler 1736)
Um multigrafo conectado G possui um circuito euleriano se e somente se o grau de cada vértice de G é par.


Prova
– Ida: Seja G um grafo euleriano. Por cada

ocorrência de vértice do circuito euleriano, existe uma aresta que chega nesse vértice e outra que sai desse vértice. Como toda aresta faz parte do circuito, isto é, nenhuma aresta fica fora do ciclo, necessariamente o número de arestas por cada vértice é par.

– Volta: Suponhamos que todos os vértices possuem

grau par. Seja vi um vértice do grafo. Tentemos, a partir de vi, construir um caminho que não passa duas vezes pela mesma aresta, e até que não seja possível continuar. Como todos os vértices possuem um grau par, sempre será possível entrar e sair de um vértice. A única exceção é o vértice vi onde o caminho vai terminar. Se esse caminho, que chamaremos C1, contém todas as arestas de
G, temos um ciclo euleriano. Senão, retiramos de
G todas as arestas que fazem parte de C1. No grafo resultante G', todos os vértices também possuem grau par e necessariamente um deles faz parte de C1, senão o