Teoria dos Grafos

Teoria dos Grafos - Exercícios do Capítulo 8
Michel Alves dos Santos

∗

Junho de 2011

Conteúdo
Lista de Figuras

1

1 Mostre que, se um grafo G não orientado for euleriano, seu conjunto de arestas poderá ser particionado em ciclos disjuntos.
1
2 No Exemplo do item 8.4.2, execute o algoritmo de Dijkstra e verifique a construção da matriz de alocação, o resultado do algoritmo húngaro e os caminhos apontados pelo vetor ‘Anterior’ acompanhando-os no grafo.
2
3 Construa uma sequência de De Brujin B(2,3).

2

4 Mostre que o gráfico de Petersen(figura 1) é não hamiltoniano. Explique porque as condições suficientes expostas no capítulo não se aplicam a ele.(Dica:
Aproveite a simetria do grafo).
2
5 Construa um algoritmo para achar um ciclo euleriano em um grafo euleriano não orientado, a partir da construção progressiva de ciclos ao longo de um percurso inicial.
3
6 Verifique se os grafos a seguir(figura 2) são hamiltonianos ou não-hamiltonianos, justificando a resposta(Dica: Um deles é hamiltoniano e o outro não).
3

Lista de Figuras
1
2

1

Grafo de Petersen. Sua sequência gráfica é (3,3,3,3,3,3,3,3,3,3). . . . . . . . . . . .
Verificação de ciclos hamiltonianos. . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
3

Mostre que, se um grafo G não orientado for euleriano, seu conjunto de arestas poderá ser particionado em ciclos disjuntos. Seja G um grafo euleriano. O caso em que G não possui arestas é trivial. Sendo G conexo e tendo pelo menos uma aresta, todo o seu vértice tem, pelo menos, grau 2. Portanto, pelo
Teorema de Euler, possui um ciclo C1 . Retirando de G as arestas de C1 obtemos um subgrafo
∗ Bacharelando

em Ciência da Computação, Universidade Federal do Estado de Alagoas(UFAL). E-mails: [e-mail], [e-mail]. Disciplina: Teoria dos Grafos. Docente Responsável: Leonardo Viana Pereira.

1

gerador G1 cujos vértices têm ainda todos grau par. Se G1 não tem arestas, está