Trabalho 01 de Algoritmos com Grafos

Adriano de Araújo Abreu Mourão (mourao.aaa at gmail.com)

Tamires Vargas Capanema Franco Santos (tamiresvargas at hotmail.com)

===

Questao 1

Verificar se grafo é completo

.grafo 01 => Completo

.grafo 02 => Não é completo

===

Questao 2

Completar Grafo

.grafo 01 => Já é completo

.grafo 02 => Mostra complemento

Questao 3

Busca em Largura

.grafo 01 => 0 1 2 3 4

.grafo 02 => 0 1 2 4 5 3 6 7

Questao 4

Busca em profundidade

.grafo 01 => 1 2 3 4

.grafo 02 => 0 1 4 5 6 7 2 3

Questao 5

Retornar número de componentes do grafo

.grafo 02 => componentes = 1

.grafo 03 => componentes = 3

Questao 6

Algoritmo de Dijkstra

.grafo 02 => Dijkstra 0-7: 0 1 5 7

.grafo 04 => Dijkstra 0-4: 0 3 4 Dijkstra 0-2: 0 3 1 2

Questao 7

Grafo Hamiltoniano

.grafo 01 => Não hamiltoniano

.grafo 02 => Não hamiltoniano

.grafo 06 => Hamiltoniano

Questao 8

Arvore geradora minima

.grafo 05 => Arvore geradora minima pelo algoritmo de Kruskal