TEORIA DE GRAFOS

&

A

B

C

D

CONCEITOS BÁSICOS:

GrafoGrafo orientado

CONCEITOS BÁSICOS:

SubgrafoVértices

adjacentesArestas adjacentesLaçoPseudografoGrau de um vérticePonto isoladoArestas

múltiplasMultigrafoGrafo

conexoGrafo desconexoCompon

entePonte

Grafo não orientado ou digrafo

CONCEITOS BÁSICOS:

Caminho

CONCEITOS BÁSICOS: Circu

ito

LEONHARD EULER (1707-1783)

CONCEITOS BÁSICOS:

Caminho de Euler

CONCEITOS BÁSICOS:Circuito de Euler

AS PONTES DE KÖNIGSBERG

SERÁ POSSIVÉL PERCORRER TODAS

AS PONTES PASSANDO UMA ÚNICA VEZ POR

CADA UMA DELAS?

EULER PROVOU QUE NÃO

1º TEOREMA DE EULER

Se um grafo possuir vérticesde grau impar não possui nenhum circuito de EulerSe um grafo for conexo e todos os

seus vértices forem de grau par então possui

pelo menos um circuito de Euler

2º TEOREMA DE EULERSe um grafo possuir mais de dois vértices de grau impar então não possui nenhum caminho de EulerSe um grafo for conexo e

possuir apenas dois vértices de grau impar

então possui pelo menos um caminho de

Euler.Qualquer que seja esse caminho ele terá de

começar num desses vértices e terminar no

outro

3º TEOREMA DE EULER

A soma dos graus de todos os vértices de

1 grafo é igual ao dobro do seu número

de arestas O número de vértices de grau

impar tem de ser par

Conjunto de regras mecânicas que, quando utilizadas

correctamente, levam à resposta de um determinado problema

ALGORITMO

ALGORITMO DE FLEURY 

Ver se o grafo é conexo e se todos os seus vértices

são de grau parComeçar num vértice qualquer Percorrer uma

aresta se :

Esta não for uma ponte para a parte não atravessada do

grafoNão existir outra

hipótese

Assinalar as arestas consoante a ordem com que forem percorridas

Quando não for possivel continuar, parar, o

percurso esta terminado.

ALGORITMO DE FLEURY

AB

C

D E F

G

H

I

JK

L M

NO

P

AB

C

D E F

G

H

I

JK

L M

NO

P

AB

C

D E F

G

H

I

J

KL

M

NO

P

1

2 3 4

56

78

910

1112

13141516 17

1819

20

21

22

23

2425

26

A B C D

E F G H

I J K L

Não tem nem caminho nem circuito de Euler

Como encontrar o percursomais económico??6 vértices de

grau ímpar

A B C D

E F G H

I J K L

VÉRTICES DE GRAU

ÍMPAR PARComo vamos fazer?

Eulerização de grafos

E F G H

I J K L

A B C D

7 arestas duplicadas

5 arestasduplicadas

A B C D

E F G H

I J K L

TEM UM CIRCUITO DE EULER

TODOS OS

VÉRTICES TÊM GRAU PAR

APLICANDO O ALGORITMO DE FLEURY,

ENCONTRAMOS UM DOS MUITOS CIRCUITOS DE EULER

A B C D

E F G H

I J KL

SOBREPONDO O CIRCUITOAO GRAFO ORIGINAL

A B C D

E F G H

I J KL

cicuitoCaminho

A B C D

E F G H

I J K L

E DCBA F GH IJKL E BC FJKGH

Semi-eulerização de grafos

1º-transformar os vértices de grau ímpar em vértices de grau par

2º- Descobrir um circuito de euler no grafo eulerizado

3º- sobrepor a este circuito o grafo original

CIRCUITO MAIS ECONÓMICOCAMINHO MAIS ECONÓMICO

excepto 2

caminho

caminho

EULERIZAR O GRAFOSEMI-EULERIZAR O GRAFO

Exemplo:Recolha do lixo de um bairro

Exemplo:Recolha do lixo de um bairro

O carro do lixo terá de repetir Algumas ruas já limpas Quantas?

9

Circuito (caminho ) de Hamilton

Percorre todos osVértices de um grafoSem repetir nenhum

A B

CD

E circuito de

Hamilton

circuito de Euler

Tem

Não tem Tem

Não tem Tem

F

G

Como sabemos se um grafo tem ou nãoum circuito (caminho) de Hamilton?

Tem circuitos Hamiltonianos

Por exemplo:Grafo completo bipartido n*n

Grafo com pontes

Não tem nenhum circuito hamiltonianoet

c

Grafos completos

F

E

D

C

B

A

Grau de cada vértice: n-1

nK

Nº total de arestas:

Reportório completo deCircuitos Hamiltonianos

12n

(n-1)! Circuitos hamiltonianos

4kA

D

C

B

A,B,C,D,AA,B,D,C,A A,C,B,D,AA,C,D,B,AA,D,B,C,AA,D,C,B,A

B,C,D,A,BB,D,C,A,B B,D,A,C,BB,AC,D,BB,C,A,D,BB,A,D,C,B

Fixando um vértice como referência,encontramosTodos os circuitos de Hamilton existentes no grafo

Em que consiste este tipo de problemas?

São essencialmente,

problemas da vida real em que se

pretende encontrar um percurso de

menor valor

Exemplo1: “O problema das 5 cidades”

A

B

CD

E

133€185€

199€

174€

121€

152€

119€150€120€

200€

Qual será a sequência menos expendiosa para o Sr.Francisco?

Exemplo 2: “Exploração do nosso sistema solar"

TerraGanymede

Callisto

Io

Mimas

Titan

4.70.6

8.1

3.2

1.5

0.8

5.15.2

1.1

5.7

5.9

3.6

5.6

8.2

3.1

Qual será o percurso mais curto?

Método1:Fazer uma lista de todos os

circuitos possíveis;

Calcular o custo total de cada circuito;

Escolher o circuito com menor custo.

Tabela1: Circuito Custo total Imagem Hamiltoniano em espelho

1 A,B,C,D,E,A 185+121+174+199+133= 812 A,E,D,C,B,A 2 A,B,C,E,D,A 185+121+120+199+152= 777 A,D,E,C,B,A 3 A,B,D,C,E,A 185+150+174+120+133= 762 A,E,C,D,B,A 4 A,B,D,E,C,A 185+150+199+120+119= 773 A,C,E,D,B,A 5 A,B,E,C,D,A 185+200+120+174+152= 831 A,D,C,E,B.A 6 A,B,D,E,C,A 185+200+199+174+119= 877 A,C,E,D,B,A 7 A,C,B,D,E,A 119+121+151+199+133= 722 A,E,D,B,C,A 8 A,C,B,E,D,A 119+121+200+199+152= 791 A,D,E,B,C,A 9 A,C,E,B,D,A 119+174+150+200+133= 776 A,D,B,E,C,A10 A,C,E,B,D,A 119+120+200+150+152= 741 A,D,B,E,C,A11 A,D,B,C,E,A 152+150+121+120+133= 676 A,E,C,B,D,A12 A,D,C,B,E,A 152+174+121+200+133= 780 A,E,B,C.D.A

Circuito Hamiltoniano obtido:

A

B

CD

E

133€185€

199€

174€

121€

152€

119€150€120€

200€

Circuito de menor custo : A, D, B, C, E, ACusto total: 152€+150€+121€+120€+133€ = 676€

Método 2:Começar em A;

Partir para a cidade cujo custo é menor;

Repetir o processo até retornar a A.

Circuito Hamiltoniano Obtido :

A

B

CD

E

133€185€

199€

174€

121€

152€

119€150€120€

200€

Circuito : A, C, E, D, B, ACusto total do circuito : 119€+120€+199€+150€+185€=773€

O sr.Francisco expande o seu negócio.

Usando o método 2 levará apenas alguns minutos a construir o circuito;

Mas:

Para usar o método 1 teremos de verificar :

9! = 362880 circuitos.

Como resolver esta situação?

É-nos cedido um super computador capaz de construir:

10 bilões de circuitos por

segundo

3.0 x 10^17 circuitos por ano

Tabela 2: Número Número de Tempo de vértices circuitos Hamiltonianos de pesquisa

16 1,307,674,368,000 2 minutos 17 2.1*1013 35 “ 18 3.6*1014 10 horas

19 6.4*1015 7 1/2 dias 20 1.2*1017 140 dias 21 2.4*1018 7 1/2 anos 22 5.1*1019 160 anos 23 1.1*1021 3500 anos 24 2.6*1022 82.000 anos 25 6.2*1023 2,000,000 anosO número de circuitos Hamiltonianos

cresce desproporcionadamente à medida que acrescentamos um vértice.

Algoritmo ineficiente: O seu uso na prática é limitado, uma vez que só pode ser usado quando o número de vértices é pequeno.Exemplo:

Método 1 – Algoritmo “ Força bruta”.

Algoritmo eficiente: O número de passos necessários cresce em proporção ao tamanho do problema. Exemplo: Método 2 – Algoritmo “Vizinho mais próximo”.

Em que consiste um algoritmo aproximado?

Usaremos o termo “algoritmo aproximado”para descrever qualquer algoritmo que produza soluções que estão, na maior parte das vezes, razoavelmente perto da solução perfeita.

Algoritmo3: O “vizinho mais próximo” repetido Partir de um determinado vértice e aplicar

o algoritmo “vizinho mais próximo”; Calcular o custo total obtido; Repetir o processo para os vértices

restantes; Escolher o circuito de menor custo; Rescreever , se necessário, esse circuito

começando no vértice de referência.

Circuito Hamiltoniano de menor custo

A

B

CD

E

133€185€

199€

174€

121€

152€

119€150€120€

200€

Circuito: A, E, D, B, C, ACusto total: 133€+199€+150€+121€+119€ = 722€

Algoritmo 4: “Aresta de menor valor” Começa-se na aresta de menor valor, qualquer que seja.

Segue-se para a aresta de menor valor seguinte e assim sucessivamente, tendo em conta as seguintes restrições:

a) Não permitir que os circuitos se formem(a não ser no final);

b) Não permitir que três arestas se juntem num ponto;

Quando não houver mais vértices para ligar, fechar o circuito.

Construção do circuito Hamiltoniano

A

B

CD

E

133€185€

199€

174€

121€

152€

119€150€120€

200€

X

X

Circuito: A, C, E, B, D, ACusto total: 119€+120€+200€+150€ 152€ = 741€

Trabalho realizado por:Ana Sofia ClaroLuisa Maria da Cruz Félix Sara da Silva Nogueira