APOSTILA DE TEORIA DOS GRAFOS E ANÁLISE DE ALGORITMOS - Profa. Camilla Brandel Martins

Prévia do material em texto

Faculdade de Filosofia, Ciências e Letras de Mandaguari 
Departamento de Informática 
 
 
 
 
 
 
 
 
 
 
 
 
APOSTILA DA DISCIPLINA 
ANÁLISE DE ALGORITMOS 
 
Profa. Camilla Brandel Martins 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Mandaguari, 2004
Faculdade de Filosofia, Ciências e Letras de Mandaguari 2 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
Ementa da Disciplina 
Estudo de conceitos e análise da complexidade de algoritmos. 
 
 
Programa: 
 
1. Introdução 
 1.1 Objetivo da Disciplina 
 1.2 Medidas de Desempenho de Algoritmos 
2. Teoria dos Grafos 
 2.1. Introdução 
 2.2. Sucessores e Antecessores de um Grafo Dirigido 
 2.3. Representação de Grafos em um Computador 
 2.4. Caminho e Conexidade 
 2.5. Localização de Centros 
 2.6. Algoritmos e problemas clássicos com grafos 
 2.7. Busca em Grafos 
 2.8. Fluxo em rede 
3.Complexidade de Algoritmos 
 3.1.Definições 
 3.2. Notação O, Omega e Theta 
 3.3. Crescimento assintótico de funções 
4. Análise da Complexidade de Algoritmos 
 4.1 Estimativas de Tempo de Execução 
 4.2. Regras para Análise de Algoritmos 
 4.3. Relações de recorrência 
5. Técnicas de Projeto de Algoritmos 
 5.1 Algoritmos de Ordenação 
 5.1.1 Algoritmos de Ordenação por inserção 
 5.1.2 Algoritmos de Ordenação por seleção 
 5.1.3 Algoritmos de Ordenação por troca 
 5.2 Algoritmo da Força Bruta 
 5.3 Algoritmo Minmax 
 5.4 Algoritmo dividir e conquistar 
 5.5 Algoritmo Guloso 
6. Teoria da Complexidade 
 6.1. Tipos de Problemas 
 6.2. Classes de Problemas 
 6.2.1. Problemas P, NP e NP-Completos 
 
Previsão de Avaliações: 
1
o
. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0 
2
o
. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0 
3
o
. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0 
4
o
. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0 
 
 
 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 3 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
ÍNDICE 
 
1 INTRODUÇÃO ................................................................................................................................ 5 
1.1 OBJETIVO DA DISCIPLINA ........................................................................................................... 5 
1.2 MEDIDAS DE DESEMPENHO DE ALGORITMOS .............................................................................. 5 
2 TEORIA DOS GRAFOS .................................................................................................................. 7 
2.1 INTRODUÇÃO ............................................................................................................................. 7 
2.1.1 Representação Gráfica ......................................................................................................... 8 
2.1.2 Representação Matemática ................................................................................................... 8 
2.1.3 Definições Básicas ................................................................................................................ 8 
2.1.4 Tipos de Grafos .................................................................................................................... 9 
2.2 SUCESSORES E ANTECESSORES DE UM GRAFO DIRIGIDO ............................................................ 12 
2.3 REPRESENTAÇÃO DE GRAFOS EM UM COMPUTADOR .................................................................. 12 
2.3.1 Matriz de Adjacência .......................................................................................................... 12 
2.3.2 Matriz de Custo .................................................................................................................. 13 
2.3.3 Matriz de Incidência ........................................................................................................... 13 
2.3.4 Lista de Arestas .................................................................................................................. 14 
2.3.5 Estrutura de Adjacência ...................................................................................................... 14 
2.4 CAMINHO E CONEXIDADE ........................................................................................................ 15 
2.4.1 Caminho ............................................................................................................................. 15 
2.4.2 Cadeia ................................................................................................................................ 15 
2.4.3 Comprimento ...................................................................................................................... 15 
2.4.4 Caminho Simples x Trajetória ............................................................................................. 16 
2.4.5 Grafo Conexo ..................................................................................................................... 16 
2.4.6 Caminhos abertos e fechados .............................................................................................. 16 
2.4.7 Circuito e Ciclo .................................................................................................................. 16 
2.4.8 Algoritmo de Goodman ....................................................................................................... 17 
2.5 LOCALIZAÇÃO DE CENTROS (EM GRAFOS NÃO VALORADOS) ...................................................... 18 
2.5.1 Distância ............................................................................................................................ 18 
2.5.2 Pista ................................................................................................................................... 19 
2.5.3 Excentricidade .................................................................................................................... 19 
2.5.4 Raio ................................................................................................................................... 19 
2.5.5 Centro ................................................................................................................................ 19 
2.5.6 Centro de um grafo dirigido ................................................................................................ 20 
2.5.7 Localização de Centros de Emergência ............................................................................... 20 
2.6 ALGORITMOS E PROBLEMAS CLÁSSICOS COM GRAFOS ................................................................ 23 
2.6.1 Algoritmo de Floyd ............................................................................................................. 23 
2.6.2 Algoritmo de Dijkstra ......................................................................................................... 28 
2.6.3 Grafos de Euler .................................................................................................................. 30 
2.6.4 Problema do Carteiro Chinês.............................................................................................. 30 
2.6.5 Caminho e Circuito Hamiltoniano....................................................................................... 34 
2.6.6 Problema do Caixeiro Viajante ........................................................................................... 34 
2.7 BUSCA EM GRAFO .................................................................................................................... 44 
2.7.1 Algoritmo Básico ou Busca Geral .......................................................................................44 
2.7.2 Busca em Profundidade ...................................................................................................... 46 
2.7.3 Busca em Largura .............................................................................................................. 49 
2.8 FLUXO EM REDE ...................................................................................................................... 53 
3 EFICIÊNCIA E CORRETUDE DE ALGORITMOS ................................................................... 54 
3.1 DEFINIÇÕES ............................................................................................................................. 54 
3.1.1 O que é um algoritmo?........................................................................................................ 54 
3.1.2 Instâncias de execução de algoritmos .................................................................................. 55 
3.1.3 Avaliação de Algoritmos ..................................................................................................... 55 
3.2 NOTAÇÃO O, OMEGA E THETA ................................................................................................. 57 
3.2.1 Notação O .......................................................................................................................... 57 
3.3 CRESCIMENTO ASSINTÓTICO DE FUNÇÕES ................................................................................. 59 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 4 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
4 ANÁLISE DA COMPLEXIDADE DE ALGORITMOS ............................................................... 60 
4.1 ESTIMATIVAS DE TEMPO DE EXECUÇÃO .................................................................................... 60 
4.2 REGRAS PARA ANÁLISE DE ALGORITMOS .................................................................................. 60 
4.3 RELAÇÕES DE RECORRÊNCIA .................................................. ERRO! INDICADOR NÃO DEFINIDO. 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 5 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
1 Introdução 
 
1.1 Objetivo da Disciplina 
Nesta altura do curso, a maioria dos alunos já deve ter compreendido que o 
desenvolvimento de algoritmos é uma atividade fundamental da computação. Assim, esta é 
mais uma disciplina que irá ajudá-lo a aprimorar suas habilidades de programação. 
Nas disciplinas de engenharia de software, aprende-se vários métodos e 
procedimentos que devem ser adotados para produzir um software eficiente e de qualidade, 
utilizando o menor tempo possível e a menor quantidade possível de recursos. A disciplina 
Análise de Algoritmos está, portanto, relacionada com a engenharia de software, pois um 
de seus objetivos é a produção de softwares eficientes. A diferença é que a engenharia se 
preocupa com diversos aspectos do software, como o paradigma utilizado, qual é a melhor 
linguagem de preocupação, como montar uma equipe de programadores, etc. Já a análise 
de algoritmos se preocupa unicamente com uma atividade: a codificação. 
 Assim, o objetivo final desta disciplina é fazer com que os alunos produzam não 
apenas códigos que funcionem, mas que sejam também eficientes. Para isso, vamos 
estudar alguns tipos de problemas que podem ser resolvidos computacionalmente. Em 
seguida, vamos ver como a abordagem adotada para resolver pode influenciar, levando a 
um algoritmo mais ou menos eficiente. 
Em longo prazo, espera-se que o aluno consiga naturalmente compreender quais 
estruturas e técnicas são mais adequadas para cada problema e as utilize de forma a 
produzir programas o mais eficientes possível. 
 
"Ao verificar que um dado programa está muito lento, 
uma pessoa prática pede uma máquina mais rápida ao seu chefe. 
Mas o ganho potencial que uma máquina mais rápida pode proporcionar 
é tipicamente limitado por um fator de 10, por razões técnicas ou econômicas. 
Para obter um ganho maior, é preciso buscar melhores algoritmos. 
Um bom algoritmo, mesmo rodando em uma máquina lenta, 
sempre acaba derrotando (para instâncias grandes do problema) 
um algoritmo pior rodando em uma máquina rápida. Sempre." 
 
- S. S. Skiena, The Algorithm Design Manual 
1.2 Medidas de Desempenho de Algoritmos 
Uma possível definição para algoritmo é a de que um algoritmo é um método para 
resolver uma classe de problemas utilizando um computador. A complexidade de um 
algoritmo seria então o custo de se utilizar o algoritmo para resolver um desses problemas, 
sendo que custo pode ser medido em tempo de processamento, armazenamento, ou 
outra unidade de medida (Wilf, 1994). 
Os programas utilizados nos computadores domésticos geralmente executam 
rapidamente. Mas quem já compilou um grande programa sabe que o tempo gasto nessa 
atividade pode ser bastante longo. Quem já tentou fazer um programa para calcular o valor 
de pi () sabe que atualmente essa é uma tarefa impossível. O estudo do montante de 
esforço computacional necessário para executar alguma computação é chamado de estudo 
da complexidade. 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 6 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
Um dos fatores que influencia o tempo de processamento é o volume de dados. Não 
é difícil perceber que calcular a soma de 2 números é mais rápido do que fazer a soma de 
2000 números. Assim, uma das medidas para se verificar a complexidade de um algoritmo 
é o tempo de execução em relação ao volume de dados. 
Por exemplo, suponha que você escreveu um pequeno programa que pede ao 
usuário para digitar quantos nomes ele quiser. Em seguida, o programa apresenta os nomes 
em ordem alfabética. Ao executar o programa e digitar 100 nomes, você percebe que o 
programa demorou 1 segundo. Ao digitar 1000 nomes, você percebe que ele demorou 9 
segundos (quando, por uma regra de 3 simples, você pudesse achar que ele iria demorar 10 
segundos). O que isso quer dizer? 
Bom, isso quer dizer que não é assim tão simples prever quanto tempo o programa 
demorará para executar quando você utilizar grandes volumes de dados. Assim, para que 
possamos prever o seu comportamento com grandes volumes, é preciso analisar o 
algoritmo e fazer alguns cálculos. 
Para aprender a fazer esses cálculos, naturalmente tomaremos alguns problemas 
computacionais como exemplo. E como vários dos problemas clássicos da computação 
envolvem o uso de grafos, iniciaremos o curso estudando teoria dos grafos. 
 
 
 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 7 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
2 Teoria dos Grafos 
2.1 Introdução 
Os grafos, ou problema em grafos, são estudados há muitos anos. Já em 1736, Euler 
descreveu o seguinte problema: Dada a configuração abaixo
1
, tendo um rio com duas ilhas, 
duas margens e 7 pontes, é possível passar por todas as pontes sem repetir nenhuma? 
Como provar? 
 
Para resolver esse problema, Euler o representou com o grafo ilustrado na Figura 1. 
Com essa representação, e considerando as propriedades do grafos que serão apresentadas 
mais tarde nesse curso, é possível resolver facilmente esse problema. 
 
 
Figura 1 . Representação gráfica do problema de Euler 
 
Esse tem sido considerado o primeiro problema do que hoje chamamos de teoria 
dos grafos. No entanto, até o fim do século 19 houve poucos trabalhos na área. Por 
exemplo, em 1847, Kirchhoff utilizou modelos de grafos no estudo de circuitos elétricos. 
Em 1857, Cayley utilizou grafos na química orgânica. Em 1859, Hamilton inventou um 
jogo que consistia na busca de um percurso fechado envolvendo todos os vértices de um 
dodecaedroregular, de tal modo que cada um deles fosse visitado uma única vez. Para 
mais exemplos, consulte, por exemplo, Boaventura Neto, 1996. 
 
1 Figura retirada do site http://www.inf.ufpr.br/~andre/Disciplinas/BSc/CI065/michel/Intro/intro.html 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 8 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
2.1.1 Representação Gráfica 
Visualmente, os grafos são representados por um conjunto de pontos e um conjunto 
de linhas ou setas ligando esses pontos. Exemplos: 
 
 
 
 
 
 
 
 
 
2.1.2 Representação Matemática 
Um grafo G é definido como G(V,A) onde V é um conjunto finito e não vazio de 
vértices e A um conjunto finito de pares de V, isto é, A  (VxV). Os elementos de A são 
chamados de arestas do grafo. 
 
2.1.3 Definições Básicas 
 Laço – uma aresta que incide com um único vértice é chamada de laço. 
 Orientação – é a direção para a qual uma seta aponta. Se a aresta não tiver seta, diz-se 
que ela não tem orientação 
 Incidente – Diz-se que uma aresta é incidente com os vértices que ela liga (não importa 
a orientação). 
 Vértices Adjacentes – dois vértices são adjacentes se estão ligados por uma aresta. 
 Vértice isolado – Um vértice é dito isolado se não existe aresta incidente sobre ele. 
 Arestas paralelas – Duas arestas incidentes nos mesmos vértices (não importa a 
orientação). Ou seja, se a1 = (v,w) e a2 = (v,w), então as arestas a1 e a2 são paralelas. 
 
 
 
 
 
 
 Laço no vértice A A aresta a3 incide no vértice C e no vértice D. 
 
Os vértices A e B são adjacentes. os vértices C e D também são adjacentes. 
 
 
 
 
 
 
 
 Vértice E isolado. As arestas a1 e a2 são paralelas 
 
 
 
 
 E 
 
 a3 
 
C D 
Vértices – são os “pontos”, ou nós 
Arestas – são as linhas ou setas, ou arcos. 
 
 
 
 A B 
 
 
 
 
v1 v2 
a1 
a2 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 9 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
2.1.4 Tipos de Grafos 
 
2.1.4.1 Grafo Rotulado 
Um grafo é dito rotulado quando seus vértices e/ou arestas são distinguidos uns dos 
outros por rótulos (que pode ser um nome, um número ou conjunto de letras ou números. 
Caso contrário o grafo é não rotulado. 
Nos exemplos abaixo, o primeiro grafo não tem nenhum rótulo. O segundo grafo 
possui rótulos nos vértices e o terceiro grafo possui rótulos nas arestas. 
 
 x1 
 a1 a2 
 
 x2 x3 
 
Grafo não rotulado Grafo rotulado Grafo rotulado 
 
 
Exemplo 1 – Represente graficamente um grafo definido matematicamente como 
segue: Grafo G(V,A), onde V = {v1,v2,v3,v4} e A = {(v1,v2),(v2,v3),(v3,v3),(v3,v1)}. 
 
Há varias formas gráficas semelhantes de se representar esse grafo, mantendo as 
definições, pois a posição dos vértices no espaço é irrelevante. Vou fazer de duas formas 
diferentes. 
 
 v1 v4 
 
 
 v2 v3 
 
 
 
2.1.4.2 Subgrafos 
Seja G(V,A) um grafo. Um subgrafo G’ de G é um grafo G’(V’,A’), tal que V’ V 
e A’ A. 
 
 
 
 
 
 
 
 Grafo G Grafo G’ 
 
2.1.4.3 Ordem 
A ordem de um grafo é definida por |V| = n. Ou seja, a ordem de um grafo é o número de 
vértices. 
 
 
v1 v2 
v3 
v4 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 10 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
2.1.4.4 Grafos simples, completos e multígrafos 
 Multígrafo – grafo que contém arestas paralelas ou aços 
 Grafo simples – grafo que não contém nenhum par de arestas paralelas ou laços. 
 Grafo completo – um grafo simples será completo quando existir uma aresta entre 
cada par de seus vértices. 
 Exemplos de grafos completos de 2, 3 e 4 vértices: 
 
 
 
 
 
 
 n 
 Um grafo completo com n vértices possui m = 2 arestas ou (n-1)! 
 Um grafo completo de n vértices é denominado cliques. 
 
2.1.4.5 Grafo Complementar 
Um grafo G é dito complementar de G se possui a mesma ordem de G e se uma aresta 
(v,w)  G, então (v,w)  G e vice-versa. Exemplo: 
 
 Grafo G Grafo G 
 a a 
 
 b d b d 
 
 c c 
 
 
No caso de grafos dirigidos, o grafo complementar G será aquele que possui os 
mesmos vértices de G, possui todas as arestas não presentes em G e possui o reverso das 
arestas de G. Por exemplo: 
 
 Grafo G Grafo G 
 a a 
 
 b d b d 
 
 c 
 c 
 
 
 
2.1.4.6 Grafo Bipartite 
Se G(V1  V2,A) é tal que, para V1  V2 =  e para toda aresta (vi,vj)  A, tem-se que 
vi  V1 e vj  V2, então o grafo é denominado bipartite. 
Ou seja, o grafo pode ser dividido logicamente em dois conjuntos de vértices, tal que toda 
aresta começa no vértice de um dos conjuntos e termina no vértice do outro conjunto. 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 11 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
 V1 = {a.,b} 
 a c V2 = {c,d,e} 
 
 d 
 
 
 b e 
 
2.1.4.7 Grafo Dirigido 
Um grafo é chamado de dirigido (ou dígrafo) se suas arestas possuem orientação. 
Caso contrário o grafo é não dirigido. Em termos leigos: será dirigido se suas arestas forem 
“flechas” que apontam o vértice inicial e final de cada aresta. 
 
2.1.4.8 Grafos Isomorfos 
Dois grafos são isomorfos se coincidirem os vértices de suas representações 
gráficas, preservando as adjacências das arestas. Em outras palavras, são isomorfos se têm 
a mesma representação matemática, mas são representados diferentemente graficamente. 
Formalmente pode-se dizer que G1(V1,A1) e G2(V2,A2) são isomorfos se 
satisfizerem as seguintes condições: 
1) |V1| = |V2| = n. 
2) Existe uma função bijetora f: V1 V2, tal que (v,w)  A1  ((f(v),f(w))  A2  v,w 
 V1. 
 
a a’ a 
 
 a’ 
 b b’ 
 
 
 c c’ c’ b 
 
 c b’ 
 
2.1.4.9 Grau e Grafos Regulares 
 O grau de um vértice v  V denotado por gr(v) = número de arestas incidentes a v 
(sendo que um laço equivale a duas arestas). 
 Um grafo é dito regular de grau r se todos os vértices possuem grau r. Ou seja, todos 
os vértices possuem o mesmo grau. 
 Teorema 1 – A soma dos graus dos vértices de um grafo é igual a duas vezes o número 
de arestas. 
 Teorema 2 – Em qualquer grafo existe sempre um número par de vértices de grau 
ímpar. 
 
2.1.4.10 Grafo Valorado 
Seja pi um número associado a cada aresta e qj um número associado a cada vértice 
de um grafo G(V,A). Então G é denominado de grafo valorado e o número pi é chamado 
de custo da aresta e o número qj é chamado de custo do vértice. 
Custo da aresta pode significar distância, altitude, capacidade, fluxo etc. 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 12 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
Custo do vértice pode significar capacidade, entradas, etc. 
 
 10km8km 16km 
 
 
2.2 Sucessores e Antecessores de um Grafo Dirigido 
Formalmente, os vértices sucessores e antecessores de um grafo dirigido são 
definidos da seguinte forma: 
 v é sucessor de w <=> (w,v)  A 
 v é antecessor de w <=> (v,w)  A 
Os conjuntos de todos os vértices sucessores e antecessores de um dos vértices de 
um grafo são formalmente definidos da seguinte forma: 
 +(v) = {w/(v,w)  A --> conjunto de sucessores de v 
 -(v) = {w/(w,v)  A --> conjunto de antecessores de v 
Exemplo: 
 b 
 
 
 a d 
 
 c 
 
+(a) = {b,c} +(b) = {c} +(c) = {d} +(d) = { } 
-(a) = { } -(b) = {a} -(c) = {a,b} -(d) = {c} 
 
2.3 Representação de Grafos em um Computador 
Para que um grafo seja armazenado em um computador, é necessário definir dois aspectos: 
 Quais informações devem ser consideradas 
 Como armazenar as informações no computador, ou seja, definir a estrutura de 
dados que será utilizada. 
A estrutura de dados é particularmente importante, pois a eficiência de um 
algoritmo que irá trabalhar sobre o grafo vai depender da escolha certa de como representar 
o grafo. 
De uma forma geral, pode-se representar um grafo utilizando matrizes ou listas, 
como veremos a seguir. 
 
2.3.1 Matriz de Adjacência 
Dado um grafo G(V,A), a matriz de adjacência A = [aij] é uma matriz n x n tal que 
aij = 1 se e somente se existe (vi, vj)  Aj 
 0 caso contrário 
Exemplo: 
 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 13 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
 
 a2 a4 
 
 
 a1 a3 
 
 
 a2 a3 
 
 
 
a1 a4 
 
 
 
 b c 
 
 
 
 a d 
 
 1 2 3 4 
1 0 1 0 0 
2 1 0 1 1 
3 0 1 0 1 
4 0 1 1 0 
 
 j 
 1 2 3 4 
 1 1 1 0 0 
i 2 0 0 1 0 
 3 0 0 0 1 
 4 0 1 0 0 
 
 
 j 
 1 2 3 4 
 1 0 2 0 0 
i 2 0 0 1 0 
 3 0 0 0 1 
 4 0 1 0 0 
 
2.3.2 Matriz de Custo 
Um grafo valorado pode ser representado por uma matriz de custo w = {wij}, onde 
wij = custo da aresta, se (vi, vj)  A 
  caso (vi, vj)  A (ou seja, caso não exista aresta) 
 
Exemplo: 
 
 a2 2 a3 
 
 1 8 
 5 
 
 a1 a4 
 
 j 
 1 2 3 4 
 1  1   
i 2 1  2 5 
 3  2  8 
 4  5 8  
 
2.3.3 Matriz de Incidência 
Dado um grafo G(V,A) de n vértices e m arestas a matriz de incidência de G é denotada 
por B = [bij] é uma matriz n x m definida por: 
bij = 1 se vi é vértice de aj 
 0 caso contrário 
 
 
 
 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 14 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
Se o grafo G for orientado (dígrafo), então poderá ser definida como: 
 
 1 se vi for vértice inicial de aj (ou se existir um laço no vértice vi) 
bij = -1 se vi for vértice final de aj 
 0 se o vértice vi não pertence à aresta aj 
 
 
Exemplo: 
 
 2 b 3 
 
 a c 
 d 
 
 1 4 
 
 e 
 
 1 a 2 b 3 
 
 
 d c 
 
 4
 
 arestas 
 a b c d e 
 1 1 0 0 0 1 
 2 1 1 0 1 0 
vértices 3 0 1 1 0 0 
 4 0 0 1 1 0 
 
 
 arestas 
 a b c d 
 1 1 0 0 0 
 2 -1 1 0 -1 
vértices 3 0 -1 1 0 
 4 0 0 -1 1 
 
2.3.4 Lista de Arestas 
Pode-se representar um grafo em um computador utilizando-se duas listas de vértices, 
representando as arestas do grafo. As listas podem ser vetores simples. 
A primeira lista contém os vértices de início de cada aresta. 
A segunda lista contém os vértices onde cada uma delas termina. Por exemplo: 
 
 v2 v3 
 
 v5 L1 = (v2,v3,v3,v4,v5,v5) 
 L2 = (v1,v2,v5,v3,v2,v4) 
v1 v4 
 
2.3.5 Estrutura de Adjacência 
Um grafo pode ser representado por uma lista de vértices e, para cada vértice da lista, é 
associada uma lista dos seus respectivos sucessores. Exemplo: 
 
 2 
 
 1 3 
 
5 4 
 
 
 1 3 
1 3 2 
3 - 
4 3 5 
5 1 2 3 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 15 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
2.4 Caminho e Conexidade 
 
2.4.1 Caminho 
Formalmente temos o seguinte: 
Definição: seja G(V,A) um grafo. Então define-se um caminho de G como sendo uma 
seqüência de arestas da forma (u,v),(v,w),(w,x),...,(y,z), onde cada aresta pertence ao grafo 
G. 
O caminho denotado acima é definido, também, como o caminho entre u e z e pode 
ser representado por: u v w x ... y z. 
O exemplo abaixo mostra um caminho entre d e c. O caminho é denotado por d a b 
c. 
 
 a 
 
 b c 
 
 
 
 d e 
2.4.2 Cadeia 
Definição: uma cadeia é uma seqüência de arestas de um grafo G, tal que qualquer par de 
arestas subseqüentes possuem um vértice de incidência comum. Ao contrário da definição 
de caminho, uma cadeia ignora a orientação das arestas. 
Portanto, todo caminho é uma cadeia, porém a recíproca nem sempre é verdadeira. 
Veja o seguinte exemplo: 
 
 b 
 
 A seqüência a b c d é um caminho, também uma cadeia. 
 a c A seqüência a b d c é uma cadeia, mas não é um caminho. 
 
 d 
 
 
 
 
 
 
2.4.3 Comprimento 
Definição: o número de arestas k que compõem um caminho (ou cadeia) é denominado de 
comprimento do caminho (ou da cadeia). Exemplo. 
 b 
O caminho a b c d é um caminho entre ‘a’ e ‘d’ de 
comprimento igual a 3 
a c 
 
 d 
Caminho: segue a orientação 
Cadeia: não precisa seguir a orientação 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 16 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
2.4.4 Caminho Simples x Trajetória 
Definição: se os vértices de um caminho (ou cadeia) forem distintos (com exceção do 
vértice inicial e o vértice final), então a seqüência recebe o nome de caminho simples (ou 
cadeia simples). Se as arestas da seqüência forem distintas, então a seqüência recebe o 
nome de trajeto ou trajetória. Exemplo: 
 
 2 3 
 
 
 1 4 A seqüência 1 2 3 4 5 é um caminho simples. 
 A seqüência 1 2 3 4 2 é uma trajetória. 
 A seqüência 1 2 3 4 2 1 é apenas uma seqüência. 
 6 5 
 
2.4.5 Grafo Conexo 
Definição: um grafo G é conexo se existe pelo menos um caminho (ou cadeia) entre 
qualquer par de vértices de G. Caso contrário o grafo é desconexo. Exemplo: 
 
 
 
 
 
 
 a) Grafo conexo b) Grafo desconexo 
Todo grafo desconexo é composto por subgrafos conexos chamados de 
componentes. Por exemplo, o grafo b) é um grafo desconexo composto por 2 componentes. 
 
2.4.6 Caminhos abertos e fechados 
Um caminho em G é denominado fechado se o vértice final é o mesmo que o vértice 
inicial. Caso contrário,o caminho é denominado aberto. Exemplo: 
 
 b c 
 
 Caminho aberto: b d c e 
 a Caminho fechado: b d c e b 
 
 
 e d 
 
De forma semelhante a um caminho fechado, uma cadeia fechada de um grafo é 
uma cadeia de G tal que a aresta inicial e a aresta final possuem um vértice de incidência 
em comum, ou em outras palavras, se o vértice inicial e o vértice final se confundem. 
 
2.4.7 Circuito e Ciclo 
Um circuito é um caminho simples fechado. 
Um ciclo é uma cadeia simples fechada. Exemplo: 
 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 17 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
 b c 
 
 Circuito: a b c d a 
 a Ciclo: d c b d 
 
 d 
 
Um grafo que não contém nenhum ciclo é chamado de “grafo acíclico”. 
 
2.4.8 Algoritmo de Goodman 
Esse algoritmo verifica se um grafo é conexo e identifica seus componentes no caso 
de ser desconexo. A idéia consiste em reduzir cada componente a um único ponto. Nesse 
algoritmo necessitamos da definição de fusão de dois vértices 
 
Fusão – Dados dois vértices u e v adjacentes de um grafo G, a fusão de v com u é feita 
eliminando-se a aresta (v,u) e em seguida tornando v e u um único vértice. O vértice 
resultante desta fusão é um vértice w adjacente a todos os vértices anteriormente 
adjacentes a u e/ou v. Exemplo: 
 
 a b a b 
 Após a fusão de u e v  
 
 u v w 
 
O procedimento consiste da escolha de um vértice inicial v0 e a fusão de um vértice 
com ele. Isto é repetido até que não reste qualquer vértice adjacente a v0. Caso reste algum 
vértice não adjacente a v0, então novo vértice v0 é selecionado e o processo é repetido. Se 
no final o grafo resultante for apenas um vértice, então o grafo é conexo. Caso contrário, o 
número de vértices representará o número de componentes do grafo. 
 
Entrada: grafo G(V,A) 
Saída: variável c contendo o número de componentes. 
P0. [inicialize] H  G; c  0; 
P1. [Gere a próxima componente] 
 Enquanto H  0 faça 
 Selecione um vértice v0  H; 
 Enquanto v0 for adjacente a algum vértice u  H faça 
 H  grafo resultante da fusão de u com v0. 
 Remova v0, isto é, faça H  H – v0; 
 c  c + 1; 
P2.[Teste do Tipo de conexidade] 
 Se c>1 então G é desconexo. 
 Senão G é conexo. 
 
 
 
 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 18 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
Exemplo: 
 a b 
 
 f e 1
o
. passo: escolher um vértice. 
 Vértice d. Fusão de d com e. 
 c d 
 
 a b 
 
 f Vértice d. Fusão de d com c. 
 
 c d 
 
 a b 
 
 f Vértice d. Fusão de d com b. 
 
 d 
 
 a 
 
 f Vértice d. Fusão com a. 
 
 d 
 
 d 
 
f 
 
 
2.5 Localização de Centros (em grafos não valorados) 
 
2.5.1 Distância 
Dados dois vértices v e w pertencentes ao grafo G(V,A), denomina-se distância 
entre v e w, o comprimento do menor caminho entre dois vértices v e w. No caso da não 
existência desse caminho, considera-se a distância infinita. 
Notação: d(v,w) = distância entre os vértices v e w 
 = comprimento do menor caminho entre v e w 
 
Denotamos por D(G) a matriz de distâncias de um grafo, onde dij=(vi,vj) 
Em um grafo conexo, distância é uma métrica, isto é, para todo vértice de G(V,A) 
tem-se que: 
i) d(u,v)>=0 com d(u,v)=0 se e somente se u=v. 
ii) d(u,v) = d(v,u) ocorre apenas quando o grafo é não orientado; 
iii) d(u,v) + d(v,w) >= d(u,w) 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 19 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
2.5.2 Pista 
Uma pista (xi,xj) ou (ij) ou ij é um caminho de comprimento mínimo entre xi e xj, ou 
seja, um caminho de comprimento igual a d(xi,xj). Por exemplo, considere o grafo abaixo: 
 b f 
 
 
 a c g 
 
 
 
 d e 
 
 Qual a distância entre a e g? 
d(a,g) = 3, (a,g) = (a,b,f,g) (a,e) = (a,b,f,e) ou (a,c,d,e) 
 
2.5.3 Excentricidade 
A excentricidade de um vértice v, denotado por e(v), é a máxima das distâncias d(v,u), isto 
é: 
e(v) = Max{d(v,u), u  G} 
Em outras palavras, a excentricidade de um vértice v é a maior distância existente a 
partir de v. 
 
2.5.4 Raio 
O raio de um grafo G, denotado por r(g), é o mínimo das excentricidades dos vértices de G 
Min(e(v)). Assim, r(G) = Min{e(v), v  G}. 
 
2.5.5 Centro 
O centro de um grafo G é definido pelo conjunto de vértices v tais que e(v) = r(g), isto é, 
centro = {v  G / e(v) = r(G) }. 
Em uma rede de comunicação, a localização de um ponto importante (uma rede de 
transmissão, por exemplo) em um centro do grafo que representa a rede é, a priori, uma 
providência no sentido de procurar reduzir ao máximo o número de transmissões de 
mensagens ou de equipamentos de conexão envolvidos. 
Exemplo: localizar o centro do grafo abaixo. 
 a b 
 
 
 c 
 
 e d 
 
 a b c d e e(v) 
a 0 1 1 2 1 2 
b 1 0 1 2 2 2 
c 1 1 0 1 1 1 
d 2 2 1 0 1 2 
e 1 2 1 1 0 2 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 20 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
raio = r(G) = 1 
centro = {c} 
 
2.5.6 Centro de um grafo dirigido 
Em um grafo dirigido, define-se excentricidade de um vértice v por 
es = Max{d(v,u), u  G} 
Define-se excentricidade de retorno de um vértice v por 
er = Max{d(u,v), u  G} 
 
O raio de um dígrafo G é definido por: 
r(G) = Min{es(v), er(v)} 
 
Centro de um dígrafo G é definido pelo conjunto de vértices v tais que 
es(v) = r(G) ou er(v) = r(G), isto é: 
centro = {v  G / es(v) = r(G) ou er(v) = r(G)} 
 
Por exemplo, localize o centro do grafo G abaixo: 
 
 a b 
 
 
 c 
 
e d 
 a b c d e es(v) 
a 0 1 1 2 2 2 
b 3 0 1 2 2 3 
c 2 3 0 1 1 3 
d 2 3 3 0 1 3 
e 1 2 2 3 0 3 
er(v) 3 3 3 3 2 
 
raio = r(G) = 2 
centro = {a,e} 
 
2.5.7 Localização de Centros de Emergência 
Aqui o interesse é determinar o centro de um grafo de tal modo que o tempo de ida e de 
volta seja mínimo (é o caso da localização de hospitais, polícia, bombeiro, etc). Observe 
que, neste caso, os vértices representam uma população e, como tal, devem ser levados em 
consideração. 
 
Definição: A excentricidade de saída e retorno de um vértice é definida por: 
esr(xi) = Max {pj [d(xi,xj) + d(xj,xi)]} 
 
 onde j é o peso do vértice xj. Este peso pode ser entendido como a importância do 
vértice. Por exemplo, para localização de um hospital, o tamanho da população num bairro 
pode ser uma informação importante. 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 21 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
Definição: O raio de um grafo G considerando ida e volta é definido por r(G) = 
Min{esr(xi)}. 
 
Definição: O centro de emergência de um grafo G é definido pelo conjunto de 
vértices v tal que esr(v) = r(G). Centro de emergência = {v  G/ esr(v) = r(G)} 
 
Por exemplo, considere o seguinte dígrafo. Localize o centro de emergência do 
grafo. 
 x1 
 
 
 x6 x2 
 
 
 
 
 x5 x3 
 
 
 x4 
 
 
 
 
D(G) 
x1 x2 x3 x4 x5 x6 
0 1 2 3 2 3 
3 0 1 2 1 2 
4 3 0 1 2 3 
3 2 3 0 1 2 
2 1 2 3 0 1 
1 2 3 4 3 0 
 
D
Tx1 x2 x3 x4 x5 x6 
0 3 4 3 2 1 
1 0 3 2 1 2 
2 1 0 3 2 3 
3 2 1 0 3 4 
2 1 2 1 0 3 
3 2 3 2 1 0 
 
D(G) + D
T
 
x1 x2 x3 x4 x5 x6 esr 
0 4 6 6 4 4 6 
4 0 4 4 2 4 4 
6 4 0 4 4 6 6 
6 4 4 0 4 6 6 
4 2 4 4 0 4 4 
4 4 6 6 4 0 6 
Como o peso de cada vértice é igual a 1, então podemos calcular a excentricidade 
diretamente da matriz D(G) + D
T
(G). Portanto, o centro de emergência do grafo é formado 
pelo conjunto {x2,x5}. 
 
Exercícios: 
1 – Desenhe o grafo cuja matriz de adjacência é dada por: 
 
 1 2 3 4 5 6 
0 1 1 0 0 1 
1 0 1 0 1 0 
1 1 0 1 0 0 
0 0 1 0 1 1 
0 1 0 1 0 1 
1 0 0 1 1 0 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 22 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
2 – Desenhe o grafo a partir da lista de adjacência: 
 
 
 
 
 
 
 
 
 
 
 
3 – Localize o centro dos grafos abaixo. Para isso, determine o raio do grafo e a 
excentricidade dos vértices. 
 a 
 a b 
 
 c b 
 
 
 d e c d 
 
 e f 
 
1
1 
1 2 4 
2 4 
3 2 
4 2 3 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 23 
Curso: Informática 
Disciplina: Análise de Algoritmos 
2.6 Algoritmos e problemas clássicos com grafos 
Existem vários algoritmos e problemas considerados “clássicos” na área de Teoria 
dos Grafos. Um desses problemas é o de encontrar um caminho mínimo entre dois vértices. 
Existem vários algoritmos que resolvem esse problema. Um deles é o algoritmo de Floyd. 
2.6.1 Algoritmo de Floyd 
Inicialmente, esse algoritmo faz uma matriz de custo do grafo. Ou seja, ele verifica 
a distância entre cada par de vértices. Se existir uma aresta, o valor que ele coloca naquela 
posição da matriz é o custo da aresta. Se não existir uma aresta entre o par de vértice, ele 
coloca o valor . 
Em seguida, ele verifica se existe um caminho de menor custo entre cada par de 
vértices, ao passar por um vértice intermediário. Ou seja, suponha um grafo com 5 vértices. 
De um modo geral, após montar a matriz de distâncias, ele fará 5 iterações: 
 1ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 1 
 2ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 2 
 3ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 3 
 4ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 4 
 5ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 5 
 
Algoritmo: 
 
Parte1 – Construir a matriz de distância e a matriz de roteamento 
 0, se i=j 
D
0
ij = , se não existe aresta entre o vértice i e o vértice j 
 custo da aresta entre o vértice i e o vértice j 
 
 
R
0
ij = j, se dij <  
 0, caso contrário 
 
Parte2 – Verificar, para cada posição da matriz, se existe um caminho mais curto 
Considerando que n é o número de vértices: 
 
Para k:= 1 to n do 
Begin 
 Para i:=1 to n do 
 Begin 
 Para j:=1 to n do 
 Begin 
 If (D
k-1 
ik + D
k-1
 kj < D
k-1
 ij) then 
 Begin 
 D
k
ij := D
k-1
 ik + D
k-1
kj; 
 R
k
ij := R
k-1
ik; 
 End 
 End; 
 End; 
End; 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 24 
Curso: Informática 
Disciplina: Análise de Algoritmos 
Por exemplo, considerando o grafo abaixo, vamos aplicar o algoritmo de Floyd para 
encontrar a matriz de custo mínimo. 
 
 v2 v3 
 
 
 
 
 
 v1 v5 
 v4 
 
O primeiro passo, então, é construir as matrizes de distância e a matriz de 
roteamento: 
 
 v1 v2 v3 v4 v5 
v1 0 5  3  
v2  0 3   
v3   0  5 
v4 1 1  0 1 
v5  1  1 0 
 
 v1 v2 v3 v4 v5 
v1 1 2 0 4 0 
v2 0 2 3 0 0 
v3 0 0 3 0 5 
v4 1 2 0 4 5 
v5 0 2 0 4 5 
 
Agora, então, o algoritmo fará várias iterações para tentar verificar se existe um 
caminho mais curto entre cada pares de vértices. No início temos: 
K=1, i=1, j=1 se D
0
11 + D
0
11 < D
0
11? 0 + 0<0? Não! 
K=1, i=1, j=2 se D
0
11 + D
0
12 < D
0
12? 0 + 5 < 5? Não! 
K=1, i=1, j=3 se D
0
11 + D
0
13 < D
0
13? 0 +  < ? Não! 
K=1, i=1, j=4 se D
0
11 + D
0
14 < D
0
14? 0 + 3 < 3? Não! 
K=1, i=1, j=5 se D
0
11 + D
0
15 < D
0
15? 0 +  < ? Não! 
 
O significado aqui é o seguinte. Para ir do vértice 1 para qualquer outro, o caminho 
fica mais curto se eu passar primeiro pelo vértice 1? 
 
Como j chegou em n, que é igual a 5 (número de vértices), então a execução sai do 
laço. Então i é incrementado para 2. Temos então: 
K=1, i=2, j=1 se D
0
21 + D
0
11 < D
0
21?  + 0 < ? Não! 
K=1, i=2, j=2 se D
0
21 + D
0
12 < D
0
22?  + 5 < 0? Não! 
K=1, i=2, j=3 se D
0
21 + D
0
13 < D
0
23?  +  < 3? Não! 
K=1, i=2, j=4 se D
0
21 + D
0
14 < D
0
24?  + 3 < ? Não! 
K=1, i=2, j=5 se D
0
21 + D
0
15 < D
0
25?  +  < ? Não! 
 
O significado aqui é o seguinte: na última iteração que vimos, por exemplo, o que 
eu estou querendo saber é se, para ir do vértice v2 ao vértice v5, é mais perto ir primeiro do 
v2 pro v1, e então do v1 pro v5, em vez de ir direto. Ou seja, estou verificando se utilizar o 
vértice 1 como intermediário encurta o caminho. Em outras palavras, para ir do vértice 2 
para qualquer outro, o caminho fica mais curto se eu passar primeiro pelo vértice 1? Vimos 
que, para este grafo, não. 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 25 
Curso: Informática 
Disciplina: Análise de Algoritmos 
Continuando então, i é incrementado para 3. Temos então: 
K=1, i=3, j=1 se D
0
31 + D
0
11 < D
0
31?  + 0 < ? Não! 
K=1, i=3, j=2 se D
0
31 + D
0
12 < D
0
32?  + 5 < ? Não! 
K=1, i=3, j=3 se D
0
31 + D
0
13 < D
0
33?  +  < 0? Não! 
K=1, i=3, j=4 se D
0
31 + D
0
14 < D
0
34?  + 3 < ? Não! 
K=1, i=3, j=5 se D
0
31 + D
0
15 < D
0
35?  +  < 5? Não! 
 
Continuando, i é incrementado para 4. Temos então: 
K=1, i=4, j=1 se D
0
41 + D
0
11 < D
0
41? 1 + 0 < 1? Não! 
K=1, i=4, j=2 se D
0
41 + D
0
12 < D
0
42? 1 + 5 < 1? Não! 
K=1, i=4, j=3 se D
0
41 + D
0
13 < D
0
43? 1 +  < ? Não! 
K=1, i=4, j=4 se D
0
41 + D
0
14 < D
0
44? 1 + 3 < 0? Não! 
K=1, i=4, j=5 se D
0
41 + D
0
15 < D
0
45? 1 +  < 1? Não! 
 
Continuando, i é incrementado para 5. Temos então: 
K=1, i=5, j=1 se D
0
51 + D
0
11 < D
0
51?  + 0 < ? Não! 
K=1, i=5, j=2 se D
0
51 + D
0
12 < D
0
52?  + 5 < 1? Não! 
K=1, i=5, j=3 se D
0
51 + D
0
13 < D
0
53?  +  < ? Não! 
K=1, i=5, j=4 se D
0
51 + D
0
14 < D
0
54?  + 3 < 1? Não! 
K=1, i=5, j=5 se D
0
51 + D
0
15 < D
0
55?  +  < 0? Não! 
 
Agora, i já chegou ao valor n, ou seja, i=5. Neste caso, o loop chega ao fim. Agora, 
a variável k é incrementada e passa ser 2. Isso significa que agora vamos ver, para cada par 
de vértices, se o uso do v2 como intemediário torna o caminho mais curto. 
 
K=2, i=1, j=1 se D
0
12 + D
0
21 < D
0
11? 5 +  < 0? Não! 
K=2, i=1, j=2 se D
0
12 + D
0
22 < D
0
12? 5 + 0 < 5? Não! 
K=2, i=1, j=3 se D
0
12+ D
0
23 < D
0
13? 5 + 3 < ? Sim!!!!!!!!!! 
K=2, i=1, j=4 se D
0
12 + D
0
24 < D
0
14? 5 +  < 3? Não! 
K=2, i=1, j=5 se D
0
12 + D
0
25 < D
0
15? 5 +  < ? Não! 
 
No momento em que eu achei um curto, então gero a minha matriz D
1
. Na prática, 
no algoritmo, é possível apenas sobrescrever os valores anteriores. A minha matriz de 
distâncias e a de roteamento passam a ser: 
 
 v1 v2 v3 v4 v5 
v1 0 5 8 3  
v2  0 3   
v3   0  5 
v4 1 1  0 1 
v5  1  1 0 
 
 v1 v2 v3 v4 v5 
v1 1 2 2 4 0 
v2 0 2 3 0 0 
v3 0 0 3 0 5 
v4 1 2 0 4 5 
v5 0 2 0 4 5 
 
Reparem que a matriz de roteamento agora indica que, para ir do vértice v1 para o 
vértice v3, é preciso primeiro passar pelo vértice v2. 
 
 
 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 26 
Curso: Informática 
Disciplina: Análise de Algoritmos 
Continuando temos: 
K=2, i=2, j=1 se D
0
22 + D
0
21 < D
0
21? 0 +  < ? Não! 
K=2, i=2, j=2 se D
0
22 + D
0
22 < D
0
22? 0 + 0 < 0? Não! 
K=2, i=2, j=3 se D
0
22 + D
0
23 < D
0
23? 0 + 3 < 3? Não! 
K=2, i=2, j=4 se D
0
22 + D
0
24 < D
0
24? 0 +  < ? Não! 
K=2, i=2, j=5 se D
0
22 + D
0
25 < D
0
25? 0 +  < ? Não! 
Continuando temos: 
K=2, i=3, j=1 se D
0
32 + D
0
21 < D
0
31?  +  < ? Não! 
K=2, i=3, j=2 se D
0
32 + D
0
22 < D
0
32?  + 0 < ? Não! 
K=2, i=3, j=3 se D
0
32 + D
0
23 < D
0
33?  + 3 < 0? Não! 
K=2, i=3, j=4 se D
0
32 + D
0
24 < D
0
34?  +  < ? Não! 
K=2, i=3, j=5 se D
0
32 + D
0
25 < D
0
35?  +  < 5? Não! 
 
Continuando temos: 
K=2, i=4, j=1 se D
0
42 + D
0
21 < D
0
41? 1 +  < 1? Não! 
K=2, i=4, j=2 se D
0
42 + D
0
22 < D
0
42? 1 + 0 < 1? Não! 
K=2, i=4, j=3 se D
0
42 + D
0
23 < D
0
43? 1 + 3 < ? Sim!!!!! 
K=2, i=4, j=4 se D
0
42 + D
0
24 < D
0
44? 1 +  < 0? Não! 
K=2, i=4, j=5 se D
0
42 + D
0
25 < D
0
45? 1 +  < 1? Não! 
 
As matrizes passam a ser, então: 
 
 v1 v2 v3 v4 v5 
v1 0 5 8 3  
v2  0 3   
v3   0  5 
v4 1 1 4 0 1 
v5  1  1 0 
 
 v1 v2 v3 v4 v5 
v1 1 2 2 4 0 
v2 0 2 3 0 0 
v3 0 0 3 0 5 
v4 1 2 2 4 5 
v5 0 2 0 4 5 
Continuando temos: 
K=2, i=5, j=1 se D
0
52 + D
0
21 < D
0
51? 1 +  < ? Não! 
K=2, i=5, j=2 se D
0
52 + D
0
22 < D
0
52? 1 + 0 < 1? Não! 
K=2, i=5, j=3 se D
0
52 + D
0
23 < D
0
53? 1 + 3 < ? Sim!!! 
K=2, i=5, j=4 se D
0
52 + D
0
24 < D
0
54? 1 +  < 1? Não! 
K=2, i=5, j=5 se D
0
52 + D
0
25 < D
0
55? 1 +  < 0? Não! 
 
As matrizes passam a ser, então: 
 
 v1 v2 v3 v4 v5 
v1 0 5 8 3  
v2  0 3   
v3   0  5 
v4 1 1 4 0 1 
v5  1 4 1 0 
 
 v1 v2 v3 v4 v5 
v1 1 2 2 4 0 
v2 0 2 3 0 0 
v3 0 0 3 0 5 
v4 1 2 2 4 5 
v5 0 2 2 4 5 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 27 
Curso: Informática 
Disciplina: Análise de Algoritmos 
Repetindo então o processo para k=3, k=4 e k=5, no final teremos as duas seguintes 
matrizes: 
 
 v1 v2 v3 v4 v5 
v1 0 4 7 3 4 
v2 10 0 3 9 8 
v3 7 6 0 6 5 
v4 1 1 4 0 1 
v5 2 1 4 1 0 
 
 v1 v2 v3 v4 v5 
v1 1 4 4 4 4 
v2 3 2 3 3 3 
v3 5 5 3 5 5 
v4 1 2 2 4 5 
v5 4 2 2 4 5 
Assim, a matriz da esquerda indica qual será o custo mínimo pra ir de um vértice a 
outro, enquanto a matriz da direita mostra qual é o caminho que deverá ser percorrido para 
ir de um vértice a outro com o custo mínimo. Por exemplo: 
 Para ir do vértice v1 para o vértice v2, o caminho mais curto, de custo 4, é passando 
pelo vértice v4. Ou seja, v1-v4-v2. 
 Para ir do vértice v1 para o vértice v3, o caminho mais curto, de custo 7, é passando 
pelo vértice v4. No entanto, vemos na matriz de roteamento que não podemos ir direto 
do v4 para o v3, é preciso passar pelo vértice v2. Assim, a rota então é v1-v4-v2-v3. 
 
Olhando apenas para essa matriz, responda: 
a) Qual é a rota de custo mínimo entre o vértice v1 e o vértice v5? 
b) Qual é a rota de custo mínimo entre o vértice v4 e o vértice v3? 
c) Qual é a rota de custo mínimo entre o vértice v5 e o vértice v1? 
 
Exercício – Utilizando o algoritmo de Floyd, encontre a matriz de custo mínimo e a 
matriz de roteamento para o grafo abaixo: 
 
 
 
 
 
 
 
 
 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 28 
Curso: Informática 
Disciplina: Análise de Algoritmos 
2.6.2 Algoritmo de Dijkstra 
O algoritmo de Dijkstra é semelhante ao de Floyd. Inicialmente, o usuário também 
deve entrar com a matriz de custo do grafo. No entanto, este algoritmo considera que o 
grafo tem um vértice inicial. Assim, ele só calcula o caminho mínimo do vértice inicial 
para todos os outros. Portanto, o usuário deve definir em seguida qual é o vértice inicial. 
O algoritmo gera então dois vetores simples: 1)uma matriz de rota e 2)uma matriz 
de custo mínimo. 
 
Leia (Custo[ ]); //ler matriz de custo 
Leia (vert); //ler vértice inicial 
Para i = 1 .. n faça // n é o número de vértices 
 Begin 
 Rota[i] = vert; // Rota do vértice inicial até o vértice i 
 Dist[i] = Custo[vert,i] // Custo inicial do vértice inicial até o vértice i 
 End 
Para a = 1.. n faça 
 Para todo k  +(a) //Para todo vértice k que é sucessor do vértice a 
 Begin 
 P = mín(D[k], D[a]+Custo[a,k]); 
 If (P < D[k]) Then 
 Begin 
 Rota[k] = a; 
 Dist[k] = P; 
 End 
 
Só lembrando que os vértices sucessores de a serão aqueles que têm um valor de 
custo diferente de 0 (ou seja, não é o próprio vértice) e diferente de  (ou seja, não existe 
aresta entre eles e, portanto, o vértice não é um sucessor). 
 Considere por exemplo o seguinte grafo: 
 
 1 2 2 
 3 
 10 
 7 3 
 8 
 
 5 4 
 
 5 
 
 4 
Inicialmente, o algoritmo solicita que o usuário entre a matriz de custo do grafo. 
 1 2 3 4 5 
1 0 2   10 
2  0 3  7 
3   0 4  
4    0  
5   8 5 0 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 29 
Curso: Informática 
Disciplina: Análise de Algoritmos 
Em seguida, pergunta qual é o vértice inicial. Vamos considerar que o vértice inicial é o 
vértice 1. Temos então: 
 
Vert = 1 
Rota[1,1,1,1,1]. 
Dist[0,2, ,,10] 
 
Ou seja, inicialmente ele inicializa todas as posições do vetor Rota com o vértice 
inicial. Em seguida, coloca o custo das arestas do vértice inicial para todas as outras. 
Quando a aresta não existe, o valor  é colocado. 
 
a = 1, k=1 vértice 1 não é sucessor de 1 
 k=2 D[2] x D[1] + Custo[1,2]  2 x 0+2  p=2. p < D[k]?? 2 <2 ? Não! 
 k=3 vértice 3 não é sucessor de 1 
 k=4 4 não é sucessor de 1 
 k=5 D[5] x D[1] + Custo[1,5]  10 x 0+10  p=10 p < D[k]? 10 < 10? Não! 
 
a = 2, k=1 vértice 1 não é sucessor de 2 
 k=2 vértice 2 não é sucessor de 2 
 k=3 D[3] x D[2] + Custo[2,3]   x 2+3  p=5 p<D[k]? 5<? Sim!! 
 Rota[3]=2, Dist[3]=5 
 Rota[1,1,2,1,1] e Dist[0,2,5, ,10]k=4 4 não é sucessor de 2 
 k=5 D[5] x D[2] + Custo[2,5]  10 x 2+7  p=9 p < D[k]? 9 < 10? Sim! 
 Rota[5]=2, Dist[5]=9 
 Rota[1,1,2,1,2] e Dist[0,2,5, ,9] 
 
a = 3, k=1 vértice 1 não é sucessor de 3 
 k=2 vértice 2 não é sucessor de 3 
 k=3 vértice 3 não é sucessor de 3 
 k=4 D[4] x D[3] + Custo[3,4]   x 5+4  p=9 p < D[4]? 9 < ? Sim! 
 Rota[4]=3, Dist[4]=9 
 Rota[1,1,2,3,2] e Dist[0,2,5, 9,9] 
 k=5 vértice 5 não é sucessor de 3 
 
a = 4, k=1 vértice 1 não é sucessor de 4 
 k=2 vértice 2 não é sucessor de 4 
 k=3 vértice 3 não é sucessor de 4 
 k=4 vértice 4 não é sucessor de 4 
 k=5 vértice 5 não é sucessor de 4 
 
a = 5, k=1 vértice 1 não é sucessor de 5 
 k=2 vértice 2 não é sucessor de 5 
 k=3 D[3] x D[5] + Custo[5,3]  5 x 9+8  p=5 p < D[3]? 5 < 5? Não! 
 k=4 D[4] x D[5] + Custo[5,4]  9 x 9+5  p=9 p < D[4]? 9 < 9? Não! 
 k=5 vértice 5 não é sucessor de 5 
 
Assim, no final temos: 
Rota[1,1,2,3,2] e Dist[0,2,5,9,9]. 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 30 
Curso: Informática 
Disciplina: Análise de Algoritmos 
Exercício 1 – Para o mesmo grafo, repita o procedimento acima, mas considerando 
que o vértice inicial é o vértice 2. 
Exercício 2 – Para o seguinte grafo, aplique o algoritmo “passo a passo”, de forma 
a descobrir a matriz de rota e a matriz de custo mínimo. Considere que o vértice 1 é vértice 
inicial. Determine então a pista do vértice 1 para todos os outros vértices 
 
 
 2 1 3 
 
 10 
 1 3 2 9 4 6 
 
 
 5 7 
 
 5 2 4 
 
2.6.3 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. 
 
TEOREMA: 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. 
 
TEOREMA: Um dígrafo G contém um circuito de Euler se e somente se os graus de 
entrada e saída de cada vértice forem iguais. 
 
Exemplos: 
 
 
 
 
 
 
 a) Não é grafo de Euler b)Não é grafo de Euler c) Grafo de Euler 
 
2.6.4 Problema do Carteiro Chinês 
A noção de grafos de Euler e caminhos de Euler são utilizadas quando é necessário 
atender seqüencialmente a um conjunto de usuários, sendo que todos devem ser atendidos. 
Exemplo são: entrega de correio, coleta de lixo, etc. 
O problema do carteiro chinês consiste em encontrar um caminho que passe por 
TODAS AS ARESTAS do grafo G(V,A) pelo menos uma vez, de preferência uma única 
vez. Há dois tipos de solução para esse problema: 
 Solução 1 – Quando o grafo é de Euler. Nesse caso, o caminho pode ser achado (e 
também seu respectivo custo). Para isso, utiliza-se o algoritmo de Fleury. 
 Solução 2 – Quando o grafo não é de Euler. Nesse caso, algumas arestas terão que ser 
repetidas e utiliza-se um algoritmo diferente. 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 31 
Curso: Informática 
Disciplina: Análise de Algoritmos 
2.6.4.1 Algoritmo de Fleury 
Este algoritmo parte do pressuposto de que G é um grafo de Euler. 
Para executar o algoritmo, deve-se iniciar em qualquer vértice v e atravessar as 
arestas de maneira arbitrária, seguindo as seguintes regras: 
 Regra 1 – Apague a aresta que foi visitada e, se algum vértice ficar isolada, apague-o 
também. 
 Regra 2 – Em cada estágio, use uma ponte (istmo) somente se não houver alternativa. 
Isto é, nunca atravesse uma aresta se essa aresta divide o grafo em duas componentes 
(excluindo o vértice isolado. 
 Observação: uma ponte (istmo) é uma aresta do grafo G cuja remoção divide o grafo G 
em duas componentes conexas de ordem maior que 1. Por exemplo, no exemplo 
abaixo, a aresta d é uma ponte. 
 
 
 b c e f 
 
 
 a d g 
 
Vamos considerar, por exemplo, o grafo abaixo e aplicar o algoritmo de Fleury, 
considerando o vértice 6 como vértice inicial (que, conseqüentemente, deve ser também o 
vértice final. 
 1 2 3 
 
 a b c d e f 
 
 g h i 
 4 5 6 7 
 
Pode-se iniciar o algoritmo por qualquer aresta que saia do vértice 6. Por exemplo, 
as arestas d, e, h, i. Conforme a implementação, pode-se deixar a escolha aleatória, ou 
pegar sempre o primeiro vértice, conforme a ordem em que o usuário digitou. Por exemplo, 
vamos iniciar pela aresta d, que deve então ser removida. Temos então a configuração da 
Figura 2. 
Em seguida a única aresta possível que pode ser removida é a c. Ao removermos a 
aresta c, o vértice 2 fica isolada, sendo removido. Temos então a configuração da Figura 3. 
 
 
 
 
 
 
 
 
Figura 2 
 
 
 
 
 
 
 
 
Figura 3 
 
O processamento está agora no vértice 5. Como a aresta h é uma ponte, não se pode 
escolhê-la. Pode-se então passar pela aresta b ou g. Vamos percorrer a aresta b, gerando 
então a configuração da Figura 4. 
1 2 3 
4 5 6 7 
a b c e f 
g h i 
4 5 6 7 
1 3 
a b e f 
g h i 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 32 
Curso: Informática 
Disciplina: Análise de Algoritmos 
Em seguida, a única opção é percorrer a aresta a. Ao eliminarmos essa aresta, o 
vértice 1 fica isolado e, portanto, é também eliminado. A configuração do grafo é mostrada 
na Figura 5. 
 
 
 
 
 
 
 
 
Figura 4 
 
 
 
 
 
 
 
 
 
Figura 5 
O processamento do algoritmo está agora no vértice 4. A única opção, portanto, é a 
aresta g, que é percorrida e eliminada. Como o vértice 4 ficou isolado, é também eliminado 
(Figura 6). 
No vértice 5, a única opção é a aresta h, que é percorrida e eliminada, juntamente 
com o vértice 5. Temos então a configuração da Figura 7. 
 
 
 
 
 
 
 
 
 
Figura 6 
 
 
 
 
 
 
 
 
 
Figura 7 
No vértice 6, novamente há duas opções: a aresta ‘e’ e a aresta ‘i’. Como estávamos 
seguindo sempre a aresta de menor ordem alfabética, vamos percorrer a aresta ‘e’, que é 
eliminada (Figura 8). 
Em seguida, a única opção é a aresta f, que é eliminada juntamente com o vértice 3. 
Temos então a configuração da Figura 9.Figura 8 
 
 
 
 
 
 
 
 
 
 
Figura 9 
 
No vértice 7, a única opção é a aresta ‘i’, que é percorrida e eliminada, juntamente 
com o vértice 7. Chegamos então no vértice final, que é também o final, e o algoritmo 
acaba. 
1 3 
4 5 6 7 
a e f 
g h i 
3 
4 5 6 7 
e f 
g h i 
3 
5 6 7 
e f 
h i 
3 
6 7 
e f 
i 
3 
6 7 
f 
i 
6 7 
i 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 33 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 
 
 
 
 
 6 
 
 
O algoritmo de Fleury, propriamente dito, pode ser expresso da seguinte forma: 
 
Ler grafo G(V,A) 
G' := G 
v0 := um vértice de G' 
C := [v0] //Inicialmente, o caminho de Euler contém só o vértice inicial v0 
Enquanto A' não vazio //Ou seja, enquanto ainda existirem arestas 
 vi := último vértice de C 
 Se vi tem só uma aresta incidente; 
 ai := a aresta incidente a vi em G' 
 Senão 
 ai := uma aresta incidente a vi em G' e que não é uma ponte 
 Retirar a aresta ai do grafo G' 
 Acrescentar ai no final de C 
 vj := vértice ligado a vi por ai 
 Acrescentar vj no final de C 
Retornar C 
 
No caso do exemplo mostrado, então, as variáveis do algoritmo teriam o seguinte 
comportamento: 
A’ = {a,b,c,d,e,f,g,h,i} V’ = {1,2,3,4,5,6,7} 
C == [6] 
 
Figura 2 
Vi:= 6 
ai := d 
A’ = {a,b,c,e,f,g,h,i} 
C = [6,d] 
vj := 2 
C = [6,d,2] 
 
Figura 3 
Vi:=2 
Ai:= c 
A’ = {a,b,e,f,g,h,i} 
C = [6,d,2,c] 
Vj:= 5 
C = [6,d,2,c,5] 
... 
 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 34 
Curso: Informática 
Disciplina: Análise de Algoritmos 
Exercício 
Considere o grafo abaixo. 
a) Mostre por que é um grafo de Euler. 
b) Aplique o algoritmo de Flery, considerando o vértice x1 como inicial. 
c) Aplique o algoritmo novamente, considerando o vértice x4 como inicial. 
Nos itens b) e c), mostre o grafo sendo percorrido passo a passo, juntamente com o 
valor das variáveis do algoritmo no momento. 
 
 x1 
 
 
 
 x7 x6 x2 
 
 
 
 
 
 x8 x5 x3 
 
 
 
 x4 
 
2.6.5 Caminho e Circuito Hamiltoniano 
De forma resumida, um caminho que passa exatamente uma vez por cada vértice de 
um grafo é chamado hamiltoniano. Se o caminho começa e termina no mesmo vértice, 
temos um circuito hamiltoniano. Um grafo que contém um ciclo hamiltoniano é um grafo 
hamiltoniano. 
De forma formal: um circuito hamiltoniano em um grafo conexo G pode ser 
definido como um caminho simples fechado que passa em cada vértice de G exatamente 
uma vez. Portanto, um circuito hamiltoniano de um grafo conexo de n vértices consiste 
exatamente de n arestas. É possível, também, que um único grafo contenha vários 
caminhos hamiltonianos. 
Teorema de Dirac: Uma condição suficiente, mas não necessária, para que um 
grafo simples G possua um ciclo hamiltoniano é que o grau de cada vértice de G seja pelo 
menos igual a n/2, onde n é o número de vértices. 
 
2.6.6 Problema do Caixeiro Viajante 
Suponha que um caixeiro viajante tenha de visitar n cidades diferentes, iniciando e 
encerrando sua viagem na primeira cidade. Suponha, também, que não importa a ordem 
com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer 
outra. Assim, o problema do caixeiro viajante consiste em descobrir a rota que torna 
mínima a viagem total. 
O custo pode ser expresso em termos de dinheiro, distância, etc. Na prática, trata-se 
de achar um circuito hamiltoniano de custo mínimo para o grafo representando o problema. 
 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 35 
Curso: Informática 
Disciplina: Análise de Algoritmos 
2.6.6.1 Complexidade do problema 
O problema do caixeiro viajante nos mostra que alguns problemas computacionais 
ainda são difíceis de serem resolvidos computacionalmente, mesmo com os computadores 
potentes que temos atualmente. 
Para entender isso, devemos notar que um mesmo grafo pode conter diversos 
caminhos hamiltonianos. Ou seja, conforme as arestas percorridas, teremos caminhos 
diferentes, com custos diferentes. Assim, não basta achar um circuito hamiltoniano, deve-
se achar um de “custo mínimo”. 
Suponha então que existem 4 cidades a serem percorridas, A, B, C e D, como 
demonstrado pelo grafo abaixo. 
 
 
 
 
 
 
 
 
Supondo que de cada cidade pode-se ir diretamente a qualquer outra, então, só 
saindo de A existem seis rotas possíveis: 
 ABCDA (custo 18) 
 ABDCA (custo 16) 
 ACBDA (custo 14) 
 ACDBA (custo 16) 
 ADBCA (custo 15) 
 ADCBA (custo 18)o 
Assim, não basta apenas achar uma rota qualquer, deve-se ainda encontrar a de 
menor custo, neste caso a de custo 14. Ou seja, o melhor procedimento, teoricamente, é 
encontrar todas as possíveis rotas e, em seguida, verificar qual delas tem o menor custo. 
Mas embora isso pareça simples, na prática nem sempre é possível. 
Considere novamente este exemplo. Além das 6 rotas iniciando pela cidade A, 
temos ainda seis possibilidades começando com B, mais seis possibilidades começando 
com C e mais seis iniciando com D. Ou seja são 24 combinações, ou (n!), onde n é o 
número de cidades. Supondo que eu considere apenas uma cidade inicial, por exemplo a 
cidade A, temos as 6 combinações acima, ou (n-1)!. 
Se eu criar um algoritmo para encontrar todas as rotas, ele vai executar 
perfeitamente com grafos com poucos vértices, como esse acima. No entanto, conforme o 
número de grafos cresce, o tempo para encontrar todas as rotas pode ser impraticável. 
Suponha um computador que seja capaz de fazer 1 bilhão de somas por segundo e 
um grafo com 20 cidades. Assim, esse computador gastará 19 adições para calcular uma 
rota qualquer, apenas concatenando cidades aleatórias. Portanto, se em 1 segundo ele 
consegue fazer 1 bilhão de adições e para cada rota eu preciso apenas de 19 adições, 
portanto em cada segundo é possível calcular aproximadamente 53 milhões de rotas por 
segundo (1bilhão/19). 
Embora isso possa parecer razoável à primeira vista, vamos ver então quantas rotas 
existem com 20 cidades. Considerando apenas uma cidade inicial, então são (n-1)! rotas 
possíveis, ou seja, 19!, que equivale a 121 645 100 408 832 000, ou 121 “quadrilhões”. 
A B 
C D 
2 4 
3 5 
4 
6 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 36 
Curso: Informática 
Disciplina: Análise de Algoritmos 
1 segundo -------------- 53 milhões de rotas 
x -------------- 121 645 100 408 832 000 rotas 
 
X = 121 645 100 408 832 000 = 2.3 x 10
9
 segundos 
 53.000.000 
 
Ora, se em 1 segundo eu calculo 53 milhões de rotas, para calcular esse número de 
rotas eu preciso de 2.3 x 10
9
 segundos, o que equivale a aproximadamente 73 anos. 
 
 
 
 
 
 
 
 
 
A tabela a seguir demonstra o tempo que demora para calcular todas as rotas 
necessárias considerando grafos com 5, 10, 15, 20 e 25 cidades. 
 
Cidades(n) Rotas por segundo Número de rotas( n - 1 )! Tempo para o cálculo 
5 250 milhoes 24 insignificante 
10 110 milhoes 362 880 0.003 seg 
15 71 milhoes 87 bilhoes 20 min 
20 53 milhoes 1.2 x 10
17
 73 anos 
25 42 milhoes 6.2 x 10
23
 470 milhoes de anos 
 
Esse problema demonstra, portanto, que mesmo com os computadores potentes 
existentes atualmente, para alguns problemas não bastaconseguir fazer um algoritmo para 
resolver um problema. O algoritmo deve ser eficiente. 
 
2.6.6.2 Aplicações 
Algumas aplicações práticas de algoritmos que resolvem o problema do caixeiro-
viajante são as seguintes: 
 Programação de operações de máquinas em manufatura (Finke e Kusiak, 1985) 
 Programação do movimento de ferramentas de corte (Chauny et al., 1987) 
 Problemas de roteamento de veículos (Bodin et al., 1983) 
 Solução de problemas de seqüenciamento de uma forma geral (Whitley et al, 1991) 
 Solução de problemas de programação (Salomon et al, 1997) 
 Distribuição de tarefas em plantas industriais (Salomon et al, 1997) 
 Trabalhos administrativos (Laporte et al, 1996) 
 Minimização do tempo que um robô industrial gasta para soldar a carcaça de um 
automóvel 
 Diminuição do tempo ou combustível na distribuição diária de um jornal produzido 
numa grande cidade. 
2.6.6.3 Tipos de soluções 
Em grafos pequenos, é possível achar vários (ou todos) os circuitos hamiltonianos 
e, em seguida, pegar aquele com o menor custo. No entanto, com grafos muito grandes não 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 37 
Curso: Informática 
Disciplina: Análise de Algoritmos 
é possível encontrar todos os circuitos hamiltonianos. Assim, existem dois tipos de solução 
para este problema: 
Solução 1 – Métodos exatos. Encontram a melhor solução, ou seja, de custo mínimo. 
Solução 2 – Métodos aproximados (heurísticas). Geram soluções satisfatórias, mas sem 
garantias de que aquele circuito hamiltoniano é o melhor possível. 
Embora existam métodos exatos, eles não são muito eficientes, devido à dificuldade 
mostrada anteriormente. Assim, normalmente são utilizados os métodos aproximados. 
Alguns exemplos de soluções são as seguintes: 
 Heurística greedy (algoritmo guloso) 
 Vizinho mais próximo 
 Inserção mais próximo 
 Inserção mais distante 
 Inserção mais econômica 
 K-opt ou K-melhoramento 
 “Simulated Annealing” 
 Algoritmos Genéticos 
 Busca Tabu 
 Heurística Clarke-Wright 
 
 
1. ALGORITMO VIZINHO MAIS PRÓXIMO 
O algoritmo consiste basicamente dos seguintes passos: 
 Escolher um vértice i qualquer e iniciar a rota. 
 Repetir os seguintes passos até incluir todos os vértices 
o Procure, considerando apenas os vértices j ainda não incluídos na rota, 
aquele que seja o mais próximo do último vértice considerado. 
o Acrescente o vértice ao roteiro 
 Acrescentar o primeiro vértice selecionado ao final da rota 
 
Pode-se observar que, embora esse algoritmo funcione para grafos onde todos os 
vértices têm ligação com todos os vértices, pode não funcionar caso contrário. 
Considere por exemplo o seguinte grafo. 
 
 
 
 
 
 
 
 
 
 
Aplicando o algoritmo, temos: 
1. Escolher, por exemplo, o vértice ‘a’. 
2. O vértice mais próximo é o ‘e’. Portanto a rota fica ‘a e’. 
3. A partir do vértice ‘e’, o mais próximo é o ‘f’. A rota, portanto, fica ‘a e f’. 
4. A partir do vértice ‘f’, o mais próximo é o b. A rota, portanto, fica ‘a e f b’. 
5. A partir do vértice ‘b’, o único vértice possível é o ‘c’. A rota, portanto, fica ‘a e f b c’ 
4 5 
4 5 
2 2 4 3 
4 
a 
b 
c 
d e 
f 
3 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 38 
Curso: Informática 
Disciplina: Análise de Algoritmos 
6. A partir do vértice ‘c’, o único vértice possível é o ‘d’. A rota, portanto, fica ‘a e f b c d’. 
7. Como todos os vértices foram inseridos, agora deveria-se acrescentar primeiro vértice 
(a) ao final da rota. No entanto, não há uma ligação direta entre ‘d’ e ‘a’ e, portanto, essa 
rota não é válida. 
Assim, pudemos perceber que esse algoritmo nem sempre encontra uma solução 
válida. Além disso, vale lembrar que, mesmo que se encontre uma solução, nem sempre ela 
é ótima. Por exemplo, a rota “c d e a b f c’ tem custo 21, enquanto a rota ‘f e a b c d f’ tem 
custo 20. 
 
2. ALGORITMO MAIS ECONÔMICA (Inserção do mais próximo) 
Este algoritmo é bastante similar ao anterior. Ou seja, inicia-se considerando um 
vértice inicial e buscando o vértice mais próximo. A diferença é que, a cada vez que eu 
procuro um novo vértice para inserir, vou escolher aquele que esteja mais perto de 
“qualquer um dos vértices que já façam parte do roteiro”. 
Ou seja, o algoritmo consiste dos seguintes passos: 
1. Escolher um vértice i qualquer. 
2. Selecionar um vértice k mais próximo de i e criar um roteiro passando por k, ou seja, 
“i k i” (Se o grafo orientado, o vértice selecionado deve ser tal que a ida e a volta são as 
menores possíveis, ou seja o menor valor para dik + dki). 
3. Repetir até que todos os vértices do grafo sejam inseridos: 
 A)Considerando o roteiro já formado, selecione um novo vértice k mais próximo 
de qualquer um dos vértices do roteiro 
 B)Considerando só as arestas que fazem parte do roteiro já formado, encontrar a 
aresta (x,y) do roteiro que apresenta o menor valor para (Dxk + Dky – Dxy). 
 C)Inserir o vértice k entre x e y. 
 
No passo b) do item 3, se não for encontrada nenhuma aresta, o procedimento vai 
depender da implementação do algoritmo. O algoritmo pode a) ser finalizado ou b) 
procurar outro vértice k para inserir no roteiro. 
 
Exemplo: Considere o mesmo grafo do exemplo anterior, reproduzido a seguir. Vamos 
aplicar o algoritmo “inserção do mais próximo”. 
 
 
 
 
 
 
 
 
 
 
Passo 1: Escolher inicialmente o vértice ‘a’. 
Passo 2. Selecionamos o vértice mais próximo, que é o vértice ‘e’. Formamos então o 
roteiro “a e a”. 
Passo 3: 
 Considerando esse roteiro, o vértice mais próximo é o vértice ‘f’. Visualmente, é fácil 
perceber que tanto faz montar o roteiro da forma “afea” ou “aefa”. Mas seguindo o 
algoritmo, temos então: 
4 5 
4 5 
2 2 4 3 
4 
a 
b 
c 
d e 
f 
3 
Faculdade de Filosofia, Ciências e Letras de Mandaguari 39 
Curso: Informática 
Disciplina: Análise de Algoritmos 
 Aresta ‘ae’ 
X=c, y=e, k=f Daf+ Dfe-Dae = 4 +2 -2 = 4 
 Aresta ‘ea’ 
X=e, y=a, k=f Def + Dfa - Dea = 2 + 4 -2 = 4 
 
 Como os dois roteiros têm o mesmo custo, vamos selecionar o primeiro. Temos 
então o roteiro “a f e a”. 
 
 Considerando esse roteiro, o vértice mais próximo é o vértice ‘b’. Temos então: 
 Aresta ‘af’ 
X=a, y=f, k=b Dab+ Dbf-Daf = 4 +3 -4 = 3 
 Aresta ‘fe’ 
X=f, y=e, k=b Dfb + Dbe - Dfe = 3 +  - 2 =  
 Aresta ‘ea’ 
X=e, y=a, k=b Déb + Dba – Dea =  + 4 -2 =  
 
Portanto, o menor roteiro é obtido inserindo-se o vértice ‘b’ entre os vértices ‘a’ e 
‘f’. Portanto, o roteiro formado é “a b f e a”. 
 
 Considerando esse roteiro, o vértice mais próximo é o vértice ‘d’. Temos então: 
 Aresta ‘ab’ 
X=a, y=b, k=d Dad+ Ddb-Dab =  + -4 =  
 Aresta ‘bf’ 
X=b, y=f, k=d Dbd + Ddf - Dbf =  + 4 - 3 =  
 Aresta ‘fe’ 
X=f, y=e, k=d Dfd + Dde – Dfe = 4 + 4 -2 = 6 
 Aresta ‘ea’ 
X=e, y=a, k=d Ded + Dda – Dea = 4 +  -2 =  
 
Portanto, o menor roteiro é obtido inserindo-se o vértice ‘d’ entre os vértices ‘f’ e 
‘e’. Portanto, o roteiro formado é “a b f d e a”. 
 
 Considerando esse roteiro, o vértice mais próximo é o vértice ‘c’. Temos então: 
 Aresta ‘ab’ 
X=a, y=b, k=c Dac+ Dcb-Dab =  +5 -4 =  
 Aresta ‘bf’ 
X=b, y=f, k=c Dbc + Dcf - Dbf = 5 + 5 - 3 = 7 
 Aresta ‘fd’ 
X=f, y=d, k=c Dfc + Dcd – Dfd = 5 + 3 -4 = 4 
 Aresta ‘de’ 
X=d, y=e, k=c Ddc + Dce – Dde = 3 +  -4 =  
 Aresta ‘ea’ 
X=e, y=a, k=c Dec + Dca – Dea =  +  -2 =  
 
Portanto, o menor roteiro é obtido inserindo-se o vértice ‘c’ entre os vértices ‘f’ e 
‘d’. Portanto, o roteiro formado é “a b f c d e a”, com um custo total de 21. 
 
Deve-se notar que, embora este algoritmo encontre um roteiro com custo baixo, que 
certamente