Teoria dos Grafos - Exercícios do Capítulo 8

Michel Alves dos Santos ∗

Junho de 2011

ConteúdoLista de Figuras 1

1 Mostre que, se um grafo G não orientado for euleriano, seu conjunto de arestaspoderá ser particionado em ciclos disjuntos. 1

2 No Exemplo do item 8.4.2, execute o algoritmo de Dijkstra e verifique a cons-trução da matriz de alocação, o resultado do algoritmo húngaro e os caminhosapontados 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 por-que 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 eulerianonão orientado, a partir da construção progressiva de ciclos ao longo de umpercurso 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 Figuras1 Grafo de Petersen. Sua sequência gráfica é (3,3,3,3,3,3,3,3,3,3). . . . . . . . . . . . 22 Verificação de ciclos hamiltonianos. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1 Mostre que, se um grafo G não orientado for euleriano,seu conjunto de arestas poderá ser particionado em ciclosdisjuntos.

Seja G um grafo euleriano. O caso em que G não possui arestas é trivial. Sendo G conexoe tendo pelo menos uma aresta, todo o seu vértice tem, pelo menos, grau 2. Portanto, peloTeorema 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: mi-chel.mas@gmail.com, michelalavessantos@hotmail.com. Disciplina: Teoria dos Grafos. Docente Responsável: Leo-nardo Viana Pereira.

1

gerador G1 cujos vértices têm ainda todos grau par. Se G1 não tem arestas, está terminada ademonstração desta implicação. Caso contrário, G1 tem um ciclo C2 e a repetição do argumentoanterior conduz-nos a um grafo G2, subgrafo gerador de G1, cujos vértices têm grau par. Se G2 nãotem arestas terminamos, caso contrário repete-se o argumento. E continuamos com este raciocíniosucessivamente até obtermos um grafo Gn totalmente desconexo (isto é, sem arestas). Aí teremosuma partição das arestas de G em n ciclos.

2 No Exemplo do item 8.4.2, execute o algoritmo de Dijks-tra e verifique a construção da matriz de alocação, o re-sultado do algoritmo húngaro e os caminhos apontadospelo vetor ‘Anterior’ acompanhando-os no grafo.

Para execução do algoritmo de Dijkstra a partir do vértice com rótulo ‘01’ teremos o seguintecenário:

[Vértice] [01] [02] [03] [04] [05] [06] [07] [08] [09] [10][Distâncias][0] [85] [inf] [460] [195] [220] [inf] [370] [285] [320][Anterior] [-] [01] [01] [08] [02] [02] [01] [09] [05] [05]

[Vértice] [11] [12] [13] [14] [15][Distâncias] [inf] [inf] [435] [inf] [inf][Anterior] [01] [01] [09] [01] [01]

Podemos observar que partindo do primeiro vértice encontraremos algumas regiões onde ocorrerão‘loopings’, que podem ser chamados de caminhos de repetição. Note que nessa primeira iteraçãotomando como origem o vértice ‘01’ não conseguiremos alcançar todos os vértices, por isso atabela de distâncias indicará distância infinita(inf). Outros caminhos de repetição, que poderamser notados no grafo fornecido, são: (02, 05, 09), (06, 03, 02, 05, 09), (08, 04), (15, 11) e (15, 11,07, 08, 05, 10, 14).

3 Construa uma sequência de De Brujin B(2,3).

B(2,3): 11101000

4 Mostre que o gráfico de Petersen(figura 1) é não hamilto-niano. Explique porque as condições suficientes expostasno capítulo não se aplicam a ele.(Dica: Aproveite a sime-tria do grafo).

Figura 1: Grafo de Petersen. Sua sequência gráfica é (3,3,3,3,3,3,3,3,3,3).

O grafo de Petersen é um tipo de grafo de Moore. Este grafo tem grande importância teórica,por diversos motivos; em particular além de ser um grafo de Moore, ele tem cintura 5, é não

2

Hamiltoniano e não planar. O grafo de Petersen tem a pecualiaridade de ser contra exemplo paranumerosas conjecturas em diferentes temas da teoria dos grafos. Vale a pena registrar que o grafode Petersen é uma gaiola(grafo regular de cintura dada, com número mínimo de vértices). Umagaiola é denotada por seus parâmetros como c(d,g) (c = cage).

Porém a sequência de graus do grafo de Petersen não é forçosamente hamiltoniana. Umsequência forçosamente hamiltoniana é aquela para qual todas as representações gráficas(conexas)são grafos hamiltonianos. Uma sequência gráfica é uma sequência finita não descrescente, deinteiros positivos, que tenha uma correspondência biunívoca com a sequência dos graus dos vérticesde um grafo não orientado G. G é então uma representação gráfica da sequência.

5 Construa um algoritmo para achar um ciclo euleriano emum grafo euleriano não orientado, a partir da construçãoprogressiva de ciclos ao longo de um percurso inicial.

grau = 0;soma = 0;matrizAdjacencias[][];N = NumeroDeLinhas(matrizAdjacencias[][]);i = 0; //i é a linha atual

Enquanto ((soma <= 2) e ( i<= N)){

grau = 0;Para( j=0; j < N; j++) grau = grau + matrizAdjacencias[i][j];Se (grau mod 2 == 1) soma ++; //caso seja ímpari++;

}

Se (soma > 2) Escreve ‘CAMINHO NÃO EXISTENTE’Senão Escreve ‘CAMINHO EXISTENTE’

6 Verifique se os grafos a seguir(figura 2) são hamiltonianosou não-hamiltonianos, justificando a resposta(Dica: Umdeles é hamiltoniano e o outro não).

Figura 2: Verificação de ciclos hamiltonianos.

O primeiro grafo é hamiltoniano porque podemos passar uma única vez por cada vértice. Jáo segundo grafo, não é hamiltoniano porque não podemos encontrar um caminho hamiltoniano.Sempre faz-se necessário passar mais de uma vez por um vértice.

3