apostila completa

Prévia do material em texto

�PAGE �
�PAGE �
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�
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:
1o. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0
2o. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0
3o. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0
4o. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0
ÍNDICE
51	Introdução	�
51.1	Objetivo da Disciplina	�
51.2	Medidas de Desempenho de Algoritmos	�
72	Teoria dos Grafos	�
72.1	Introdução	�
72.1.1	Representação Gráfica	�
72.1.2	Representação Matemática	�
72.1.3	Definições Básicas	�
82.1.4	Tipos de Grafos	�
112.2	Sucessores e Antecessores de um Grafo Dirigido	�
112.3	Representação de Grafos em um Computador	�
112.3.1	Matriz de Adjacência	�
122.3.2	Matriz de Custo	�
122.3.3	Matriz de Incidência	�
132.3.4	Lista de Arestas	�
132.3.5	Estrutura de Adjacência	�
142.4	Caminho e Conexidade	�
142.4.1	Caminho	�
142.4.2	Cadeia	�
142.4.3	Comprimento	�
152.4.4	Caminho Simples x Trajetória	�
152.4.5	Grafo Conexo	�
152.4.6	Caminhos abertos e fechados	�
152.4.7	Circuito e Ciclo	�
162.4.8	Algoritmo de Goodman	�
172.5	Localização de Centros (em grafos não valorados)	�
172.5.1	Distância	�
172.5.2	Pista	�
182.5.3	Excentricidade	�
182.5.4	Raio	�
182.5.5	Centro	�
192.5.6	Centro de um grafo dirigido	�
192.5.7	Localização de Centros de Emergência	�
222.6	Algoritmos e problemas clássicos com grafos	�
222.6.1	Algoritmo de Floyd	�
272.6.2	Algoritmo de Dijkstra	�
292.6.3	Grafos de Euler	�
292.6.4	Problema do Carteiro Chinês	�
332.6.5	Caminho e Circuito Hamiltoniano	�
332.6.6	Problema do Caixeiro Viajante	�
432.7	Busca em Grafo	�
432.7.1	Algoritmo Básico ou Busca Geral	�
452.7.2	Busca em Profundidade	�
482.7.3	Busca em Largura	�
512.8	Fluxo em Rede	�
523	Eficiência e Corretude de Algoritmos	�
523.1	Definições	�
523.1.1	O que é um algoritmo?	�
533.1.2	Instâncias de execução de algoritmos	�
533.1.3	Avaliação de Algoritmos	�
553.2	Notação O, Omega e Theta	�
553.2.1	Notação O	�
573.3	Crescimento assintótico de funções	�
584	Análise da Complexidade de Algoritmos	�
584.1	Estimativas de Tempo de Execução	�
584.2	Regras para Análise de Algoritmos	�
624.3	Relações de recorrência	�
�
�
Introdução
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 
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.
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.�
Teoria dos Grafos
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�, 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.
. 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 dodecaedro regular, de tal modo que cada um deles fosse visitado uma única vez. Para mais exemplos, consulte, por exemplo, Boaventura Neto, 1996.
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:
	
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.
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
Tipos de Grafos
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						 
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’
Ordem
A ordem de um grafo é definida por |V| = n. Ou seja, a ordem de um grafo é o número de vértices.
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.
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
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.
						V1 = {a.,b}
 a		 c			V2 = {c,d,e}
			 d	
				
	 b		 e
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.
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:
|V1| = |V2| = n.
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’
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.
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.
Custo do vértice pode significar capacidade, entradas, etc.
	 10km
				 8km 16km
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}
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.
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:
�
 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
�
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
	(
�
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
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
�
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
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
4
Caminho e Conexidade
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
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
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 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
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.
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.
Circuito e Ciclo
Um circuito é um caminho simples fechado.
Um ciclo é uma cadeia simples fechada. Exemplo:
		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”.
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.
Exemplo:
	 a		 b
 f		 e			1o. 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
Localização de Centros (em grafos não valorados)
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:
d(u,v)>=0 com d(u,v)=0 se e somente se u=v.
d(u,v) = d(v,u) ocorre apenas quando o grafo é não orientado;
d(u,v) + d(v,w) >= d(u,w)
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)
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.
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}.
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
raio = r(G) = 1
centro = {c}
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}
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.
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
�DT
	x1
	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) + DT
	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) + DT(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
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
�
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.
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: descobrirse 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
D0ij = (, 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
R0ij = 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 (Dk-1 ik + Dk-1 kj < Dk-1 ij) then
 Begin
 Dkij := Dk-1 ik + Dk-1kj;
 Rkij := Rk-1ik;
 End
 End;
 End;
End;
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 D011 + D011 < D011? 0 + 0<0? Não!
K=1, i=1, j=2		se D011 + D012 < D012? 0 + 5 < 5? Não!
K=1, i=1, j=3		se D011 + D013 < D013? 0 + ( < (? Não!
K=1, i=1, j=4		se D011 + D014 < D014? 0 + 3 < 3? Não!
K=1, i=1, j=5		se D011 + D015 < D015? 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 D021 + D011 < D021? ( + 0 < (? Não!
K=1, i=2, j=2		se D021 + D012 < D022? ( + 5 < 0? Não!
K=1, i=2, j=3		se D021 + D013 < D023? ( + ( < 3? Não!
K=1, i=2, j=4		se D021 + D014 < D024? ( + 3 < (? Não!
K=1, i=2, j=5		se D021 + D015 < D025? ( + ( < (? 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.
Continuando então, i é incrementado para 3. Temos então:
K=1, i=3, j=1		se D031 + D011 < D031? ( + 0 < (? Não!
K=1, i=3, j=2		se D031 + D012 < D032? ( + 5 < (? Não!
K=1, i=3, j=3		se D031 + D013 < D033? ( + ( < 0? Não!
K=1, i=3, j=4		se D031 + D014 < D034? ( + 3 < (? Não!
K=1, i=3, j=5		se D031 + D015 < D035? ( + ( < 5? Não!
Continuando, i é incrementado para 4. Temos então:
K=1, i=4, j=1		se D041 + D011 < D041? 1 + 0 < 1? Não!
K=1, i=4, j=2		se D041 + D012 < D042? 1 + 5 < 1? Não!
K=1, i=4, j=3		se D041 + D013 < D043? 1 + ( < (? Não!
K=1, i=4, j=4		se D041 + D014 < D044? 1 + 3 < 0? Não!
K=1, i=4, j=5		se D041 + D015 < D045? 1 + ( < 1? Não!
Continuando, i é incrementado para 5. Temos então:
K=1, i=5, j=1		se D051 + D011 < D051? ( + 0 < (? Não!
K=1, i=5, j=2		se D051 + D012 < D052? ( + 5 < 1? Não!
K=1, i=5, j=3		se D051 + D013 < D053? ( + ( < (? Não!
K=1, i=5, j=4		se D051 + D014 < D054? ( + 3 < 1? Não!
K=1, i=5, j=5		se D051 + D015 < D055? ( + ( < 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 D012 + D021 < D011? 5 + ( < 0? Não!
K=2, i=1, j=2		se D012 + D022 < D012? 5 + 0 < 5? Não!
K=2, i=1, j=3		se D012 + D023 < D013? 5 + 3 < (? Sim!!!!!!!!!!
K=2, i=1, j=4		se D012 + D024 < D014? 5 + ( < 3? Não!
K=2, i=1, j=5		se D012 + D025 < D015? 5 + ( < (? Não!
No momento em que eu achei um curto, então gero a minha matriz D1. 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.
Continuando temos:
K=2, i=2, j=1		se D022 + D021 < D021? 0 + ( < (? Não!
K=2, i=2, j=2		se D022 + D022 < D022? 0 + 0 < 0? Não!
K=2, i=2, j=3		se D022 + D023 < D023? 0 + 3 < 3? Não!
K=2, i=2, j=4		se D022 + D024 < D024? 0 + ( < (? Não!
K=2, i=2, j=5		se D022 + D025 < D025? 0 + ( < (? Não!
Continuando temos:
K=2, i=3, j=1		se D032 + D021 < D031? ( + ( < (? Não!
K=2, i=3, j=2		se D032 + D022 < D032? ( + 0 < (? Não!
K=2, i=3, j=3		se D032 + D023 < D033? ( + 3 < 0? Não!
K=2, i=3, j=4		se D032 + D024 < D034? ( + ( < (? Não!
K=2, i=3, j=5		se D032 + D025 < D035? ( + ( < 5? Não!
Continuando temos:
K=2, i=4, j=1		se D042 + D021 < D041? 1 + ( < 1? Não!
K=2, i=4, j=2		se D042 + D022 < D042? 1 + 0 < 1? Não!
K=2, i=4, j=3		se D042 + D023 < D043? 1 + 3 < (? Sim!!!!!
K=2, i=4, j=4		se D042 + D024 < D044? 1 + ( < 0? Não!
K=2, i=4, j=5		se D042 + D025 < D045? 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 D052 + D021 < D051? 1 + ( < (? Não!
K=2, i=5, j=2		se D052 + D022 < D052? 1 + 0 < 1? Não!
K=2, i=5, j=3		se D052 + D023 < D053? 1 + 3 < (? Sim!!!
K=2, i=5, j=4		se D052 + D024 < D054? 1 + ( < 1? Não!
K=2, i=5, j=5		se D052 + D025 < D055? 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
�
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ínimopra 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:
�
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
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].
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
	
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
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.
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.
�
 
 
 
�
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.
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.
�
�
�
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.
�
�
�
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.
�
�
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.
					 
					 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]
...
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
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.
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.
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”.
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 109 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 1017
	73 anos
	25
	42 milhoes
	6.2 x 1023
	470 milhoes de anos
Esse problema demonstra, portanto, que mesmo com os computadores potentes existentes atualmente, para alguns problemas não basta conseguir fazer um algoritmo para resolver um problema. O algoritmo deve ser eficiente.
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.
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 é 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
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. 
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’
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:
	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 não será o maior custo possível, pode acontecer de existir um roteiro com custo ainda menor. Por exemplo, neste caso um possível caminho heuleriano seria “abcdfea”, com custo 20 e outro seria “abcfdea”, com custo 24.
Exercício
1. O que é um grafo hamiltoniano?
2. Qual é a diferença entre o problema do carteiro chinês e o problema do caixeiro viajante?
3. Considere os grafos A e B abaixo. Para cada um eles, descubra um caminho hamiltoniano utilizando o algoritmo “vizinho mais próximo”.
		Grafo A					Grafo B
4. Considere os mesmos grafos A e B da questão anterior. Para cada um eles, descubra um caminho hamiltoniano utilizando o algoritmo “inserção do mais próximo”.
3. ALGORITMO INSERÇÃO DO MAIS DISTANTE
Este algoritmo consiste dos seguintes passos:
1. Escolher um vértice i qualquer.
2. Selecionar um vértice k mais afastado de i e criar um roteiro passando por k, ou seja, “i k i” 
3. Repetir até que todos os vértices do grafo sejam inseridos.
Considerando os vértices que já fazem parte do roteiro, verificar qual vértice não-inserido está mais próximo de cada vértice do roteiro. Forma-se então um conjunto Temp com vértices e suas distâncias.
Selecionar do conjunto Temp o vértice k com a maior distância.
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).
Inserir o vértice k entre x e y. 
Para exemplificar esse algoritmo, vamos considerar novamente o mesmo grafo anterior, reproduzido abaixo:
Passo 1: escolho o vértice a
Passo 2: O vértice adjacente a ‘a’ mais afastado são o ‘b’ e o ‘f’, com distância 4. Vou escolher o vértice ‘b’, por ser o primeiro. Formo então o roteiro “a b a”.
Passo 3:
Passo 3.1
Vértice a ( o mais próximo é o vértice ‘e’, com custo 2.
Vértice b ( o mais próximo é o vértice ‘f’, com custo 3.
Temp ( {(e,2), (f,3)}
Passo 3.2.
O vértice de Temp com a maior distância é o f, com distância 3.
Passo 3.3.
Aresta ab
Daf + dfb – dab = 4+3-4 = 3
Aresta ba
Dbf + dfa – dba = 3 + 4 -4 = 3
Como deu empate, escolho a primeira aresta, ‘ab’.
Passo 3.4.
Inserir o vértice ‘f’ no roteiro, entre a aresta ‘ab’.
Roteiro: “afba”.
Passo 3.1
Vértice a ( o mais próximo é o vértice ‘e’, com custo 2.
Vértice f ( o mais próximo é o vértice ‘e’, com custo 2
Vértice b ( o mais próximo é o vértice ‘c’, com custo 5.
Temp ( {(e,2), (e,2),(c,5)}
Passo 3.2.
O vértice de Temp com a maior distância é o ‘c’, com distância 5.
Passo 3.3.
Aresta af
Dac + dcf – daf = ( + 5 – 4 = (
Aresta fb
Dfc + dcb – dfb = 5 + 5 - 3 = 7
Aresta ba
Dbc + dca – dba = 5 + ( - 4 = (
A aresta que acrescenta menor custo é a fb.
Passo 3.4.
Inserir o vértice ‘c’ no roteiro, entre a aresta ‘fb’.
Roteiro: “afcba”.
Passo 3.1
Vértice a ( o mais próximo é o vértice ‘e’, com custo 2.
Vértice f ( o mais próximo é o vértice ‘e’, com custo 2
Vértice c ( o mais próximo é o vértice ‘d’, com custo 3
Vértice b ( todos os vértices adjacentes já foram inseridos.
Temp ( {(e,2), (e,2),(d,3)}
Passo 3.2.
O vértice de Temp com a maior distância é o ‘d’, com distância 3.
Passo 3.3.
Aresta af
Dad + ddf – daf = ( + 4 – 4 = (
Aresta fc
Dfd + ddc – dfc = 4 + 3 - 5 = 4
Aresta cb
Dcd + ddb – dcb = 3 + ( - 5 = (
Aresta ba
Dbd + dda – dba = ( + ( - 4 = (
A aresta que acrescenta menor custo é a fc.
Passo 3.4.
Inserir o vértice ‘c’ no roteiro, entre a aresta ‘fb’.
Roteiro: “afdcba”.
Passo 3.1
Vértice a ( o mais próximo é o vértice ‘e’, com custo 2.
Vértice f ( o mais próximo é o vértice ‘e’, com custo 2
Vértice d ( o mais próximo é o vértice ‘e’, com custo 4
Vértice c ( todos os vértices adjacentes já foram inseridos 
Vértice b ( todos os vértices adjacentes já foram inseridos.
Temp ( {(e,2), (e,2),(e,4)}
Passo 3.2.
O vértice de Temp com a maior distância é o ‘e’, com distância 4.
Passo 3.3.
Aresta af
Dae + def – daf = 2 + 2 – 4 = 0
Aresta fd
Dfe + ded – dfd = 2 + 4 - 4 = 2
Aresta dc
Dde + dec – ddc = 4 + ( - 3 = (
Aresta cb
Dce + deb – dcb = ( + ( - 3 = (
Aresta ba
Dbe + dea – dba = ( + 2 - 4 = (
A aresta que acrescenta menor custo é a af
Passo 3.4.
Inserir o vértice ‘e’ no roteiro, entre a aresta ‘af’.
Roteiro final : “aefdcba”.
4. HEURÍSTICA DE MELHORAMENTO 2-OPT
Vimos que os métodos anteriores nem sempre conseguem encontrar o melhor caminho possível. Em virtude disso, este algoritmo, na verdade, não é utilizado para encontrar um caminho hamiltoniano, mas sim para “melhorar” um caminho hamiltoniano já existente.
Assim, dado um grafo e um caminho hamiltoniano nesse grafo, este algoritmo tenta melhorar esse caminho trocando duas arestas do caminho por outras duas arestas. O algoritmo é basicamente o seguinte:
1. Considere uma matriz de distâncias de um grafo e um vetor contendo o caminho inicial.
2. Selecione duas arestas do caminho: (a,b) e (c,d).
2. Verifique se existem 2 arestas alternativas (x,y) (z,w) utilizando apenas os vértices ‘a’, ‘b’, ‘c’ e ‘d’ tal que o custo d(x,y)+d(z,w) seja menor do que o custo inicial d(a,b)+d(c,d)
Por exemplo, considere o grafo abaixo:
Vamos supor que, aplicando um método qualquer, o caminho encontrado tenha sido “a b c d e a”, com custo 21. O caminho, portanto, é composto das arestas (a,b), (b,c), (c,d), (d,e) e (e,a). 
Assim, escolhemos aleatoriamente as arestas (a,b) e (c,d) para serem trocadas. Vamos verificar então se as arestas (a,c) e (b,d) são melhores escolhas.
D(a,b) + d(c,d) = 4 + 5 = 9
D(a,c) + d(b,d) = 1 + 4 = 5
Verificamos, assim, que as novas arestas reduzem o custo do caminho. Vamos então, trocar as arestas, de forma que o novo caminho seja: “a c b d e a”, com custo 17.
Conforme a implementação, o algoritmo pode ser aplicado várias vezes, para verificar se não existe uma solução ainda melhor. Neste caso, por exemplo, outra alternativa, considerando o grafo original, seria trocar as arestas (e,a) e (b,c) pelas arestas (a,c) e (e,b). Vamos verificar como ficam os custos neste caso:
D(e,a) + d(b,c) = 5 + 3 = 8
D(a,c) + d(e,b) = 1 + 2 = 3
Portanto, fazemos a troca e o caminho final fica: “a,c, d, e, b, a”, com custo 16. Os grafos abaixo mostram os possíveis caminhos hamiltonianos.
5. HEURÍSTICA DE MELHORAMENTO 3-OPT�
A heurística 3-opt é praticamente idêntica à 2-opt, com a diferença de que, em vez de movermos apenas 2 arestas, movemos 3. Por exemplo, considerando o mesmo grafo anterior, poderíamos remover as arestas (a,b), (c,d) e (d,e) e inserir as arestas (a,d), (d,b) e (c,e). Neste caso o custo total seria 20, o que é mais vantajoso que os 21 iniciais. O caminho percorrido no grafo é exemplificado a seguir:
Tanto para a heurística 2-opt quanto para a 3-opt, repare que, embora algumas arestas tenham seu sentido modificado, a heurística não considera essas mudanças no algoritmo por estarmos considerando apenas grafos não dirigidos e, portanto, o custo não é alterado. No entanto, lembre-se que ao implementar o algoritmo é necessário fazer modificações no vetor que armazena o caminho.
Busca em GrafoAté agora, vimos que os grafos podem ser utilizados ajudar a solucionar diversos problemas, tais como encontrar o menor caminho entre dois pontos ou encontrar a melhor rota para passar por diversos pontos.
Outra possibilidade, então, é utilizar a representação na forma de grafos para a busca. Pode-se buscar um vértice específico ou um vértice que atenda a alguma características. Por exemplo, suponha que você tenha um grafo representando as cidades brasileiras e, em cada vértice do grafo, o número de habitantes. Você poderia fazer uma busca para tentar encontrar todas as cidades com menos de 5.000 habitantes. Ou então fazer uma busca para verificar se existe pelo menos alguma cidade com menos de 1.000 habitantes.
Mas qual é, então, o método mais eficiente para se fazer uma busca? Vejamos então alguns possíveis métodos:
Algoritmo Básico ou Busca Geral
Seja G um grafo conexo.
Escolhe-se um vértice qualquer como vértice inicial. Marca-se esse vértice como já visitado.
Repetir os seguintes passos até que a condição seja satisfeita ou todas as arestas tiverem sido exploradas:
2.1. Selecionar um vértice já visitado v que seja incidente a alguma aresta (v,w) não visitada. 
2.2. Marca-se a aresta (v,w) como visitada.
2.3. Se o vértice w ainda não tiver sido marcado, marca-se como visitado.
A condição de parada depende do objetivo do programa e, portanto, pode ser qualquer uma, tal como:
A distância percorrida é maior do que 10.000
Foi encontrado um vértice com valor 57.
Foi encontrado um vértice com o nome “x”.
Todos os vértices já foram percorridos.
Por exemplo, vamos supor que queremos fazer uma busca no grafo abaixo até que todos os vértices tenham sido visitados, de modo a fazer uma contagem da soma dos valores das arestas.
1. Iniciar com o vértice a.
 Vértices visitados = {a}.
 Arestas visitadas = {}
 Soma = 0
2. Escolho o vértice visitado ‘a’ e (aleatoriamente) a aresta não visitada (a,b).
 Vértices visitados = {a,b}
 Arestas visitadas = {(a,b)}
 Soma = 4
3. Escolho (aleatoriamente) o vértice visitado ‘b’ e a aresta não visitada (b,d).
 Vértices visitados = {a,b,d}
 Arestas visitadas = {(a,b),(b,d)}
 Soma = 9
4. Escolho o vértice visitado ‘a’ e a aresta não visitada (a,e).
 Vértices visitados = {a,b,d,e}
 Arestas visitadas = {(a,b),(b,d),(a,e)}
 Soma = 14
5. Escolho o vértice visitado ‘a’ e a aresta não visitada (a,d).
 Vértices visitados = {a,b,d,e} ( Note que o vértice já tinha sido visitado
 Arestas visitadas = {(a,b),(b,d),(a,e),(a,d)}
 Soma = 21
6. Escolho o vértice visitado ‘e’ e a aresta não visitada (e,f)
 Vértices visitados = {a,b,d,e,f}
 Arestas visitadas = {(a,b),(b,d),(a,e),(a,d),(e,f)}
 Soma = 26
7. Escolho o vértice visitado ‘b’ e a aresta não visitada (b,c).
 Vértices visitados = {a,b,d,e,f,c}
 Arestas visitadas = {(a,b),(b,d),(a,e),(a,d),(e,f),(b,c)}
 Soma = 32
8. Como todos os vértices já foram visitados, a condição de parada é alcançada e o algoritmo sai do laço.
Busca em Profundidade
A única diferença para o algoritmo básico é o critério para escolher o próximo vértice a ser visitado. Neste algoritmo, considera-se a cada iteração apenas os vértices já visitados que são incidentes a alguma aresta ainda não percorrida. Escolhe-se então aquele mais recentemente visitado.
Vamos implementar esse algoritmo de forma recursiva:
Definir uma pilha P;
Escolher um vértice qualquer r para servir de vértice inicial (raiz);
Prof(r).
Fim.
Procedimento P(v)
 4. Marcar r como já visitado;
 5. Colocar r na pilha P;
 6. Para w ( (+(v) (para todos os vértices w que pertencem aos sucessores de v)
 Se w não foi visitado então:
 7. Visitar(v,w);
 8. P(w);
 Senão se w pertence à pilha e ‘v’ e ‘w’ não são consecutivos na pilha então:
 9. Visitar(v,w);
 Fim-para 
 10. Retirar v da pilha P;
Fim-procedimento
Vejamos então como ficaria a busca utilizando como exemplo o mesmo grafo anterior, reproduzido a seguir:
1. Pilha P = {}
2. Vértice r = a
3. P(a).
4. Visitados = {a}
5. Pilha P = {a}
6. (+(a) = {b,d,e,f}
7. Visitar (a,b).
 8. P(b).
 4.Visitados = {a,b}
 5. Pilha P = {a,b}
 6. (+(b) = {a,c,d}
 Vértice ‘a’ - ‘a’ já é marcado e ‘a’ e ‘b’ são consecutivos na pilha.
	 Vértice ‘c’:
	 7. Visitar (b,c)
 8. P(c) 
4. Visitados = {a,b,c}
5. Pilha P = {a,b,c}
6. (+(c) = {b,d}
Vértice ‘b’ – ‘b’ já foi visitado e ‘b’ e ‘c’ são consecutivos na pilha
Vértice ‘d’:
7. Visitar (c,d)
8. P(d)
4. Visitados = {a,b,c,d}
5. Pilha P = {a,b,c,d}
6. (+(d) = {a,b,c,e}
Vértice ‘a’ – já foi visitado mas ‘a’ e ‘d’ não são consecutivos
 9. Visitar (d,a).
Vértice ‘b’ – já foi visitado mas ‘b’ e ‘d’ não são consecutivos
 9. Visitar (d,b)
Vértice ‘c’ – já foi visitado e são consecutivos
Vértice ‘e’:
7. Visitar (d,e).
8. P(e)
4. Visitados = {a,b,c,d,e}
5. Pilha P = {a,b,c,d,e}
6. (+(e) = {a,d,f}
Vértice ‘a’ – já visitado mas ‘a’ e ‘e’ não consecutivos
 9. Visitar (e,a)
Vértice ‘d’ – já visitado e são consecutivos
Vértice ‘f’ – não visitado:
7. Visitar (e,f).
8. P(f).
4. Visitados = {a,b,c,d,e,f}
5. Pilha = {a,b,c,d,e,f}
6. (+(f) = {a,e}
Vértice ‘a’ – visitado mas não consecutivos
 9. Visitar (f,a)
Vértice ‘e’ – visitado mas consecutivos
Como já visitei todos os sucessores de ‘f’, chego ao fim do laço ‘para’. Saindo do laço então:
10. Pilha = {a,b,c,d,e}
Como cheguei ao fim do procedimento, volto para o ponto onde foi feita a última chamada recursiva. Ou seja, a chamada a P(f).
Neste ponto, eu estava verificando os sucessores de ‘e’. Como todos os sucessores já foram verificados, chego novamente ao fim do laço ‘para’. Então:
10. Pilha = {a,b,c,d}.
Chego ao fim do procedimento e, portanto, volto para o ponto anterior onde foi feita uma chamada recursiva. Ou seja, a chamada a P(e).
Neste ponto, eu estava verificando os sucessores de ‘d’. Como todos os sucessores já foram verificados, chego novamente ao fim do laço ‘para’. Então:
10. Pilha = {a,b,c}.
Chego ao fim do procedimento e, portanto, volto para o ponto anterior onde foi feita uma chamada recursiva. Ou seja, a chamada a P(d).
Neste ponto, eu estava verificando os sucessores de ‘c’. Como todos os sucessores já foram verificados, chego novamente ao fim do laço ‘para’. Então:
10. Pilha = {a,b}.
Chego ao fim do procedimento e, portanto, volto para o ponto anterior onde foi feita uma chamada recursiva. Ou seja, a chamada a P(c).
Neste ponto, eu estava verificando os sucessores de ‘b’. Notem que os sucessores de ‘b’ são {a,c,d}. No entanto, quando eu estava verificando ‘c’ foi feita a chamada recursiva. Portanto, o vértice ‘d’ ainda não foi verificado.
Vértice ‘d’: O vértice ‘d’ já foi visitado, e ‘d’ não pertence mais à pilha.
Agora sim todos os sucessores de ‘b’ já foram verificados. Chego então ao fim do laço ‘para’. Então:
10. Pilha = {a}.
Chego ao fim do procedimento e, portanto, volto para o ponto anterior onde foi feita uma chamada recursiva. Ou seja, a chamada a P(b).
Neste ponto, eu estava verificando os sucessores de ‘a’. Notem que no primeiro sucessor de ‘a’ já foi feita uma chamada recursiva. Portanto, ainda não foram verificados os vértices ‘d’, ‘e’ e ‘f’.
Vértice ‘d’: O vértice já foi visitado e não pertence mais à pilha.
Vértice ‘e’: O vértice já foi visitado e não pertence mais à pilha.
Vértice ‘f’: O vértice já foi visitado e não pertence mais à pilha.
Agora todos os sucessores de ‘a’ já foram verificados. Chego então ao fim