Aulas-UFBA-1

8/14/2019 Aulas-UFBA-1

1/139

DCC/UFBA MAT156

Adolfo Almeida Duran

2005


2/139

Adolfo Duran - 2005 Teoria dos Grafos

Apresentao

O curso / motivao Horrio /sala

Programa do curso

Referncias Avaliao E-mail : [email protected]
mailto:[email protected]:[email protected]


3/139


Porque estudar Grafos

Importante ferramenta matemtica com aplicaoem diversas reas do conhecimento Gentica, qumica, pesquisa operacional,

telecomunicaes, engenharia eltrica, redes decomputadores, conexo de vos areos, restries deprecedncia, fluxo de programas, dentre outros

Utilizados na definio e/ou resoluo de

problemas

Introduo


4/139


Porque estudar Grafos

Em computao: estudar grafos mais umaforma de solucionar problemas computveis

Os estudos tericos em grafos, buscam odesenvolvimento de algoritmos mais eficientes.


5/139


O que so Grafos

Diagrama - Corresponde a soma de pontos e linhas, onde

os pontos apresentam alguma informao e as linhasindicam o relacionamento entre dois pontos quaisquer

Ferramenta de modelagem Abstrao matemtica que representa situaes reais

atravs de um diagrama.


6/139Adolfo Duran - 2005 Teoria dos Grafos

As pontes de Knigsberg

Um pouco de histria

possvel sair de uma das ilhas, passar umanica vez por cada uma das pontes e retornar aoponto de origem ?




Resolvido em 1736 por Leonhard EulerNecessrio um modelo para representar o

problema

Abstrao de detalhes irrelevantes: rea de cada ilha Formato de cada ilha Tipo da ponte, etc.




Euler generalizou o problema atravs de ummodelo de grafos



As pontes de Knigsberg Euler mostrou que no existe o trajeto proposto

utilizando o modelo em grafos Verifique nos grafos abaixo se o trajeto proposto possve


10/139Adolfo Duran - 2005 Teoria dos Grafos 1

O problema das 3 casas

possvel conectar os 3 servios s 3 casassem haver cruzamento de tubulao?

gua luz telefone

A teoria

dosgrafosmostraque no

possvel



Quantascores so

necessriaspara colorir omapa doBrasil, sendoque estadosadjacentesno podem

ter a mesmacor?



Questes sobre o caminho mnimo

De forma a reduzir seus custos operacionais,uma empresa de transporte de cargas desejaoferecer aos motoristas de sua frota ummecanismo que os auxilie a selecionar o melhor

caminho (o de menor distncia) entre quaisquerduas cidades por ela servidas, de forma a quesejam minimizados os custos de transporte.



Modelagem com grafos

Estamos interessados em objetos e nas relaes entreeles

Quem so eles nos problemas apresentados?

Como representar graficamente?



Modelagem com grafosNo problema das casas

Vrtices so casas e servios Arestas so as tubulaes entre casas e servios

No problema da colorao de mapas Vrtices so estados Arestas relacionam estados vizinhos

No problema do caminho mais curto Vrtices so as cidades Arestas so as ligaes entre as cidades


16/139

Adolfo Duran - 2005 Teoria dos Grafos 1

Trs desenvolvimentos isolados despertaramo interesse pela rea

Formulao do problema das 4 cores (DeMorgan 1852).

Qual a quantidade mnima de cores para colorir um

mapa de tal forma que pases fronteirios possuamcores diferentes?Apresenta-se um exemplo em que 3 cores no sosuficientes. Uma prova de que 5 cores suficiente foiformulada. Conjecturou-se ento que 4 cores seriamsuficientes. Esta questo ficou em aberto at 1976quando Appel e Haken provaram para 4 cores


17/139


Trs desenvolvimentos isolados despertaram o interessepela rea

Problema do ciclo Hamiltoniano (Hamilton 1859)

Existem n cidades. Cada par de cidades pode ser

adjacente ou no arbitrariamente. Partindo de umacidade qualquer, o problema consiste em determinar umtrajeto que passe exatamente uma vez em cada cidadee retorne ao ponto de partida.


18/139


Trs desenvolvimentos isolados despertaram

o interesse pela rea

Teoria das rvores- Kirchoff (1847) - problemas de circuitos

eltricos- Cayley (1857) - Qumica Orgnica

f


19/139


Dois tipos de elementos

Vrtices ou nsArestas

Definies

v1

v2v3 v4

v5

v6

G f Si l


20/139


G = (V,E)

V um conjunto finito no-vazio de vrtices E um conjunto finito de arestas

|V| o nmero de vrtices representado porn, se n=|V|

|E| o nmero de arestas representado porm, isto m=|E|

Cada aresta e pertencente ao conjunto E ser denotada pelo

par de vrtices (x,y) que a forma

Dizemos que os vrtices x e y so extremos (ouextremidades) da aresta e.

Grafo Simples


21/139


G = (V,E)


22/139


Dois vrtices x e y so ditos adjacentes ou vizinhos seexiste uma aresta e unindo-os.

Os vrtices u e v so ditos incidentes na aresta e, seeles so extremos de e.

Duas arestas so adjacentes se elas tm ao menos umvrtice em comum.

A aresta e=(x,y) incidente a ambos os vrtices x e y.


23/139


v1

v2v3 v4

v5 v6

e1V = {v1, v2, v3, v4, v5, v6}

E = {(v1,v2),(v1,v3),(v1,v4),(v2,v4),(v3,v4),(v4,v5)}

Grafo simples

e1 incidente a v4 e v5


24/139


Exemplo

Exerccio

Desenhe a representao geomtrica do seguintegrafo:

V = {1,2,3,4,5,6};E ={(1,2),(1,3),(3,2),(3,6),(5,3),(5,1),(5,6),(4,6),(4,5),(6,1),(6,2),(3,4)}

Mais definies


25/139


Lao uma aresta formada por um par de vrtices idnticos

Arestas mltiplas ou paralelas Quando existe mais de uma aresta entre o mesmo par

de vrtices.

Multigrafo Um grafo que permite a existncia de arestas mltiplas

Mais definies


26/139


Exerccio

Defina formalmente o grafo abaixo e identifique osconceitos de lao, aresta mltipla e multigrafo nomesmo:


27/139


Grau de um vrtice

Grau de um vrtice v (grau(v)) o nmero de arestasque incidem em v.

O grau de um vrtice v tambm pode ser definidocomo o nmero de arestas adjacentes a v.

Obs.: Um lao conta duas vezes para o grau de umvrtice

Grau(b) = 3

Grau(d) = 2Grau(a) = 2


28/139


Qualquer vrtice de grau zero um vrtice isolado

Qualquer vrtice de grau 1 umvrtice terminal

Um vrtice mpartem um nmero mpar de arestas

Um vrtice par, tem um nmero par de arestas


29/139


Grafo Regular(k-regular) todos os vrtices tm o mesmo grau (k)

v1

v2v4

v3

Seqncia de graus de um grafo consiste em

escrever em ordem crescente o grau de todosos seus vrtices


30/139


v1

v2v3 v4

v5 v6

e1

V6 um vrtice isolado,grau(v6)=0

V5 um vrtice terminal,grau(v5)=1

V2 um vrtice par,grau(v2)=2

V1 um vrtice mpar,grau(v1)=3

Seqncia de graus = 0,1,2,2,3,4


31/139


Exerccio

Identificar no grafo abaixo os vrtices isolados,terminais, impares, pares e a seqncia de graus dografo:

ReflexoO que podemos concluir sobre a soma dos graus deum grafo?


32/139


Soma dos graus de um grafo:

O resultado sempre par, e corresponde formula

abaixo:

A prova inspirada no Lema do Aperto de Mos que diz:

Se vrias pessoas se apertam a mo o nmero total demos apertadas tem que ser par. Precisamente porque

duas mos esto envolvidas em cada aperto.

S


33/139


Soma dos graus de um grafo:

Em grafos, cada aresta contribui duas unidades para ocmputo geral do grau dos vrtices, pois cada aresta

possui dois extremos. Portanto, a soma total par e duasvezes o nmero de arestas do grafo.

Se o grafo forregularde grau r, a soma dos graus dos

vrtices tambm igual a r vezes o nmero de vrtices.

A d d f


34/139


A soma dos graus de um grafo sempre par:

Quando o grafo regular de grau r, temos:


35/139


Corolrio

Em qualquer grafo, o no

de vrtices com grau mpar deveser PAR

Prova

Para a soma ser par, o primeiro somatrio tem que gerarum resultado par, portanto |Vmpar| par.


36/139


Teorema da Amizade I

Em toda cidade, com pelo menos dois habitantes,residem duas pessoas com o mesmo nmero deamigos na cidade.

Exerccio

Modele o teorema acima usando grafos e prove-o.


37/139


Modelando o problema

V = pessoas.E = relao de amizade.No existe a necessidade de laos nem dearestas multiplas, ento o grafo simples.

O enunciado do teorema pode ser representadopela seguinte afirmao:

Se G(V,E) simples, com |V|

2, implica queexistem x e y distintos pertencentes a V, tal quegrau(x) = grau(y).

Demonstrao


38/139


Demonstrao

Se G simples, ento, 0 grau(v) n - 1, onde n=|V|.

Alm disso, se existe v, tal que grau(v)= 0, ento noexiste v, tal que grau(v) = n-1.

Por outro lado, se existe v, tal que grau(v)= n - 1, ento

no existe v, tal que grau(v) = 0.Suponha que no existe vrtice v onde grau(v)= 0.

Ento o grau de qualquer vrtice do grafo ter um dos

valores do conjunto {1, ... , n-1}.

D t ( t )


39/139


Demonstrao (cont.)

Ou seja, existem n-1 valores para o grau de n vrtices,

logo existem vrtices v e w distintos onde grau(v) =grau(w).

Analogamente, suponha que no existe vrtice v onde

grau(v)= n-1. Ento o grau de qualquer vrtice do grafoter um dos valores do conjunto {0, ... , n-2}.

Ou seja, existem n-1 valores para o grau de n vrtices,

logo existem vrtices v e w distintos onde grau(v) =grau(w).

D t t di


40/139


Demonstrao por contradio

Suponha que no existam vrtices x e y, tais que grau(x)

= grau(y), ou seja, para todo x e y pertencentes a V,grau(x) diferente de grau(y).

Ento, para vrtices distintos temos:grau(v1) = 0, grau(v2) = 1, grau(v3) = 2, ...., grau(vn) = n -1

O que representa uma contradio.

Outros tipos de grafos


41/139


Grafo Nulo (vazio)

Grafo cujo nmero de arestas zero. Ou, grafo regularde grau zero.

p g

1

4

3

2

Nn um grafo nulo com n vrtices

Exemplo: N4

V={1,2,3,4}; E={ }.

G f C l t


42/139


Grafo Completo

Grafo simples em que quaisquer vrtices distintos doisa dois so adjacentes. Ou, grafo regular de grau n-1,onde n=|V|.

Kn

um grafo completo com n vrtices.

Exemplo: K4

Quantas arestas tem o K ?


43/139


Quantas arestas tem o Kn?

Veja que |E| = ( r * |v| ) / 2, onde r o grau e v o nmero de

vrtices.

Logo |E| = (( n - 1 ) n ) / 2

Podemos provar tambm com anlise combinatria. Onmero de arestas igual ao nmero de combinaes den vrtices dois a dois.

Cn,m

= n! / ( m! (n m)! )

Complemento de um grafo


44/139



Seja G um grafo simples com um conjunto de vrticesV.G complemento de G se

V = Ve

dois vrtices so adjacentes em G, se e

somente se, no o so em G

C l t d f


45/139



C l t d f


46/139



Exerccio:

D exemplos que confirmem as propriedadesacima

Propriedade 1

Um grafo regular tem complemento regular

Propriedade 2

O complemento deKnNn

Grafo Bipartido


47/139


Grafo Bipartido

Um grafo dito ser bipartido quando seu conjunto

de vrtices Vpuder ser particionado em doissubconjuntos V1 e V2, tais que toda aresta de G une

um vrtice de V1 a outro de V2.

1

4

3

2

5

6

V1

V2

Grafo Bipartido


48/139


Grafo BipartidoSejam os conjuntos H={h | h um homem} e M={m |

m um mulher} e o grafo G(V,A) onde:

V= HU MA = {(v,w) | (v He w M) ou (v Me w H) e }

Grafo Bipartido Completo


49/139


Grafo Bipartido Completo

um grafo bipartido em V1 e V2, sendo que cada

elemento de V1 adjacente a cada elemento de V2.

K3,3

V1

V2

Subgrafo


50/139


Subgrafo

Um grafo Gs(Vs, As) dito ser subgrafo de um grafo

G(V,A) quando VsVeAsA. O grafo G2, porexemplo, subgrafo de G1

G1 G2

Subgrafo Prprio


51/139


Subgrafo Prprio

Um subgrafo G2 dito prprio, quando G2 subgrafo distinto de G1

Subgrafos podem ser obtidos atravs daremoo de arestas e vrtices.

Subgrafo Induzido


52/139


Subgrafo Induzido

Se G2 um subgrafo de G1 e possui toda a aresta (v, w)

de G1 tal que ambos, v e w, estejam em V2, ento G2 o

subgrafo induzido pelo subconjunto de vrtices V2.

3 2

1

4 5

V1= {1,2,3,4,5}

G1

3 2

1

4

V2= {1,2,3,4}

G2

V2 induz G2

Clique


53/139


Clique

Denomina-se clique de um grafo G a um subgrafo

(induzido) de G que seja completo

Conjunto Independente de Vrtices (C I V )


54/139


Conjunto Independente de Vrtices (C. I. V.)

Chama-se C.I.V. a um conjunto induzido de G que seja

um grafo nulo

O tamanho de um clique ou de um C.I.V. igual cardinalidade de seu conjunto de vrtices.

Grafo Rotulado


55/139


Grafo Rotulado

Um grafo G(V,A) dito ser rotulado em vrtices (ou

arestas) quando a cada vrtice (ou aresta) estiverassociado um rtulo

Grafo Valorado


56/139


Grafo Valorado

Um grafo G(V,A) dito ser valorado quando existe

uma ou mais funes relacionando Ve/ouA comum conjunto de nmeros.

V= {v | v uma cidade com aeroporto}A = {(v,w,t) | }

Isomorfismo de Grafos


57/139



Dois grafos G1 e G2 so isomorfos se existe uma

correspondncia um a um entre os vrtices de G1 e

G2, com a propriedade de que o nmero de arestas

unindo os vrtices em G1 igual ao nmero de

arestas unindo os vrtices correspondentes em G2.

Isomorfismo de Grafos (em outras palavras)


58/139


Isomorfismo de Grafos (em outras palavras)

Sejam dois grafos G1(V

1,A

1) e G

2(V

2,A

2). Um

isomorfismo de G1 sobre G2 um mapeamentobijetivo f: V

1 V

2tal que {x,y} A

1se e somente se

{f(x),f(y)}A2, para todo x,y V

1.

Funo:{ (a2), (b 1), (c 3), (d 4), (e 6), (f 5) }

Isomorfismo de Grafos (exemplo)


59/139


so o s o de G a os (e e p o)

f(u) = azul, f(v) = lils, f(w) = vermelho,f(x) = verde, f(y) = amarelo, f(z) = rosa

u v w

x y z



60/139


Preserva:

Simetria: G1 G2 G2 G1Reflexividade: G1 G1Transitividade: G1 G2 e G2 G3 G1 G3

Proposies vlidas se G1 G2

G1 e G2 tm o mesmo nmero de vrtices

G1 e G2 tm o mesmo nmero de arestasG1 e G2 tm a mesma sequncia de graus

Grafos Orientados ou Dgrafos


61/139


Um dgrafo D(V,A) um conjunto finito no vazio V de

vrtices, e um conjunto A de pares ordenados deelementos de V. Chamamos o conjunto A de arcos

Digrafo Simples

um digrafo que no possui laos e os arcos so todosdistintos

Mais sobre dgrafos


62/139


Conjunto finito no vazio de vrtices

Conjunto finito no vazio de arestas Arestas so chamadas de arcos Um arco (v,w) passa a servw

D = (V,A)

V = {a,b,c,d)

A = {ac,ba,bc,cb,cd,cd)

a d

b c

Dgrafos Simples


63/139


g pTodos os arcos so distintos

No existem auto-laos Para obter o grafo correspondente a um dgrafo

Eliminar as direes dos arcos

No necessariamente um grafo correspondente aum dgrafo simples um grafo simples

Apresente um exemplo de um dgrafo

simples que quando transformadoem grafo, no simples

Os vrtices de um dgrafo possuem:G d d d h i


64/139


Grau de entrada: nmero de arcos que chegam no vrtice(grauent(v))

Grau de sada: nmero de arcos que partem do vrtice(grausai(v)) Da mesma forma:

Sequncia de graus de entrada

Sequncia de graus de sada

Proposio

grauent(vi) = grausai(vi) = | A |

Os dgrafos so isomrficos se:


65/139


Existe um isomorfismo entre os respectivos grafoscorrespondentes

Preserva a ordem dos vrtices em cada arco

a d

b c

a d

b c

Os grafos abaixo no so isomorfos

Unio

Operaes com grafos


66/139


Unio

Considere 2 grafos G1(V1,E1) e G2(V2,E2) onde V1 e V2

so conjuntos distintos A unioG1 G2 formada pelo grafo com conjunto de

vrtices V1 V2 e conjunto de arestas E1 E2

Exemplo

G: V1={1,2} e E1={(1,2)}

H: V2={3,4} e E2={ }GH: V={1,2,3,4} e E={(1,2)}

Soma

Considere 2 grafos G1(V1 E1) e G2(V2 E2) onde V1 e V2


67/139


Considere 2 grafos G1(V1,E1) e G2(V2,E2) onde V1 e V2so conjuntos distintos

A soma G1 + G2 formada por G1 G2 e de arestasligando cada vrtice de G1 a cada vrtice de G2.

Exemplo

G: V1 = {1,2} e E1 = {(1,2)}

H: V2 = {3,4} e E2 = { }G + H: V={1,2,3,4} e E={(1,2),(1,3),(1,4),(2,3),(2,4)}

Exemplo


68/139


1 2

G H

3 4

GH G + H

1 2

3 4

1 2

3 4

Unio e Soma


69/139


Podem ser aplicadas a qualquer nmero finito de grafos

So operaes associativas

So operaes comutativas

Remoo de Aresta


70/139


Se e uma aresta de um grafo G, denota-se G-e o grafo

obtido de G pela remoo da aresta e

Genericamente, se F um conjunto de arestas em G,denota-se G-F ao grafo obtido pela remoo das arestasem F.

Remoo de Vrtice


71/139


Se v um vrtice de um grafo G denota-se por G-v o

grafo obtido de G pela remoo do vrtice vconjuntamente com as arestas incidentes a v.

Genericamente denota-se G-S ao grafo obtido pelaremoo dos vrtices em S, sendo S um conjunto

qualquer de vrtices de G.

Contrao de aresta


72/139


Denota-se porG/e o grafo obtido pela contrao da aresta

e. Isto significa removere de G e unir suas duasextremidades v,w de tal forma que o vrtice resultanteseja incidente s arestas originalmente incidentes a v e w.

Representao de grafos


73/139


Embora seja conveniente arepresentao de grafos atravs dediagramas de pontos ligados por

linhas, tal representao inadequada se desejamos armazenar

grandes grafos em um computador

Uma maneira simples de armazenar grafos,


74/139


listando os vrtices adjacentes a cada vrtice do

grafo

u: v,y

v: u,y,ww: v,x,yx: w,yy: u,v,w,x

u

y v

x w

Matriz de adjacncia


75/139


Se G um grafo com vrtices {1,2,3,...,n}, sua matrizde adjacncia a matriz n X n cujo elemento ij onmero de arestas ligando o vrtice i ao vrticej

Matriz de incidncia


76/139


Se G um grafo com vrtices {1,2,3,...,n} e arestas

{1,2,3,...,m}, sua matriz de incidncia a matriz n X mcujo elemento ij o nmero de vezes em que o vrticei incidente arestaj.

Grafo ConexoConectividade


77/139


Um grafo G(V,A) dito ser conexo se ele nopode ser expresso como a unio de dois grafos.

G1 G2

Grafo desconexo


78/139


Um grafo G(V,A) dito ser desconexo se ele podeser expresso pela unio de dois outros grafos.

Componente conexa


79/139


Um grafo G(V,A) desconexo formado por pelo menosdois subgrafos conexos, disjuntos em relao aos vrtices

Cada um destes subgrafos conexos dito ser umacomponente conexa de G.

Vrtice de corteUm vrtice dito ser um vrtice de corte se


80/139


Um vrtice dito ser um vrtice de corte sesua remoo (juntamente com as arestas aele conectadas) provoca uma reduo naconectividade do grafo.

X2 um vrtice de corte

PonteUma aresta dita ser uma ponte se sua


81/139


Uma aresta dita ser uma ponte se suaremoo provoca uma reduo naconectividade do grafo.

(X1,X4) uma ponte

Grafo cclico (ou grafo circuito)Outros tipos de grafos


82/139


Um grafo conectado que regular de grau 2

um grafo cclico (= ciclo)

Cn um grafo cclico com n vrtices

C6

Grafo caminhoO grafo obtido a partir de C atravs da


83/139


O grafo obtido a partir de Cn atravs da

remoo de um aresta o grafo caminho emn vrtices, Pn

C5 P5

Grafo rodaO grafo obtido a partir de C atravs da


84/139


O grafo obtido a partir de Cn-1 atravs da

ligao de cada vrtice a um novo vrtice v um grafo roda em n vrtices, Wn

Corresponde soma de N1 com Cn-1

C5 W6

Grafos cbicosSo grafos regulares de grau 3


85/139


So grafos regulares de grau 3

O primeiro deles conhecido comoGrafo de Petersen

Cadeia (= passeio)Cadeias, caminhos, ciclos...


86/139


( p ) Uma cadeia (walk) uma seqncia qualquer de

arestas adjacentes que ligam dois vrtices. O conceito de cadeia vale tambm para grafos

orientados, bastando que se ignore o sentido da

orientao dos arcos.A seqncia devrtices (x6, x5, x4, x1)

um exemplo decadeia

Cadeia elementar (= caminho =path)Uma cadeia dita ser elementar se no passa duas


87/139


Uma cadeia dita ser elementarse no passa duas

vezes pelo mesmo vrtice

1 2

3 4

1 2

3 4

Cadeia de tamanho 21 2 4

Cadeia de tamanho 33 1 4 2

Cadeia simples (= trilha = trail)U d i dit i l d


88/139


Uma cadeia dita ser simples se no passa duas

vezes pela mesma aresta (arco).

1 2

3 4

1 2

3 4

Cadeia de tamanho 41 2 4 1 3

Cadeia de tamanho 51 2 4 1 3 2

CaminhoU i h d i l t d


89/139


Um caminho uma cadeia na qual todos os arcos

possuem a mesma orientao. Aplica-se, portanto,somente a grafos orientados

A seqncia de vrtices(x1, x2, x5, x6, x3)

um exemplo decaminho

CicloU i l d i i l f h d ( ti


90/139


Um ciclo uma cadeia simples e fechada (o vrtice

inicial o mesmo que o vrtice final).

A seqncia de vrtices(x1, x2, x3, x6, x5, x4, x1)

um exemplo de ciclo

Exemplos de ciclos


91/139


1 2

3 4

1 2

3 4

Ciclo de tamanho 31 2 4 1

Ciclo de tamanho 31 2 3 1

Circuito


92/139


Um circuito um caminho simples e fechado. Aplica-se, portanto, somente a grafos orientados

A seqncia de vrtices(x1, x2, x5, x4, x1)

um exemplo decircuito

Grafo fortemente conexo No caso de grafos orientados, um grafo dito ser

fortemente conexo (f-conexo) se todo par de vrtices est


93/139


fortemente conexo (f-conexo) se todo par de vrtices estligado por pelo menos um caminho em cada sentido

ou seja, se cada par de vrtices participa de um circuito. Isto significa que cada vrtice pode ser alcanvel

partindo-se de qualquer outro vrtice do grafo.

Componente fortemente conexaUm grafo G(V,A) que no fortemente conexo


94/139


g ( ) qformado por pelo menos dois subgrafos fortementeconexos, disjuntos em relao aos vrtices

Cada um destes

subgrafos dito seruma componentefortemente conexa deG

Um grafo conectado G(V,A) dito sereuleriano se existe um ciclo que contm todas

Grafos Eulerianos


95/139


euleriano se existe um ciclo que contm todas

as arestas de G.

cadeia simples fechada que no passa 2 vezes

pela mesma aresta etermina no mesmovrtice

Grafo semi-eulerianoUm grafo conectado no-euleriano G semi-


96/139


Um grafo conectado, no euleriano G semi

euleriano se existe uma cadeia simplescontento todas as arestas de G

Teorema (Euler 1736)Um grafo conectado G euleriano se e somente se


97/139


go grau de cada vrtice de G par

Prova:

Ida: Seja G um grafo euleriano. Logo ele contm um cicloeuleriano. Por cada ocorrncia de vrtice desse ciclo,existe uma aresta que chega nesse vrtice e outra que saidesse vrtice. Como toda aresta faz parte do ciclo, isto ,

nenhuma aresta fica fora do ciclo, necessariamente onmero de arestas por cada vrtice par.

Volta: Suponhamos que todos os vrtices possuemgrau par. Seja vi um vrtice do grafo. Tentemos, a partir

de v construir uma cadeia que no passa duas vezes


98/139


de vi, construir uma cadeia que no passa duas vezes

pela mesma aresta, e at que no seja possvelcontinuar. Como todos os vrtices possuem um graupar, sempre ser possvel entrar e sair de um vrtice. Anica exceo o vrtice vi onde a cadeia vai terminar.

Se essa cadeia, que chamaremos C1, contm todas asarestas de G, temos um ciclo euleriano. Seno,retiramos de G todas as arestas que fazem parte de C1.

No grafo resultante G', todos os vrtices tambmpossuem grau par e necessariamente um deles fazparte de C1, seno o grafo no seria conexo.

Volta (cont.): Recomeamos o mesmo processo com ografo G', partindo de um vrtice comum com C1,

obtendo assim um novo ciclo C A figura abaixo


99/139


obtendo assim um novo ciclo C2. A figura abaixo

mostra que dois ciclos que tm um vrtice em comumpodem formar um ciclo nico: chegando no vrticecomum em um dos dois ciclos, continuamos o percursono outro ciclo. Continuando esse processo,

necessariamente obteremos um ciclo nico que contmtodas as arestas de G.

Algoritmo de HierholzerAlgoritmo para a construo de um ciclo euleriano

id ti d d t d E l


100/139


sugerido a partir da prova do teorema de Euler

Comece em qualquer vrtice u e percorra aleatoriamenteas arestas ainda no visitadas a cada vrtice visitado atfechar um ciclo

Se sobrarem arestas no visitadas, recomece a partir deum vrtice do ciclo j formado

Se no existem mais arestas no visitadas, construa ociclo euleriano a partir dos ciclos formados, unindo-os apartir de um vrtice comum

Algoritmo de HierholzerAlgoritmo para a construo de um ciclo euleriano



101/139





102/139


possvel sair de uma das ilhas, passar uma

nica vez por cada uma das pontes e retornar aoponto de origem ?



103/139


Como nem todos os vrtices tm grau par, o grafono euleriano. Logo, impossvel atravessar

todas as pontes uma s vez e voltar ao lugar departida

Corolrio IUm grafo conectado G e leriano se e somente se


104/139


Um grafo conectado G euleriano se e somente se

ele pode ser decomposto em ciclos

Corolrio IIUm grafo conectado G semi-euleriano se esomente se ele possui exatamente 2 vrtices de

grau mpar

Algoritmo de FleuryAlgoritmo para a construo de um ciclo euleriano

em um grafo euleriano


105/139



Comece em qualquer vrtice u e percorra asarestas de forma aleatria, seguindo sempre asseguintes regras:

I apague as arestas depois de passar por elasII se aparecer algum vrtice isolado, apague-otambmIII passe por uma ponte somente se no houveroutra alternativa

Algoritmo de FleuryAlgoritmo para a construo de um ciclo euleriano



106/139



Um grafo G(V,A) dito serhamiltoniano seexiste um ciclo que passa exatamente uma vez

Grafos Hamiltonianos


107/139


em cada um dos vrtices de G

no hamiltonianohamiltoniano

Grafo semi_hamiltoniano


108/139


Um grafo G(V,A) dito ser semi-hamiltoniano se no hamiltoniano e existe uma cadeia que passaexatamente uma vez em cada um dos vrtices de G

Hamiltoniano Semi-hamiltoniano

nohamiltoniano

Grafo hamiltoniano


109/139


No existe uma caracterizao para identificar grafoshamiltonianos como existe para os eulerianos

A busca de tal caracterizao um dos maioresproblemas ainda no solucionados da teoria dosgrafos

Grafo hamiltoniano


110/139


Muito pouco conhecido dos grafos hamiltonianos

A maioria dos teoremas existentes so da forma: SeG possui arestas suficientes, ento G hamiltoniano

Ciclo hamiltoniano em grafos completos


111/139


Todo grafo completo, que contm maisde 2 vrtices hamiltoniano

Seja v1,v2,...,vn os vrtices de G. Comoexiste uma aresta entre qualquer par devrtices, possivel, a partir de v1 percorreressa sequncia at v

ne voltar para v

1

Teorema (Dirac 1952)Uma condio suficiente, mas no necessria,

para que um grafo simples G com n (>2) vrtices


112/139


para que um grafo simples G com n (>2) vrticesseja hamiltoniano que o grau de todo vrtice de g

seja n/2

O grafo abaixo, hamiltoniano mas no respeita acondio do teorema de Dirac

Teorema (Ore 1960)Uma condio suficiente, mas no necessria, para

que um grafo simples G com n (>2) vrtices seja


113/139


que um grafo simples G com n (>2) vrtices sejahamiltoniano que a soma dos graus de cada par

de vrtices no adjacentes seja no mnimo n

Permite identificar mais grafos hamiltonianos que oanterior, mas demora muito para efetuar os clculos. Uma

busca por tentativa e erro pode ser mais eficiente emalguns casos

O adjetivo "hamiltoniano" deve-se ao matemticoirlands Sir William Rowan Hamilton (1805-1865).Diz-se que ele inventou um jogo que envolve um


114/139


dodecaedro (slido regular com 20 vrtices, 30arestas e 12 faces).Hamilton rotulou cada vrtice do dodecaedro com onome de uma cidade conhecida.

O objetivo do jogo era que o jogador viajasse "aoredor do mundo" ao determinar uma viagem circularque inclusse todas as cidades exatamente uma vez,com a restrio de que s fosse possvel viajar de

uma cidade a outra se existisse uma aresta entre osvrtices correspondentes.

A figura abaixo mostra um grafo querepresenta este problema, ou seja os vrticese arestas de um dodecaedro


115/139


e arestas de um dodecaedro.

Como explorar um grafoAlguns Problemas


116/139


Como obter um processo sistemtico para caminharpelos vrtices e arestas de um grafo?

Como caminhar no grafo de modo a visitar todos os

vrtices e arestas evitando repetiesdesnecessrias de visitas a um mesmo vrtice ouaresta?

Que recursos adicionais so necessrios?

Como explorar um grafoNecessidade de marcar quando um vrtice e umaaresta j foram visitados ou no


117/139


aresta j foram visitados ou no

Busca Geral G(V,E)1. Escolher e marcar um vrtice inicial;

2. Enquanto existir algum vrtice v marcado e incidente auma aresta (v,w), no explorada, efetuar:

a) escolher o vrtice v;b) explorar a aresta (v,w). Se w no marcado ento

marcar w.

Algoritmo Geral

O problema do Caminho mais curto

Um motorista deseja encontrar o caminho, mais curtopossvel entre duas cidades do Brasil


118/139


possvel, entre duas cidades do Brasil

Caso ele receba um mapa das estradas de rodagem doBrasil, no qual a distncia entre cada par adjacente decidades est exposta, como poderamos determinar umarota mais curta entre as cidades desejadas?

Uma maneira possvel enumerar todas as rotaspossveis que levam de uma cidade outra, e entoselecionar a menor.

O problema do menor caminho consiste emdeterminar um menor caminho entre um vrticede origem s V e todos os vrtices vde V.


119/139


Menor caminho com destino nico: encontrar um

caminho mais curto para um vrtice destino v Menor caminho para um par: encontrar umcaminho mais curto para um determinado par devrtices ue v

Menor caminho para todos os pares: encontrar umcaminho mais curto de upara v, para todos e quaisquerpares ue v

Variantes do problema

O problema do Caminho mais curtoUma maneira mais eficiente:

Percorra o grafo, partindo do vrtice de origem s,


120/139


associando a cada vrtice um nmero l(v) indicando amenor distncia entre s e v.

Isso significa que quando chegamos ao vrtice v, nafigura abaixo, l(v) ser min ( l(u)+6 , l(x)+4 )

6

5

u

3

s

6

2 7

v

x y

412

3

Calculando os pesos:


121/139


6

5

u

3

s

6

2 7

v

x y

412

3

0

5

3

11

9

Como obter um caminho mnimo partindo de s para y


122/139


6

5

u

3

s

6

2 7

v

x y

412

3

0

5

3

11

9

Outra possibilidade:


123/139


6

5

u

3

s

6

2 7

v

x y

412

3

0

5

3

11

9

O algoritmo de Dijkstra

O algoritmo de Dijkstra identifica, a partir de um vrticedo grafo, qual o custo mnimo entre esse vrtice e


124/139


do grafo, qual o custo mnimo entre esse vrtice etodos os outros do grafo.No incio, o conjunto S contm somente esse vrtice,chamado origem. A cada passo, selecionamos noconjunto de vrtices sobrando, o que o mais perto da

origem.Depois atualizamos, para cada vrtice sobrando, a suadistncia em relao origem. Se passando pelo novovrtice acrescentado, a distncia fica menor, essa

nova distncia que ser memorizada


Suponhamos que o grafo representado por uma matrizde adjacncia onde temos o valor se no existe aresta


125/139


jentre dois vrtices.

Suponhamos tambm que os vrtices do grafo soenumerados de 1 at n, isto , o conjunto de vrtices N= {1, 2, ..., n}.

Utilizaremos tambm um vetor D[2..n] que conter adistncia que separa todo vrtice do vrtice 1 (o vrtice

do grafo que o vrtice 1 escolhido arbitrariamente).


funoDijkstra(L = [1..n, 1..n]: grafo): vetor[2..n]


126/139


C:= {2,3,...,n} {Implicitamente S= N- C}Parai:= 2 atn:

D[i]:= L[1,i]

Repetirn-2vezes:v:= Elemento de Cque minimiza D[v]C:= C - {v}Para cada elemento wde C:

D[w] := min(D[w],D[v]+ L[v,w])

RetornarD

Exemplo


127/139


Passo v C DIncio - {2,3,4,5} [50,30,100,10]1 5 {2,3,4} [50,30,20,10]

2 4 {2,3} [40,30,20,10]3 3 {2} [35,30,20,10]


Da maneira descrita, obtemos o custo do caminhomnimo para qualquer vrtices, mas no obtemos o


128/139


caminho mnimo.Para identificar esse caminho mnimo, s acrescentarmais um vetor P[2..n], onde P[v] indica o vrtice queprecede vno caminho mais curto.

Para isso, primeiro devemos inicializar esse vetor.

Segundo, no mesmo momento que o vetor D

atualizado, atualizamos tambm o vetorP.

O algoritmo de Dijkstra para o caminho mnimo

funoDijkstra(L = [1..n, 1..n]: grafo): vetor[2..n]C:= {2,3,...,n}


129/139


Parai:= 2 atn:D[i]:= L[1,i]P[i]:= 1

Repetirn-2vezes:v:= Elemento de Cque minimiza D[v]C:= C - {v}Para cada elemento wde C:

Se D[w] > D[v]+ L[v,w]ento

D[w] := D[v]+ L[v,w]P[w] := v

RetornarP

Exemplo


130/139


Passo v C D PIncio - {2,3,4,5} [50,30,100,10] [1,1,1,1]1 5 {2,3,4} [50,30,20,10] [1,1,5,1]

2 4 {2,3} [40,30,20,10] [4,1,5,1]3 3 {2} [35,30,20,10] [3,1,5,1]

O algoritmo de Dijkstra para o caminho mnimo

Vemos que o estado final do vetor P [3,1,5,1].Para saber qual o caminho mais curto entre os


131/139


vrtices 1 e 2, procuramos o valor na posio 2desse vetor (no esquea que P e D so indexados apartir de 2).O vetor indica que o ltimo vrtice antes do vrtice 2

o vrtice 3.Repetimos de novo o mesmo processo para ver ocaminho mais curto entre 1 e 3. No vetor, na posio3, temos o valor 1, que a origem.

Ento, o caminho mais curto 1,3,2.

O problema do carteiro chins

Problema discutido pelo matemtico chins Mei-Ku Kuan


132/139


Um carteiro deseja entregar suas cartas, percorrendo amenor distncia possvel e retornando ao ponto departida

Ele deve passar por cada estrada pelo menos uma vez,mas deve evitar passar por muitas estradas mais de umavez.

O problema do carteiro chins

O problema pode ser reformulado em termos de umgrafo valorado onde o grafo corresponde rede de


133/139


estradas e o valor de cada aresta corresponde aocomprimento da estrada.

Assim, devemos buscar uma cadeia fechada de

tamanho mnimo que inclua cada aresta do grafo pelomenos uma vez.

Se o grafo for euleriano??

O problema do carteiro chinsSe o grafo for euleriano, basta buscar um ciclo euleriano(algoritmo de Fleury)


134/139


Se o grafo no euleriano?Para ilustrar a soluo, vamos considerar um grupoespecial de grafos, onde exatamente 2 arestas tm graumpar

A

F

B C

D

E

8 14 10

53

6

4

5

9

O problema do carteiro chinsJ que os vrtices B e E so os nicos que tm graumpar, podemos encontrar uma cadeia semi-euleriana deB at E passando por cada aresta exatamente uma vez


135/139


A fim de retornar ao ponto de partida, cobrindo a menordistncia possvel, s encontrar o menor caminho de Eat B (EF A B)

A

F

B C

D

E

8 14 10

53

6

4

5

9

O problema do carteiro chinsA soluo do problema dada combinando o menorcaminho com a cadeia semi-euleriana


136/139


Note que, fazendo essa combinao, obtemos um grafoeuleriano

A

F

B C

D

E

8 14 10

53

6

4

5

9

O problema do caxeiro viajante

Um caxeiro viajante deseja visitar um dado grupo decidades e retornar ao ponto de partida, percorrendo a


137/139


menor distncia possvel

Esse problema pode ser formulado em termos de grafosvalorados

O objetivo encontrar um ciclo hamiltoniano com omenor peso possvel em um grafo valorado completo

O problema do caxeiro viajante

Um algoritmo possvel calcular a distncia de todos ospossveis ciclos hamiltonianos e escolher o menor


138/139


C

B E

D

7 3 5

6

9

8

A

62

48

No grafo ao lado, amenor rota seria

AB D E C Atotalizando umadistncia de 26

O problema do caxeiro viajanteCom mais de 5 cidades, a soluo anterior passa a ficarmuito complicada...


139/139


Por exemplo, com 20 cidades a quantidade de possveisciclos hamiltonianos (19!)/2, o que daproximadamente 6 x 1016

No se conhecem algoritmos eficientes para resolveresse problema

Existem algoritmos eursticos que do soluesaproximadas

Documents

Aulas-UFBA-1