teoria dos grafos

Prévia do material em texto

Teoria dos Grafos – Módulo 4 – pág. 1 
Teoria dos Grafos 
Módulo 4 
Lista de adjacências de um grafo. 
Caminhos de Euler. 
Circuito de Hamilton (circuito hamiltoniano). 
 
1. Lista de adjacências de um grafo 
 
Lista de adjacência de um grafo é um arranjo de ponteiros, um para cada nó. O ponteiro 
de cada nó ou vértice aponta para o nós vizinhos. No exemplo abaixo é apresentada a 
lista de adjacência de um grafo. 
 
Grafo Lista de adjacência Processo de construção da lista 
 
Do vértice 1 parte uma aresta para o 
vértice 1 (laço), do vértice 1 parte outra 
para vértice 2 e outra para o vértice 4, 
sendo assim finalizada a lista do vértice 
1 com um ponto. O processo é repetido 
para os outros vértices. 
 
2. Caminhos de Euler 
 
Caminho de Euler de um grafo é um caminho passando uma única vez por cada aresta 
do grafo (percorrendo todas as arestas do grafo). Todos os grafos que admitem um 
caminho de Euler são chamados de grafos de Euler. 
Define-se um caminho de Euler como sendo um caminho fechado passando uma única 
vez por cada aresta do grafo (percorrendo todas as arestas do grafo). Todos os grafos 
que admitem um caminho de Euler são chamados de grafos de Euler. 
 
Um grafo conexo G (simples, não orientado) é um grafo de Euler se e somente se todos 
os seus vértices são de grau par ou se existirem apenas 2 vértices com grau impar. No 
caso em que todos os vértices têm grau par o caminho pode começar em qualquer 
vértice e terminar nele mesmo. No caso de grafo com apenas 2 vértices de grau ímpar o 
caminho deve começar num deles e terminar no outro. 
 
Um dígrafo G (grafo orientado) contém um circuito de Euler se e somente se os graus de 
entrada e saída de cada vértice forem iguais. 
 
3. Circuito de Hamilton 
É o circuito em todos os vértices são visitados apenas uma vez não sendo necessário 
passar por todas as arestas. Os grafos que possui circuito de Hamilton são chamados de 
Hamilton. Não existem regras práticas para descobrir se um grafo é de Hamilton. Sua 
descoberta é feita por tentativa e erro. Exemplo: 
 
Grafo de Hamilton Circuito de Hamilton 
 
 
 
 
 
Teoria dos Grafos – Módulo 4 – pág. 2 
Exemplo 1 - módulo 4 – teoria dos grafos. 
Monte a lista de adjacência do grafo abaixo: 
 
Solução: O grafo é direcionado. Do vértice 1 partem arcos para os 
vértice 1 e 2, do vértice 2 partem arcos para os vértices 3 e 4, do vértice 
3 parte um arco para o vértice 2 e do vértice 4 parte um arco para o 
vértice 3. Então a lista da adjacência é: 
 
 
 
Exemplo 2 - módulo 4 – teoria dos grafos. 
Verifique se o grafo ao lado é um grafo de Euler. Justifique. 
 
Solução: O grafo é direcionado. Para que seja um grafo de Euler é 
necessário que graus de entrada e saída de cada vértice sejam iguais. O 
vértice 1 possui grau saída = 2 e grau de entrada = 1. Portanto o grafo não 
é um grafo de Euler. 
 
Exemplo 3 - módulo 4 – teoria dos grafos. 
Faça a lista de adjacência de grafo completo de 4 vértices (K4) 
Solução: Desenhando o grafo K4 e seguindo o raciocínio do exemplo 1 temos: 
 
 
 
 
 
Exemplo 4 - módulo 4 – teoria dos grafos. 
O grafo abaixo o grafo chamado de K5. Verifique se o K5 é um grafo de Euler. Justifique. 
Se o K5 for um grafo de Euler escreva um caminho de Euler. 
 
Solução: O K5 é um grafo de Euler porque o grau de todos os vértices é par (grau = 4). O 
caminho Euler é um percurso passando por todas as arestas sem haver repetição de 
arestas. Escolhendo o vértice 1 como início temos o seguinte caminho de Euler: 
1;2;3;4;5;1;4;2;5;3;1. Existem outros caminho de Euler neste grafo. 
 
Exercícios propostos 
1) Escreva a lista de adjacência do grafo K5 
 
 
 
 
Teoria dos Grafos – Módulo 4 – pág. 3 
2) Dos grafos abaixo, quais são grafos de Euler? 
 
 (A) (B) (C) (D) 
 
 
3) Dos grafos abaixo, quais são grafos de Hamilton? 
 
 (A) (B) (C) (D) 
 
4) Desenhe o grafo que possui a seguinte lista de adjacência: 
 
 
5) Temos a lista de adjacência de um grafo. Este grafo é um grafo de Euler? Justifique. 
 
6) O grafo K5 é um grafo de Euler? Justifique 
 
 
7) O grafo K5 é um grafo de Hamilton? Justifique