Instituto Superior de Educac~ao
Departamento de Ci^
encias e Tecnologia
Licenciatura em Ensino de Matematica
Trabalho de Fim de Curso
Introduc~ao a Teoria dos Grafos e Aplicac~oes
Ant
onio Furtado
Orientadora: Doutora Tetyana Goncalves
2007/2008
Instituto Superior de Educac~ao
Departamento de Ci^
encia e Tecnologia
Licenciatura em Ensino de Matematica
Trabalho de Fim de Curso
Introduc~ao a Teoria dos Grafos e Aplicac~oes
Ant
onio Furtado
Trabalho Cientco apresentado no ISE para obtenc~ao do grau
de Licenciado em Ensino de Matematica, sob orientac~ao da Prof.
Doutora Tetyana Goncalves
O Juri
Presidente
Orientadora
Arguente
ISE, aos ................................ de 2008
Agradecimentos
Agradeco a Professora Doutora Tetyana Goncalves, minha orientadora, pelos
sabios conhecimentos, entusiasmo, atenc~ao que sempre me dedicou. A minha
prezada famlia, minha namorada, os meus amigos, pelo carinho e amizade
que foram decisivos no meu empenho durante todos esses anos de estudos.
Com apreco e innita estima agradeco ao Nilson, Anibal, Jair, Edmilson e
a todos que s~ao muitos pela amizade e incansavel ajuda na lida do dia-a-dia e
muito especialmente na elaboraca~o do presente trabalho. Pude compartilhar
momentos indeleves em companhia de colegas, amigos, docentes e a todos
vos um muito obrigado pela forca e encorajamento que sempre me deram.
i
Sumario
Agradecimentos
i
Introduc~ao
1
1 Conceitos Basicos
4
1.1
1.2
1.3
1.4
Grafos . . . . . . . . . . . . . . . . .
Digrafos . . . . . . . . . . . . . . . .
Subgrafo . . . . . . . . . . . . . . . .
Representac~ao de grafos por matrizes
1.4.1 Matriz de Adjac^encia . . . . .
1.4.2 Matriz de Incid^encia . . . . .
1.5 Isomorsmo . . . . . . . . . . . . . .
1.6 Exerccios . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Caminhos e conectividade
2.1
2.2
2.3
2.4
Caminhos . . . . .
Conexidade . . . .
Caminhos de Euler
Exerccios . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
4
7
9
9
10
11
13
14
17
.
.
.
.
.
.
.
.
.
.
.
.
3 Caminhos mais curtos
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
18
20
24
26
3.1 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 27
4 Tipos de Grafos
32
4.1 Grafos Bipartido . . . . . . . . . . . . . . . . . . . . . . . . . 32
ii
4.2 Arvores
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.1 Arvore
suporte Mnima . . . . . . . . . . . . . . . . . . 39
4.3 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5
Aplicac~oes
42
5.1 Problemas Propostos e Resolvidos . . . . . . . . . . . . . . . . 42
Consideraco~es Finais
50
Refer^encias Bibliogracas
51
iii
Introduc~ao
Estruturas que podem ser representadas por grafos est~ao em toda parte e
muitos problemas de interesse pratico podem ser formulados como quest~oes
sobre certos grafos.
A origem da Teoria dos Grafos e, em geral, associada ao problema das pontes
de Konigsberg. Parte desta cidade localizava-se em duas ilhas do rio Pregel
as quais estavam ligadas as margens e uma a outra atraves de 7 pontes, conforme a Figura. Os habitantes queriam encontrar um trajecto (com partida
e chegada a um mesmo lugar) que lhes permitisse atravessar apenas uma vez
cada uma das pontes.
Figura 1: Pontes de Konigsberg em 1736, e respectivo multigrafo.
Este problema foi resolvido por Euler 1 , que provou a inexist^encia de tal
percurso, modelando atraves dum multigrafo.
1 matem
atico
suco Leonhard Euler (1707-1783)
1
Um problema semelhante foi formulado e resolvido (em 1857) pelo Hamilton
2
. Este problema, que consiste em percorrer todos os vertices do dodecaedro
representado na Figura 2, passando uma unica vez em cada um, com partida
e chegada no mesmo vertice foi designado por viagem a volta do mundo.
Figura 2:
Outro problema, tambem bastante antigo, relacionado com a Teoria dos
Grafos, diz respeito a coloraca~o de mapas. Com este problema, pretendia-se
saber qual o menor numero de cores necessarias para pintar um mapa de
modo que n~ao existam pases, com fronteira comum, pintados da mesma cor.
Desde cedo se conjecturou que 4 cores bastariam para resolver este problema.
Estes problemas e muitos outros como: Problemas de colocaca~o de sinais
de sentido proibido e o estabelecimento de percursos alternativos, a sequ^encia
de ruas que um carteiro deve percorrer para entregar a correspond^encia, os
percursos a efectuar pelos carros de recolhas de lixo pelas ruas das cidades,
as rondas dos polcias e muitos outros podem ter uma soluca~o mais eciente
usando conceitos de grafos.
Esta teoria cobre um vasto campo de aplicaco~es: Fsica, Qumica, Biologia, Sociologia, Economia, Gest~ao, Engenharias, Matematica, etc.
2 matem
atico
irland^es Sir William Hamilton (1805-1865)
2
Por ser praticamente impossvel abordar todos os conteudos e aplicac~oes
da Teoria dos Grafos neste trabalho centramos nos seguintes objectivos:
Recolha e estudo dos fundamentos da Teoria dos Grafos;
Selecca~o, sugest~ao e apresentaca~o dos problemas de aplicac~oes diversas
que envolvem a tematica escolhida;
Constituica~o (elaborac~ao) de um documento de apoio na iniciaca~o dos
estudos ligados com "grafos".
Desse modo, sugerimos um documento de apoio, de consulta para os
interessados neste tema, para um seminario sobre a Teoria dos Grafos
3
Captulo 1
Conceitos Basicos
1.1 Grafos
Denic~ao 1.1 Chama-se grafo a um par ordenado G = (V; E ) constitudo
por um conjunto nito1 de v
ertices (ou nos) V (G) e, um conjunto nito
de arestas E (G), de tal forma que, cada aresta e esta associada a um par
de vertices distintos v e v chamados de n
os extremos de e, e arestas
i
j
diferentes tem nos extremos diferentes.
Seja e 2 E (G) (uma aresta) e v ; v 2 V (G) (dois vertices) escreve-se
e = fv ; v g = fv ; v g designando que e e uma aresta denida por v e v .
i
i
j
j
j
i
i
j
Denic~ao 1.2 O numero de vertices e arestas de um grafo e designado por
ordem e dimens~ao do grafo, e escreve-se jGj = jV (G)j; kGk = jE (G)j
respectivamente.
A gura 1.1 representa um grafo de ordem jV (G)j = 7 e dimens~ao
kE (G)k = 9.
V (G) = fv1 ; v2 ; v3 ; v4 ; v5 ; v6 ; v7 g
E (G) = ffv1 ; v2 g; fv2 ; v3 g; fv3 ; v4 g; fv4 ; v5 g; fv5 ; v6 g; fv6 ; v1 g; fv7 ; v1 g; fv7 ; v3 g; fv7 ; v5 gg
1 Tamb
em
existem grafos innitos mas neste trabalho so e considerado grafos nitos
4
Figura 1.1: Exemplo de um grafo
Denic~ao 1.3 Dois vertices dizem-se adjacentes se e so se denem uma
aresta. Uma aresta que liga um vertice a si proprio e designada por lacete
(laco). Se num grafo existir mais do que uma aresta entre dois vertices este
e designado por multigrafo.
Figura 1.2: Multigrafo
Figura 1.2 representa um multigrafo com laco no vertice v1 , e arestas
paralelas entre os vertices v2 e v3
Denic~ao 1.4 Uma aresta e de um grafo qualquer diz-se incidente sobre
um vertice se este for um dos seus nos extremos.
Denic~ao 1.5 Dene-se grau (ou val^encia) de um vertice v , como sendo
o numero das arestas incidentes sobre o respectivo vertice, representa-se por
deg(v) . Um vertice diz-se mpar ou par consoante o seu grau seja um
numero mpar ou par, respectivamente.
5
Obs: Note-se que um lacete incide duas vezes sobre o mesmo vertice pelo que
conta duas vezes para efeito do calculo do grau do vertice respectivo.
Um vertice v e dito isolado se deg (v ) = 0.
Denic~ao 1.6 Um grafo G diz-se p-regular se 8v
(no caso de p = 3 estes grafos se designam por
i
2 V (G) : deg(v ) = p
cubicos).
i
Teorema 1.1 Em qualquer grafo (multigrafo) a soma dos graus dos seus
vertices e igual a duas vezes o numero das suas arestas.
Demonstrac~ao:
Proceder-se-a por induc~ao sobre o numero de arestas do grafo: denote-se por
p(n) a armaca~o de que a soma dos graus de todos os vertices de um grafo
com n arestas e igual a 2n.
1. Se o grafo n~ao tem qualquer aresta, ent~ao o grau de qualquer dos seus
vertices e zero e a soma dos graus de todos os vertices e zero. Assim,
p(0) e uma proposica~o verdadeira.
2. Suponha-se que para um dado k 2 N se verica p(k 1) , isto e, que a
soma dos graus de todos os vertices de um grafo G com k 1 arestas
e igual a 2k 2. Considere-se agora um grafo G0 com k arestas. Para
obter G0 a partir de G a unica coisa que e necessario fazer e acrescentar
a G uma aresta e = fa; bg . Este acrescento aumenta o grau do vertice
a de uma unidade e o grau do vertice b de uma unidade: ent~ao, ao
passar de G para G0 por adica~o da aresta e a soma dos graus de todos
os vertices de G0 aumenta 2 unidades fazendo com que a soma dos graus
de todos os vertices de G0 seja igual a 2k.
Logo para qualquer k 2 N se tem p(k 1) ) p(k). Portanto pelo princpio
de induc~ao nita, a armaca~o do teorema e valida para todo k 2 N .
6
1.2 Digrafos
Denic~ao 1.7 Dene-se grafo orientado ou digrafo ("directed graph")
como um par ordenado D = (V; E ) em que V (D) e um conjunto nito de
vertices e, E (D) um conjunto nito de arestas dirigidas (arcos) de tal forma
que cada arco esta associado a um vertice inicial v e um terminal v . Arcos
i
j
diferentes tambem tem vertices inicial e/ou terminal diferentes.
Figura 1.3: Digrafo
A gura 1.3 representa um digrafo de ordem jDj = 6 = jV (D)j e dimens~ao
kDk = 9 = jE (D)j.
Obs: Num digrafo escreve-se e = (v ; v ) para signicar que e e um arco de
v para v , e e = (v ; v ) 6= (v ; v ) . Neste caso diz-se que v e adjacente
a v . Alem disso a aresta e e dita emergente do vertice v e, e incidente
sobre v .
i
i
j
i
j
j
j
i
i
j
i
j
Denic~ao 1.8 O grau de sada (emerg^encia) d (v) de um vertice v em
um digrafo D e o numero de arcos emergentes de v e o grau de entrada
(incid^encia) d+(v) e o numero de arcos incidentes em v.
Denic~ao 1.9 Um digrafo D e p-regular se para qualquer vertice de D,
existir um numero p 2 N; p 0 tal que, d+ (v ) = d (v ) = p.
i
i
Teorema 1.2 Seja D um digrafo de ordem p e dimens~ao q, comV = fv1 v g.
X
p
Ent~ao,
d+ (v ) =
X
p
i
i=1
p
d (v ) = q
i
i=1
7
Denic~ao 1.10 Dizemos que um digrafo D e simetrico, se sempre que
(u; v ) 2 E (D), ent~ao (v ; u) 2 E (D) .
Figura 1.4: Digrafos simetricos
Denic~ao 1.11 Um digrafo D e dito assimetrico se sempre que
(u; v ) 2 E (D) ) (v ; u) 2= E (D) .
Assim, digrafo assimetrico tem a propriedade que todo par de vertices e
ligado por, no maximo, um arco.
Denic~ao 1.12 Um grafo orientado em que todo par de vertices e ligado por
exactamente um arco e chamado um
torneio
Figura 1.5: Digrafos assimetricos: Torneio e n~ao torneio
Denic~ao 1.13 Um grafo que n~ao possua arestas multiplas nem lacos diz-se
simples.
8
Figura 1.6: Grafos simples
1.3 Subgrafo
Denic~ao 1.14 Um subgrafo do grafo G = (V; E ) e um grafo G0 = (V 0 ; E 0 )
tal que, V 0 (G0 ) V (G) e E 0 (G0 ) E (G). Pode-se escrever G0 G , e dizer
que G contem G0 . Se G0 G e G0 contem todas as arestas fv ; v g 2 E (G)
com v ; v 2 V 0 (G0 ) , ent~ao G0 e um subgrafo induzido de G. Escreve-se
G0 = G[V 0 ] e l^e-se: G0 e o subgrafo de G induzido por V 0 .
i
i
j
j
Denic~ao 1.15 Seja G = (V ; E ) um grafo e, G0 um subgrafo de G, tal que,
G0 = (V; E 0 ). A G0 chama-se grafo parcial de G.
Considere grafo G da gura 1.6 com dois subgrafos G1 ,G2 . G1 e um subgrafo
induzido de G . Pode-se obter subgrafos eliminando arestas ou vertices de
um grafo. Se v e um vertice, o subgrafo G0 = G v e obtido removendo-se
o vertice e as arestas incidentes sobre v .
1.4 Representac~ao de grafos por matrizes
Trabalhando com grafos nitos as vezes deparamos com grafos de uma grande
dimens~ao. Nestas situac~oes estudar o grafo atraves da sua representaca~o
graca pode n~ao ser o metodo mais ecaz. Assim, surge a necessidade de
procura de outros meios para o estudo dos mesmos. Uma das ideias consiste
em representaca~o de grafos pelas matrizes.
9
1.4.1
Matriz de Adjac^
encia
Denic~ao 1.16 Seja G = (V; E ) um grafo (digrafo D = (V; E )) qualquer,
onde jGj = n (jDj = n), a matriz de adjac^
encia A = [a ] e construda
n
do seguinte
( modo:
a =1
A =
a =0
ij
G
ij
( fv ; v g 2 E (G) A
( fv ; v g 2= E (G)
i
j
D
i
(
=
ij
Figura 1.7:
A matriz de adjac^encia do graco da gura 1.7 e:
A
G
0
0
B
B
1
B
B
=B 0
B
B
@0
1
0
1
0
1 1
0
1
0
1
1
0
0
1
0
0
1
1
1
0
0
1
C
C
C
C
C
C
C
A
A matriz de adjac^encia de um grafo e simetrica .
Figura 1.8:
10
a =1
a =0
ij
j
n
ij
( (v ; v ) 2 E (D)
( (v ; v ) 2= E (D)
i
j
i
j
A matriz correspondente ao digrafo da gura 1.8 e:
A
D
1.4.2
0
0
B
B
1
B
B
=B 0
B
B
@0
0
0
1
1
0 0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
1
C
C
C
C
C
C
C
A
Matriz de Incid^
encia
Ao contrario da matriz de adjac^encia, a matriz de incid^encia pode representar
grafos com arestas multiplas ou (em digrafos) com arcos paralelos.
Denic~ao 1.17 A matriz de incid^encia B = [b ] , de um grafo (multigrafo) G = (V; E ) , com V (G) = fv(1 ; v2 ; ; v g e E (G) = fe1 ; e2 ; ; e g e
b =1 ( v 2e
denida da seguinte forma: B =
b = 0 ( v 2= e
ij
n
m
ij
i
j
ij
i
j
G
Figura 1.9:
Matriz de incid^encia correspondente ao multigrafo da gura 1.9 e:
B
G
0
1
B
B
1
B
B
=B 0
B
B
@0
1
0
1
0
0 0
1
0
1
0
0
1
0
0
0
1
0
1
0
0
0
0
1
0
1
0
1
C
C
C
C
C
C
C
A
Seja D um digrafo, ent~ao b = 1 se v estiver no incio do arco, b = 1
se v estiver no m do arco e, 0 caso contrario.
ij
i
i
11
ij
Figura 1.10:
Matriz de incid^encia do digrafo da gura 1.10 e:
B
D
0
B
B
=B
B
@
1
1
0
0
0
1
0
1
1
0
1
0
1
0
1
0
0
1
1
0
0
0
1
1
1
C
C
C
C
A
Teorema 1.3 Seja B matriz de incid^encia de um grafo G = (V; E ), B
transposta de B e A a matriz de adjac^encia de um grafo simples verica-se a
relaca~o B B = D + A onde D e uma matriz diagonal de ordem n (numero
T
T
de vertices do grafo) cujos elementos da diagonal principal s~ao os graus dos
matriz D da-se o nome de matriz dos graus.
vertices respectivos. A
Demonstrac~ao: seja C = B B . Uma vez que, B transforma as linhas
de B em colunas, ent~ao o elemento C e igual ao produto escalar entre as
linhas i e j de B , logo C = C .
T
T
ij
ij
ji
C = b 1 b1 + b 2 b2 + b b + + b b
t
ij
i
t
i
j
t
ik
j
t
im
kj
mj
se i = j ent~ao
C = C = b 1 b1 + b 2 b2 + b b + + b b
t
ij
ii
X
m
que e igual
i
t
t
i
i
ik
i
ki
t
im
mi
b2 , e o resultado sera igual a soma dos 1 existentes
ik
k =1
nessa soma que, e o grau do vertice v .
i
12
se i 6= j ent~ao
C = b 1 b1 + b 2 b2 + b b + + b b
t
ij
i
,C
ij
t
t
t
i
j
ik
j
im
kj
mj
,
= b 1b 1 + b 2b 2 + b b + + b b
i
j
i
j
ik
jk
im
jm
caso uma das parcelas for 1 as restantes t^em de ser 0, pois se b b = 1,
signica que v e adjacente a v e e e unica uma vez que n~ao pode existir
arestas paralelas. Ainda pode ser que 8k = 1; m ; b b = 0, fazendo
com que a soma seja 0, o que quer dizer v e v n~ao denem nenhuma
aresta.
ik
i
j
jk
k
ik
i
jk
j
Sendo assim podemos concluir que B B = D + A.
T
1.5 Isomorsmo
Denic~ao 1.18 Dois grafos G1 = (V1 ; E1 ) G2 = (V2 ; E2 ) dir-se-~ao
isomorfos se existir uma bijecca~o ' : V1 ! V2, tal que
f'(v ); '(v )g 2 E2 , fv ; v g 2 E1
i
j
i
j
Figura 1.11:
Os dois grafos da gura 1.11 s~ao isomorfos. Pois existe uma bijecca~o
' : V1 ! V2 denida por:
'(v1 ) = w1 ; '(v2 ) = w2 ; '(v3 ) = w4 ; '(v4 ) = w3
.
13
facil ver que os grafos isomorfos t^em matrizes de adjac^encia iguais, ate
E
a ordem dos seus nos. Uma maneira simples, mas eciente, de testar
o isomorsmo e provar exactamente o contrario atraves do conceito
de Invariante. Invariante e uma propriedade que e preservada pelo
isomorsmo, como por exemplo, numero de nos, grau e determinante
da matriz de adjac^encia.
1.6 Exerccios
1. Prove que num grafo o numero de vertice de grau mpar e par.
Sugest~ao: Lembre-se que
X
n
deg(v ) e par.
i
i=1
2. Prove que dado um grafo G: tr(A2 ) = 2kGjj , onde A e a matriz
de adjac^encia.
sugest~ao: primeiro mostre que a de A2 e o grau de v .
ii
i
3. Seja V um conjunto de pontos no plano. Digamos que dois desses
pontos s~ao adjacentes se a dist^ancia entre eles e menor que 2 . Essa
relaca~o de adjac^encia dene o grafo dos pontos no plano (sobre o
conjunto V ). Faca uma gura do grafo denido pelos pontos
abaixo.
(0; 2) (1; 2) (2; 2)
(0; 1) (1; 1) (2; 1)
(0; 0) (1; 0) (2; 0)
4. A Figura 1.12 representa as ruas de uma determinada zona, desenhe sua representac~ao sob forma de grafo
5. Os hidrocarbonetos conhecidos como alcanos t^em formula qumica
H C2 +2 , onde C e H representam atomos de carbono e hidrogenio
respectivamente.
p
p
(a) Represente as moleculas de C4 H1 0 .
14
Figura 1.12:
Figura 1.13: Molecula (CH4 ) de Metano e propano (C3 H8 )
(b) Desenhe os grafos correspondentes a essas moleculas, estude
o isomorsmo entre eles.
6. Para os grafos desenhados a seguir
Figura 1.14:
(a) Fazer a descric~ao formal (como par ordenado de conjuntos).
(b) Determinar o grau de cada vertice.
(c) Vericar o teorema 1.1
15
7. Seja G = (V; E ) um grafo cuja matriz de incid^encia e a seguinte:
1
0
111000
C
B
C
B
0
0
0
1
1
0
C
B
C
B
B
001001C
C
B
C
B
0
1
0
0
1
0
A
@
100101
(a) Determinar o grau de cada vertice.
(b) Esbocar uma representaca~o pictorica de G.
(c) Determinar a matriz de adjac^encia de G.
8. Considerar o digrafo D = (V; E ).
Figura 1.15:
Determinar a matriz de adjac^encia e incid^encia de D.
9. Determinar o subgrafo induzido pelo conjunto dos vertices fv1 ; v2 ; v3 ; v6 g
.
Figura 1.16:
16
Captulo 2
Caminhos e conectividade
2.1 Caminhos
Denic~ao 2.1 Chama-se caminho entre dois vertices v e v num
i
r
grafo a uma sequ^encia nita de vertices e arestas da forma
v ; e ; v +1 ; e +1 ; :::; e 1 ; v , onde, para cada j , e e uma aresta que liga
v a v +1 .
i
j
i
i
i
r
r
j
j
Os vertices e as arestas de um caminho podem n~ao ser todos distintos.
Um caminho diz-se simples se n~ao tiver arestas repetidas e, diz-se
elementar se n~ao tiver vertices repetidos. Um caminho no qual o
vertice inicial e o vertice terminal coincidem chama-se circuito. Um
circuito diz-se simples se n~ao possuir arestas repetidas e um circuito
simples no qual nenhum vertice e repetido excepto o vertice inicial
(terminal) designa-se por ciclo. Dado um caminho P de um grafo G
designa-se por comprimento de P o numero de arestas que o constitui
e denota-se por: comp(P ). Por exemplo, uma aresta e um caminho de
comprimento 1, e um vertice e um caminho de comprimento 0. Por
outro lado, um tri^angulo e um ciclo de comprimento 3.
17
2.2 Conexidade
Denic~ao 2.2 Um grafo G e dito conexo se e so se para qualquer par
de vertices v ; v 2 G : v 6= v existir um caminho entre eles.
i
j
i
j
Denic~ao 2.3 Dene-se dist^ancia entre dois vertices v ; v de um
grafo G conexo como sendo menor comprimento dos caminhos que v~ao
de v a v . Representa-se por: dist (v ; v ) .
i
i
j
G
i
j
j
Figura 2.1:
O caminho v5 ; v5 v4 ; v4 ; v4 v2 ; v2 ; v2 v6 ; v6 ; v6 v4 ; v4 ; v4 v3 ; v3 ; v3 v1 ; v1 ; v1 v5 ; v5
e um circuito simples (n~ao ha arestas repetidas e o vertice inicial e
terminal coincidem), mas n~ao e um ciclo ja que para alem do vertice
inicial (que e tambem terminal) ha outro vertice, o vertice v6 , que esta
repetido.
Denic~ao 2.4 Uma componente conexa (o maximo subgrafo conexo
de H ) de um grafo G = (V; E ) e um subgrafo conexo G0 G : G0 + v
torna-se desconexo, com v 2 V (G).
i
i
O grafo da gura 2.2 tem 2 componentes conexas. Uma componente
conexa e sempre n~ao vazia.
Num digrafo estes conceitos levam em conta a orientaca~o.
Denic~ao 2.5 Chama-se caminho orientado a uma sequ^encia nita de
arcos da forma v1 ; e1 ; v2 ; e2 ; :::; e 1 ; v onde, para cada j = 1; 2; :::; r 1
r
18
r
Figura 2.2:
, se tem e = (v ; v +1 ) . Se existir um caminho orientado de v1 para
v dir-se-a que v1 esta conectado a v .
j
j
j
n
n
A partir daqui dene-se caminho fechado, circuito e ciclo concordantemente.
Se entre dois vertices quaisquer v e v (v 6= v ) existir sempre um
caminho orientado de v para v e um caminho orientado de v para v
o digrafo diz-se fortemente conexo ; mas se transformando todos os
seus arcos em arestas o grafo obtido for conexo ent~ao o digrafo diz-se
fracamente conexo .
i
i
j
j
i
j
j
i
As sucessivas pot^encias da matriz de adjac^encia de um grafo servem
para determinar o numero de caminhos de comprimento dado entre os
varios pares possveis de vertices de um grafo.
Teorema 2.1 Seja A a matriz de adjac^encia de um grafo de ordem n,
o elemento da linha i e coluna j da pot^encia de ordem k (k 1) de A
e igual ao numero de caminhos de comprimento k , entre os vertices i
e j.
Demonstrac~ao: Demonstrar-se-a este teorema por induca~o nita.
1. Um caminho de comprimento 1 e uma aresta; logo, tendo em
conta a denica~o de matriz de adjac^encia, o teorema verica-se
para k = 1
19
2. Suponha-se ent~ao que o teorema se verica para a pot^encia
k 1(k > 1). Seja, para cada k = 1; 2; 3; :::; a( ) o elemento (i; j )
k
ij
da pot^encia de ordem k da matriz A. Ent~ao a
(k )
ij
onde
a
(k
ip
1)
a =
pj
(
X
n
=
a(
k
ip
1)
a ,
pj
p=1
a(
k
ip
( fp; j g 2 E (G)
0 ( fp; j g 2= E (G)
1)
Por hipotese (induc~ao) a( 1) e o numero de caminhos de comprimento k 1 entre os vertices i e p e, portanto, a( 1) sera o
numero de caminhos de comprimento k entre os vertices i e j que
inclui uma aresta que vai de p a j .
k
ip
k
ip
Somando todas as possibilidades que v~ao desde p = 1 n, obtem-se
o resultado pretendido.
Teorema 2.2 Seja G um grafo de ordem n, cuja matriz de adjac^encia
e A e S = A + A2 + A3 + + A 1 . Ent~ao existe (pelo menos) um
caminho entre o vertice i e j se e so se, o elemento de ordem (i; j ) na
matriz S for diferente de zero.
n
Se todos os elementos da matriz S forem diferentes de zero ent~ao G e
um grafo conexo.
2.3 Caminhos de Euler
Euler para responder ao problema dos moradores de Konigsberg esquematizou o problema como mostra a gura 2.3, em que os vertices
representam a terra e as arestas as pontes.
Denic~ao 2.6 Chama-se caminho euleriano a um caminho simples
de um grafo que contem todas as arestas de um grafo. Um caminho
euleriano que seja fechado designa-se por circuito euleriano.
20
Figura 2.3: Esquema das Pontes
Euler resolveu o problema com o seguinte teorema:
Teorema 2.3 (Euler) Um grafo (ou multigrafo) conexo possui um
circuito euleriano se e so se todos os vertices tiverem grau par.
Demonstrac~ao.
1. Existe circuito de Euler ent~ao todos os vertices t^em grau par.
Se existe um circuito de Euler, ent~ao sempre que se chega a um
vertice e preciso sair e, por isso, as arestas incidentes em cada
vertice t^em que ser em numero par.
2. Todos os vertices t^em grau par, ent~ao existe circuito de Euler.
Se todos os vertices t^em grau par o grafo deve conter pelo menos
um circuito. Com efeito, considere-se um grafo G com m arestas
e todos os vertices com grau par. Seja C o caminho de maior
comprimento que se pode ter em G. Sejam os vertices desse caminho x1 x2 x 1 x . Como x tem grau par ent~ao ele n~ao pode
estar ligado so a x 1 , mas como C e o caminho de maior comprimento em G, ent~ao a outra aresta deve ligar a um dos outros
vertices deste caminho, obtendo-se assim o circuito desejado. Para
demonstrar a exist^encia de um circuito de Euler procede-se por
induca~o matematica sobre o numero de arestas do grafo.
p
p
p
p
21
(a) Para m = 1, a proposica~o e verdadeira pois, o unico grafo
conexo com 1 aresta cujo grau dos vertices seja par, e um
grafo so com um vertice de grau dois (a aresta e um laco),
onde claramente ha um circuito de Euler.
(b) Por hipotese de induc~ao, considere-se que todos os grafos
conexos com numero de arestas inferior a m e em que todos
os vertices t^em grau par possuem um circuito de Euler.
(c) Seja agora G um grafo conexo com m arestas e em que todos
os vertices t^em grau par. G tem um circuito. Seja C esse
circuito. Num circuito cada vertice esta ligado ao vertice anterior e ao seguinte. Se retirarmos de G as arestas de C , o
grafo resultante G0 continua a ter todos os vertices com grau
par. O grafo G0 pode n~ao ser conexo. Cada uma das suas
componentes conexas obedece a hipotese de induca~o e, por
isso, possui um circuito de Euler.
Estamos em condico~es de construir um circuito de Euler para G,
comecando no circuito C , usando cada circuito de Euler das componentes conexas de G0 sempre que um vertice de C pertencer
a uma dessas componentes, regressando a C exactamente a esse
vertice e continuando ate voltar ao ponto de partida.
Teorema 2.4 Num grafo conexo existe um caminho de Euler se e so
se houver exactamente duas arestas com grau mpar.
Demonstrac~ao. Unindo os dois vertices de grau mpar por uma aresta
teremos um grafo conexo em que todas as arestas t^em grau par. Estamos, assim, em condic~oes de encontrar um circuito de Euler. Basta
escrever o circuito de tal modo que a aresta introduzida seja a primeira
ou a ultima e depois retira-la para obter um caminho de Euler, que vai
comecar e acabar nos dois vertices de grau mpar.
Denic~ao 2.7 Uma aresta e e chamada de ponte se a sua remoca~o
torna o grafo desconexo.
22
Figura 2.4:
Removendo e obtem-se o seguinte grafo desconexo:
Figura 2.5:
Denic~ao 2.8 Seja G = (V; E ) um grafo. Um caminho de G diz-se
hamiltoniano se passar uma e uma so vez por cada um dos vertices
do grafo.
Algoritmo de Fleury
1. Escolher um vertice qualquer para iniciar.
2. Escolher qualquer aresta que saia desse vertice, mas caso uma
dessas arestas for uma ponte ent~ao devera ser a ultima escolhida.
3. Destruir a aresta utilizada.
4. Repetir 2 e 3 ate chegar ao vertice inicial.
5. Se n~ao ha mais arestas o circuito de Euler esta encontrado. Caso
ainda haja arestas, recomecar o circuito a partir de um dos vertices
do circuito onde ainda haja arestas incidentes.
23
2.4 Exerccios
1. Nos grafos que se seguem indicar se possvel:
Figura 2.6:
(a) Determinar um caminho elementar de v1 a v6 .
(b) Determinar um caminho simples de v1 a v6 que n~ao seja elementar
(c) Determinar um caminho de v1 a v6 que n~ao seja simples
2. Considere o seguinte grafo. Determine:
Figura 2.7:
(a) Determinar um circuito que n~ao seja um ciclo.
(b) Determinar um circuito que n~ao seja simples.
(c) Determinar um circuito simples.
3. Considerar o digrafo G = (V; E ) onde
V = fv1 ; v2 ; v3 ; v4 ; v5 ; v6 g e
E = f(v1 ; v2 ); (v2 ; v3 ); (v3 ; v4 ); (v4 ; v5 ); (v5 ; v6 ); (v1 ; v6 ); (v2 ; v6 ); (v5 ; v2 )g
24
(a) Determinar um caminho de v1 a v6 de comprimento 6.
(b) Determinar um caminho simples de v1 a v6 com 5 arcos
(c) Determinar um ciclo com 4 arcos.
(d) Determinar a dist^ancia entre o vertice v2 e v5 .
(e) Usar a matriz de adjac^encia de G para determinar o numero
de caminhos de v2 a v4 de comprimento 2.
4. Usar um procedimento matricial para o grafo a qual corresponde
a matriz de adjac^encia.
A
G
0
0
B
B
1
B
B
=B 1
B
B
@0
1
0
0
1
0 0
1
0
0
0
1
0
1
0
0
1
0
0
1
1
1
1
C
C
C
C
C
C
C
A
Determinar:
(a) Se existe um caminho entre o vertice v1 e v5 .
(b) Se o grafo e ou n~ao conexo?
5. Encontrar se possvel o ciclo de Euler e Hamilton nas guras
abaixo, e justicar as negativas.
Figura 2.8:
25
Captulo 3
Caminhos mais curtos
Sempre que num grafo ha custos associados as arestas, diz-se que estamos perante um grafo valorado.
Denic~ao 3.1 Chama-se custo de um caminho a soma dos valores
correspondentes as arestas que o constituem.
A representaca~o de um tal grafo pode ser feita gracamente escrevendo
os valores correspondentes a cada aresta sobre ela, ou atraves da matriz de adjac^encia, substituindo a entrada igual a 1 que informa da
exist^encia de uma aresta pelo custo que lhe corresponde.
Para grafos valorados, alem de interessar estabelecer a exist^encia de
pelo menos um caminho entre dois quaisquer vertices, e muitas vezes,
importante obter o caminho de menor custo.
O caminho mais curto entre dois vertices e aquele cujo custo e o
menor possvel. Se o grafo for de pequena dimens~ao, bastara fazer uma
lista de todos os caminhos possveis e escolher o de menor custo. Podese construir a matriz custos com base nos caminhos mais curtos entre
cada par de vertices.
Quando a dimens~ao do grafo e maior este processo e impraticavel.
Descrevemos seguidamente o algoritmo de Dijkstra por ser um dos mais
26
simples de aplicar, que funciona tanto para grafos orientados como
n~ao orientados e que tambem se presta a uma facil implementac~ao
computacional.
3.1 Algoritmo de Dijkstra
Este algoritmo, baseia-se no princpio de que o caminho mais curto
entre dois vertices contem o caminho mais curto entre cada par de
vertices intermedios. Vamos descrever o algoritmo determinando o caminho mais curto entre os vertices a e h do digrafo da gura 3.1.
Figura 3.1: Determinar o caminho mais curto do digrafo valorado
Partindo do vertice a, em cada passo do algoritmo determina-se o caminho mais curto entre esse vertice e um outro vertice do grafo que
ca no caminho para h. O algoritmo termina quando se consegue atingir h. Vamos denir dois conjuntos de vertices S e T do seguinte
modo: S e o conjunto dos vertices para onde ja se sabe qual e o caminho mais curto e T e o conjunto dos outros vertices. Inicialmente
e S = fag e T = fb; c; d; e; f; g; hg, pois o caminho mais curto entre
a e a e obviamente de comprimento nulo. Em cada iteraca~o vamos
tirar um vertice de T e inseri-lo em S . Com esse objectivo construmos
27
uma tabela em que se indicam as dist^ancias mnimas ja determinadas
para os vertices de S e as dist^ancias estimadas para os vertices de T
para onde se pode ir directamente a partir dos vertices de S , para os
vertices de T aos quais n~ao seja possvel chegar directamente a partir
dos vertices de S consideramos que a dist^ancia estimada e 1: A coluna
"antecedente"permitira, como veremos construir o caminho mais curto
depois de sabermos qual o valor que lhe corresponde. Inicialmente
temos a seguinte tabela:
Vertice Dist^ancia mnima Dist^ancia estimada Antecedente
a
0
a
b
3
a
c
8
a
d
4
a
e
1
f
1
g
1
h
1
Observando a coluna "dist^ancia estimada", vemos que o menor valor e 3
e corresponde ao vertice b. Ent~ao o caminho mais curto entre o vertice
a e o vertice b e 3 e ja podemos passar o vertice b para o conjunto
T . A partir do vertice b pode-se ir para c e e. O caminho de a a b
tem comprimento 3 e de b a c comprimento 2, logo o caminho de a a c
passando por b tem comprimento 5 que e menor do que o valor 8 antes
estimado. Actualizamos esse valor e mudamos o antecedente de c de a
para b. A dist^ancia estimada para e passa a ser 10, com antecedente b.
Temos assim novos conjuntos S = fa; bg e T = fc; d; e; f; g; hg e a nova
tabela:
28
Vertice Dist^ancia mnima Dist^ancia estimada Antecedente
a
0
b
3
a
c
5
b
d
4
a
e
10
b
f
1
g
1
h
1
Neste momento a menor dist^ancia estimada e 4 para o vertice d. Passamos o vertice d do conjunto T para o conjunto S (S = fa; b; dg e
T = fc; e; f; g; hg) e actualizamos os valores da tabela tendo em atenc~ao
os vertices para onde se pode ir directamente a partir de d. Repare-se
que de d para c a dist^ancia e 2, que somados a dist^ancia 4 ate d daria
uma dist^ancia 6 para c, valor superior ao 5 anteriormente estimado,
pelo que n~ao se considera esse caminho.
Vertice Dist^ancia mnima Dist^ancia estimada Antecedente
a
0
b
3
a
c
5
b
d
4
a
e
10
b
f
1
g
9
d
h
1
A dist^ancia estimada mnima neste momento e 5 para c. Ent~ao o vertice
c passa para o conjunto S (S = fa; b; c; dg e T = fe; f; g; hg) e repete-se
tudo de novo.
29
Vertice Dist^ancia mnima Dist^ancia estimada Antecedente
a
0
b
3
a
c
5
b
d
4
a
e
10
b
f
8
c
g
9
d
h
1
Passa-se f de T para S : S = fa; b; c; d; f g e T = fe; g; hg. De f pode-se
ir para e, g e h. Para e a dist^ancia estimada passa a ser 9 = 8 + 1 < 10
e actualiza-se o antecedente de e para f . Para g a dist^ancia seria
8 + 4 = 12 > 9 pelo que n~ao se considera e, para h temos agora a
dist^ancia estimada 8 + 3 = 11. Temos assim o novo quadro:
Vertice Dist^ancia mnima Dist^ancia estimada Antecedente
a
0
b
3
a
c
5
b
d
4
a
e
9
f
f
8
c
g
9
d
h
11
f
No passo seguinte tanto podemos escolher e como g , uma vez que
correspondem ambos a dist^ancia estimada mnima. Vamos escolher
e: S = fa; b; c; d; e; f g e T = fg; hg : De e so e possvel chegar a
h com a dist^ancia 9 + 8 = 17 > 11. Seguidamente escolhemos g:
S = fa; b; c; d; e; f; gg e T = fhg . De g tambem so se pode ir para h
com a dist^ancia 9 + 3 = 12 > 11. Finalmente, a menor dist^ancia estimada corresponde ao vertice h com o valor 11: S = fa; b; c; d; e; f; g; hg
30
e T = ;. Temos o quadro nal
Vertice Dist^ancia mnima Dist^ancia estimada Antecedente
a
0
b
3
a
c
5
b
d
4
a
e
9
f
f
8
c
g
9
d
h
11
f
Conclumos assim que o comprimento do caminho mais curto entre os
vertices a e h e 11. Para saber qual o caminho temos que analisar a
coluna dos antecedentes. O antecedente de h e f , o antecedente de f
e c, o antecedente de c e b e o antecedente de b e a. Temos assim o
caminho a ! b ! c ! f ! h:
31
Captulo 4
Tipos de Grafos
4.1 Grafos Bipartido
Um dos tipos de grafos com muita import^ancia, nos problemas de emparelhamento (casamentos, distribuica~o de grupos de tarefas por grupos de pessoas,
etc.) s~ao os chamados grafos bipartidos .
Um grafo G e dito r-partido se o seu conjunto de vertices admite uma
partica~o em r classes de modo que cada aresta tem extremos em classes
diferentes. Vertices na mesma partic~ao n~ao podem ser adjacentes.
Denic~ao 4.1 Um grafo G diz-se bipartido se existe uma partica~o do seu
conjunto de vertices em V 0 e V 00 (V = V 0 [ V 00 : V 0 \ V 00 = ;) tal que n~ao
existem arestas entre qualquer par de vertices de V 0 nem entre qualquer par
de vertices de V 00 . Um tal grafo bipartido e usualmente representado por
G = (V 0 ; V 00 ; E ), onde E denota o respectivo conjunto de arestas. Quando
jV(G)j = r, jV 00(G)j = s; 8x 2 V 0 8y 2 V 00 fx; y 2 E (G) este grafo denotase por K e designa-se por grafo bipartido completo.
r;s
O grafo K tem r + s vertices e r s arestas. Note-se tambem que os grafos
K e K s~ao iguais. Por convenca~o escreve-se sempre primeiro o menor dos
valores de s e r.
r;s
r;s
s;r
32
Figura 4.1: Grafos Bipartido
Denic~ao 4.2 Designa-se por grafo completo (nulo) de ordem n e denotase por K (N0 ) um grafo com n vertices dois a dois adjacentes (n~ao adjan
centes, ou seja, sem qualquer aresta). Um digrafo e dito completo se existir
um arco entre qualquer par dos seus vertices.
Figura 4.2: Digrafo Completo
Teorema 4.1 Um grafo admite uma bipartica~o se e so se n~ao tem circuitos
de comprimento mpar.
Demonstrac~ao: Se G = (V 0 ; V 00 ; E ) e um grafo bipartido, ent~ao e claro que
todos os circuitos t^em comprimento par. Com efeito, uma vez que tanto em
V 0 como em V 00 n~ao existem vertices adjacentes, partindo-se, por exemplo,
de um vertice em V 0 , de cada vez que se passa para V 00 , para se obter um
circuito, tem de se voltar a V 0 na aresta seguinte, pelo que qualquer circuito
tem comprimento par. Suponhamos que G n~ao tem circuitos de comprimento
33
mpar. Uma vez que um grafo e bipartido sse cada uma das suas componentes
constitui um subgrafo bipartido, podemos supor, sem perda de generalidade,
que G e conexo. Considere-se um vertice arbitrario z 2 V (G) e seja
V 0 = fw 2 V (G) : dist (z ; w) imparg . Nestas condico~es n~ao existem
arestas que liguem vertices de V 0 (caso contrario existiriam circuitos de
comprimento mpar). Por outro lado, como todos os vertices de V (G)nV 0
est~ao a uma dist^ancia par de z (em particular z esta a uma dist^ancia 0 dele
proprio), n~ao existem vertices adjacentes em V (G)nV 0 (uma vez que, por
raz~oes id^enticas as anteriores, em tais condico~es, existiriam circuitos de comprimento mpar). Logo, fazendo V 00 = V (G)nV 0 obtem-se uma bipartic~ao
para G, dada por G = (V 0 ; V 00 ; E ).
G
Denic~ao 4.3 Designa-se por grafo complementar de um grafo G = (V; E )
e denota-se por G = (V; E ) um grafo com o mesmo conjunto de vertices de
G no qual dois vertices s~ao adjacentes se e so se n~ao s~ao adjacentes em G
Figura 4.3: G e seu Complementar G
Pode-se concluir ent~ao que o complementar de um grafo completo K e um
grafo nulo N e que o complementar do grafo bipartido completo K e o
grafo desconexo composto de duas componentes conexas K e K .
n
n
r;s
r
s
4.2 Arvores
Uma outra classe importante de grafos s~ao as arvores. S~ao de extrema utilidade na resoluca~o de problemas combinatorios e de optimizaca~o: Instalaca~o
34
de cabos para distribuica~o de energia electrica, procura de caminhos mais
curtos ou com menor custo.
Usamos arvores direccionadas para calcular uma estrategia optima para jogos relativamente simples. Esta mesma tecnica e usada em muitos programas
para jogar Xadrez, com uma arvore de grande dimens~ao.
Denic~ao 4.4 Chama-se arvore um grafo T conexo e acclico (sem ciclos).
Uma arvore pode ser dirigida ou n~ao dirigida consoante T for um digrafo
ou, simplesmente, um grafo. O termo arvore sem qualquer qualicativo
interpreta-se sempre no sentido de ser uma arvore n~ao dirigida.
Figura 4.4: Arvore
Dirigida
Figura 4.5: Arvore
n~ao Dirigida
Pode-se designar um vertice para ser a raiz da arvore, o que demonstra uma
relaca~o logica entre os vertices. Essas arvores s~ao ditas hierarquicas e a
dist^ancia entre cada vertice e a raiz e denominada de nvel. Em uma arvore
hierarquica os vertices podem ser rotulados de acordo com a denominac~ao
de uma arvore genealogica: lhos, pais e ancestrais, no sentido literal das
palavras. Uma arvore hierarquica onde cada vertice da origem a dois outros
de nvel inferior, e chamada de arvore binaria. Os vertices de grau 1 em uma
arvore s~ao chamados de folhas.
35
Teorema 4.2 Numa arvore T existe um unico caminho simples entre cada
par de vertices
Demonstrac~ao: Sejam u e v dois vertices quaisquer de uma arvore T . Visto
que T e um grafo conexo ent~ao existe pelo menos um caminho entre u e v e,
portanto, existe um caminho simples entre aqueles dois vertices. Suponha-se
que, se possvel, P e P 0 s~ao dois caminhos simples entre aqueles dois vertices.
Se P e P 0 forem diferentes ent~ao existe uma aresta que pertence a um e n~ao
pertence ao outro. Suponha-se que e e a primeira aresta que esta em P mas
n~ao em P 0 quando se caminha de u para v , isto e, suponha-se que se tem
P : u::::::u :e::u +1 ::::::v
i
i
P 0 : u::::::u :::v +1 ::::::v
i
i
Seja W o conjunto de vertices intermedios de P situados entre u +1 e v e
seja W 0 o conjunto de vertices intermedios de P 0 situados entre v +1 e v . Se
W e W 0 n~ao tiverem quaisquer elementos comuns, ent~ao obter-se-a um ciclo
percorrendo todos os vertices de W a partir de u e depois todos os vertices de
W 0 (desde v ate u ). Esta situac~ao n~ao pode ocorrer pois T n~ao possui ciclos,
por hipotese. Por outro lado, supondo que W e W 0 t^em vertices comuns
seja u o primeiro vertice de P que pertence tambem a W 0 de tal forma que
nenhum vertice entre u e u esta em P 0 . Ent~ao obtem-se novamente um
ciclo partindo de u ate u em P e de u a u em P 0 . Quer dizer, a suposic~ao
que mais que um caminho simples entre dois vertices distintos de T implica
a exist^encia de um ciclo em T . Como T n~ao possui ciclos ent~ao entre dois
vertices quaisquer de T ha apenas um caminho simples.
i
i
i
i
r
i
i
r
r
r
i
Teorema 4.3 Se num grafo G existir apenas um unico caminho simples
entre dois quaisquer dos seus vertices, ent~ao G e uma arvore.
36
Teorema 4.4 Numa arvore cada aresta e uma ponte.
Teorema 4.5 Se G for um grafo conexo no qual cada aresta e uma ponte
ent~ao G e uma arvore.
Demonstrac~ao: Suponha-se que G n~ao e uma arvore, seja C um ciclo em G
e suponha-se que e designa uma aresta em C . Seja G0 o grafo que se obtem
suprimindo a aresta e em G. Visto que, por hipotese,e e uma ponte ent~ao
G0 e desconexo. Sejam p e q dois vertices quaisquer de G. Como G e conexo
existe um caminho P entre p e q . Se P n~ao contiver e ent~ao existiria tambem
um caminho entre p e q no grafo desconexo G0 . Por outro lado, se e = fv; wg
for uma aresta de P que tambem pertence ao ciclo C que parte, por exemplo,
do vertice t, obtem-se o seguinte caminho em G0 entre p e q
p::::::v::::::t::::::w::::::q
(substitui-se a aresta e pelo resto do circuito C que vai de v a w). Por outras
palavras, existe sempre um caminho entre cada par de vertices de G0 o que
contraria o facto de G ser desconexo.
Teorema 4.6 Uma arvore T com n vertices tem n 1 arestas.
Demonstrac~ao: Far-se-a a demonstrac~ao por induca~o em n.
1. A proposic~ao e verdadeira para n = 1 (uma vez que numa arvore
n~ao pode haver lacetes).
2. Suponha-se que a proposica~o e verdadeira para todo o m natural tal que 1 < m < n. Seja e = fu; v g uma aresta de T que e
uma arvore, pois tem lugar o teorema 4.5. Suprimindo a aresta
e obtem-se um subgrafo T 0 desconexo com duas componentes
conexas H e H 0 . Tanto H como H 0 s~ao arvores com k e k0 vertices
que s~ao numeros inteiros positivos tais que k + k0 = n. Ent~ao
tanto k como k0 s~ao menores que n. Pela hipotese de induc~ao H
37
tem k 1 arestas e H 0 tem k0 1 arestas e as duas componentes
juntas t^em (k 1) + (k0 1) = (k + k0 ) 2 = n 2 arestas. Ent~ao
T 0 tem n 2 arestas e, consequentemente, T tem n 1 arestas.
Assim pelo princpio de induca~o nita ca provado o teorema.
Teorema 4.7 Qualquer grafo conexo com n vertices e n
1 arestas e uma
arvore.
Demonstrac~ao:Se G = (V; E ) n~ao fosse uma arvore existiria uma aresta
e que n~ao seria uma ponte. Suprima-se e para obter o grafo G0 = (V; E 0 ).
Continue-se este processo ate obter um subgrafo H = (V; F ) no qual cada
aresta seja uma ponte. Ent~ao H e uma arvore com n 1 arestas. Isto
signica que apos este processo de remoca~o de arestas acabou por se car
com o mesmo numero, ou seja, que o grafo inicial ja era uma arvore.
Denic~ao 4.5 Uma arvore suporte (geradora) de um grafo G e um grafo
parcial de G que e uma arvore.
Teorema 4.8 Um grafo G e conexo se e so se possuir uma arvore suporte.
Demonstrac~ao: Se G possuir uma arvore suporte ent~ao, visto que a arvore e
conexa e possui o mesmo numero de vertices que G, G e conexo. Suponhamos
que G n~ao e conexo ent~ao nenhum dos seus grafos parciais sera conexo e,
portanto, nenhum deles pode ser uma arvore. Se G e conexo ent~ao G admite
uma arvore de suporte. Supondo G conexo procuremos uma aresta em G
que possa ser removida sem que o grafo se torne desconexo. Uma de duas
situaco~es pode ocorrer:
1. N~ao existe tal aresta;
2. Existe tal aresta;
No primeiro caso ja encontramos uma arvore. No segundo caso removemos
a aresta e repetimos o processo ate que se ocorra a primeira situac~ao.
38
Ha fundamentalmente dois processos para encontrar uma arvore de suporte
para um dado grafo conexo: o destrutivo e o construtivo.
1. O processo destrutivo baseia-se na demonstraca~o do teorema
que garante a exist^encia da arvore de suporte. Comeca-se por
considerar o grafo inicial. Uma aresta cuja remoc~ao n~ao torna o
grafo desconexo tem que pertencer a um circuito. Se n~ao houver
nenhum circuito ja se tem uma arvore. Caso contrario identica-se
um circuito e retira-se uma aresta. Se n~ao houver mais circuitos
se termina o processo, caso contrario repete-se ate n~ao haver mais
circuitos.
2. No processo construtivo vai-se construindo a arvore comecando
com um vertice do grafo inicial e, em cada passo, escolhe-se uma
aresta do grafo que comece num vertice da arvore e termine num
vertice que ainda n~ao esteja na arvore, acrescentando-se ent~ao esse
vertice e essa aresta a arvore. O processo termina quando todos os
vertices estiverem na arvore. Para um mesmo grafo podem existir
varias arvores de suporte.
4.2.1
Arvore
suporte M
nima
Quando, estivermos perante um grafo valorado, torna-se de crucial import^ancia
a determinaca~o de uma arvore suporte cujo custo seja o mnimo possvel.A
tal arvore e designada por arvore de suporte mnima. Existem varios
algoritmos que permitem a obtenc~ao de tal arvore. A resposta pode n~ao ser
unica, embora, neste caso, geralmente, o numero de opc~oes de escolha e mais
reduzido.
Algoritmo de Prim.
A arvore e obtida pelo processo construtivo.
Denote-se o conjunto T , formado pelos vertices que, em cada passo do algoritmo, ja foram colocados na arvore. Inicia-se a construca~o da arvore
39
escolhendo a aresta com custo mnimo. Colocam-se os dois vertices a que
essa aresta e incidente no conjunto T. Em cada iterac~ao escolhe-se, entre as
arestas que t^em um vertice em T e outro em V T , a que tiver custo mnimo.
Acrescenta-se essa aresta a arvore e o novo vertice a T e repete-se o processo
n 1 vezes. Deste modo garante-se que n~ao se formam circuitos.
Denic~ao 4.6 Chama-se oresta a um grafo desconexo, que cada componente conexa e arvore.
Teorema 4.9 Um grafo G e uma oresta se e so se jE (G)j jV (G)j + c(G) =
0 onde c(G) denota o numero de componentes de G.
Demonstrac~ao: A prova da condica~o necessaria vai ser feita por induca~o
sobre o numero de arestas de G, tendo em conta que o resultado se verica
trivialmente para jE (G)j = 0. Suponha-se jE (G)j > 0 e que o resultado se
verica para todas as orestas com menos do que jE (G)j arestas. Seja G0
um subgrafo de G obtido por eliminac~ao de uma aresta arbitraria. Logo G0 e
uma oresta com jE (G)j 1 arestas, jV (G)j vertices e c(G)+1 componentes.
Por hipotese de induc~ao, aplicada a G0 ,
0 = jE (G0 )j jV (G0 )j+c(G0 ) = jE (G)j 1 jV (G)j+c(G)+1 = jE (G)j jV (G)j+c(G) :
(Suponha-se que G tem p componentes, G1 ; ; G , pelo que
p
jE (G)j jV (G)j + p =
X
p
(jE (G )j
jV (G )j + 1)
j
j
j =1
Ent~ao
jE (G)j jV (G)j + p = 0 ,
X
p
(jE (G )j
jV (G )j + 1) = 0
j
j
j =1
e, uma vez que 8j 2 f1; ; pg jE (G )j jV (G )j + 1 > 0 conclui-se que
8j 2 f1; ; pg jE (G )j jV (G )j +1 = 0 Consequentemente,todos os grafos
G , com j 2 f1; ; pg , s~ao arvores.
j
j
j
j
40
j
4.3 Exerccios
1. Tr^es vizinhos inimigos usam a mesma agua, oleo e gas. Eles desejam construir caminhos que vai das suas casas a cada uma das 3
fontes. Apresente uma proposta, identicando o tipo de grafo.
n(n 1)
2. Prove que um grafo de ordem n, completo tem dimens~ao
.
2
41
Captulo 5
Aplicaco~es
5.1 Problemas Propostos e Resolvidos
1. Numa Escola Secundaria organiza-se um campeonato de Futsal
entre as 7 turmas do 11o ano. Cada turma deve jogar uma unica
vez com cada uma das outras. A certa altura sabe-se que: a turma
A ja fez 6 jogos; a B fez 5 jogos; a C e a D zerem 3 jogos cada
uma; a E e a F zeram 2 jogos cada uma e a G ainda so fez 1
jogo. Sera possvel saber que jogos fez a turma C ? E quantos
jogos faltam ainda fazer ao todo?
Resoluc~ao :
Considerando as turmas como elementos do conjunto dos vertices, tracando uma aresta caso as turmas ja tenham
jogado, obtemos grafo da gura 5.1. Analisando o grafo veremos
que, a turma C ja fez 3 jogos (jogou com A, B e D). O grafo tem
11 arestas que e o total de jogos ent~ao realizados. Sabendo que
cada turma deve jogar uma unica vez com as outras (cada uma
realizara 6 jogos), faz com que no nal do campeonato tenhamos
um grafo completo de ordem 7, pelo que o total de jogos seria
76
= 21, fazendo 21 11 encontramos o numero de jogos por
2
realizar.
42
Figura 5.1:
Outra via: Representemos o grafo pela sua matriz de adjac^encia.
Cada la da matriz representa uma turma respeitando a ordem alfabetica (1a la turma A, 2a la turma B , ...).
0
0
B
B
1
B
B
1
B
B
B
A=B 1
B
B
1
B
B
@1
1
0
1
1
1
1
1 0
1
1
0
1
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
C
C
C
C
C
C
C
C
C
C
C
C
A
A soma dos elementos da 3a la da matriz e 3, grau do vertice
C , o que quer dizer que a turma C ja fez 3 jogos. Para saber que
jogos ja fez vamos analisar os elementos iguais a 1 na 3a linha
(representa os jogos realizados pela turma C ): a31 = 1 quer dizer
que a turma C ja jogou com A; a32 = 1, jogou com B ; a34 = 1,
jogou com D. Para determinar os jogos que faltam faz-se o mesmo
processo que na primeira resoluca~o.
2. Perguntou-se a seis pessoas de um grupo de quem elas gostavam
dentro do grupo. Representamos as pessoas pelas letras p, q, r, s,
t e u. Com as respostas preenchemos o quadro:
43
Pessoas Gosta de
p
q, r, t, u
q
p, t
r
p, u
s
p
t
p, q, u
u
p
Estude as relac~oes entre estas pessoas descobrindo:
(a) Quem e a mais popular.
(b) Quem e a menos popular.
(c) Um grupo de verdadeiros amigos.(Cada elemento do grupo e
amigo dos restantes).
Sugest~ao :Esta situaca~o pode ser estudada considerando as pessoas como elementos do conjunto dos vertices, um arco entre elas
caso uma respondeu a outra como amigo.
3. Nas ilhas de Cabo Verde, a ag^encia NITOUR disp~oe de um plano
de viagens que une directamente as 10 ilhas do arquipelago. Os
navios n~ao efectuam paragens intermedias.
Utilizando a matriz de adjac^encia, descreve-se no quadro as linhas
e sentidos em que o servico operado.
As ilhas s~ao representadas por letras maiusculas de A a J.
44
A
B
C
D
E
F
G
H
I
J
A
0
0
0
0
1
0
0
1
0
0
B
1
0
1
0
0
0
0
0
0
0
C
0
0
0
0
0
0
1
0
0
0
D
0
0
1
0
0
0
0
0
0
0
E
1
0
0
0
0
0
1
0
0
0
F
0
0
0
0
0
0
0
0
0
1
G
0
0
0
1
0
0
0
0
0
0
H
0
0
0
0
0
0
0
0
1
1
I
0
0
0
0
0
0
0
1
0
0
J
0
1
1
0
0
1
0
0
0
0
(a) ) Para que ilhas se pode deslocar um passageiro que esteja no
local F ?
(b) Para ir de C para H qual e o numero mnimo de navios que
um passageiro deve usar?
(c) O sistema garante o transporte de passageiros entre qualquer
par de ilhas?
(d) Caso a resposta tenha sido n~ao apresente uma soluca~o, inserindo novos percursos, que permita o transporte de passageiros entre qualquer par de ilhas. (Isto e, acrescente arcos
de modo a transforma-lo num digrafo fortemente conexo).
4. Considere os seguintes conjuntos A = fa; bg, B = fc; dg,
C = fe; f g, efectue a seguinte operac~ao A B C , utilizando
conceitos da teoria dos grafos.
5. Uma mulher deve transportar um le~ao, uma raposa e um coelho
de uma margem a outra de um rio, em um barco que so cabe a
mulher e mais um dos animais. Se o le~ao e a raposa, ou a raposa e
o coelho, carem na margem oposta em que estiver a mulher, em
dado instante, o primeiro come o segundo. Construa um grafo,
e mostre todas as formas de cruzar o rio com seguranca para a
45
raposa e o coelho.
Resoluc~ao: Criemos um vertice para cada conguraca~o segura
(aquela em que ninguem come ninguem) possvel, e uma aresta
entre dois vertices se a conguraca~o representada por um puder
ser obtida daquela representada pelo outro cruzando-se o rio.
Os animais est~ao todos num lado A do rio. Representemos a
viagem do lado A para B pelo arco azul, e o regresso a A por
vermelho. Observando a gura 5.2 podemos ver que inicialmente
Figura 5.2:
a mulher so pode levar a raposa para o lado B , pois se zer outra
escolha deixara ou o le~ao e raposa, ou raposa e coelho do lado
oposto e o primeiro comera o segundo. Regressando sozinha no
barco vai encontrar o coelho e o le~ao, aqui ela tanto pode levar
o coelho como o le~ao. Optando por levar o coelho, ao chegar na
margem B , cara com coelho e raposa. Forcosamente tera que
levar a raposa para o lado A pois, se deixar os dois para ir buscar
o le~ao a raposa comera o coelho. Levando a raposa e trazendo
o le~ao, teremos o coelho e le~ao no lado pretendido B , assim ira
46
sozinha buscar a raposa no lado A. Esta e uma forma segura de
cruzar o rio com animais.
6. Um certo jogo de dois jogadores comeca com uma pilha vazia. Os
jogadores se alternam colocando 1, 2 ou 3 moedas de 1 centavo na
pilha. O vencedor sera aquele que colocar o decimo sexto centavo.
Sugest~ao : Descreva o jogo em termos de grafos direccionados,
mostrando que o segundo jogador tem uma estrategia vencedora.
7. Uma rede rodoviaria entre seis povoaco~es, A, B, C, D, E e F, e
constituda por oito estradas como descrito a seguir: entre A e B
com 30Km; entre A e C com 22Km; entre A e D com 30Km;
entre B e E com 20Km; entre C e E com 12Km; entre C e D
com 36Km; entre E e F com 40Km; entre D e F com 18Km.
Represente esta rede rodoviaria por um grafo com pesos. Em
seguida aplique o algoritmo de Dijkstra ao grafo para determinar
o percurso mais curto da povoaca~o D para a povoac~ao B , bem
como a respectiva dist^ancia.
8. Prove que sim ou que n~ao:
possvel ter um grupo de 9 pessoas, cada uma das quais
(a) E
conhece exactamente 5 das outras.
(b) Em qualquer grupo, o numero de pessoas n~ao apertaram as
m~aos de um numero mpar de pessoas do grupo e par.
(c) O numero de todos os seres humanos (vivos e mortos) que se
casaram um numero mpar de vezes e par.
(d) Em qualquer livraria, o numero de livros com um numero
mpar de paginas e par.
Sugest~ao :Lembre-se que
{ em qualquer grafo a soma do grau de todos os vertices e par.
{ o numero de vertices de grau mpar e par.
9. Numa cidade do interior, o prefeito, preocupado com a assist^encia
a saude da populaca~o, deseja construir um Pronto Socorro equipado
47
com ambul^ancias para buscar os pacientes em caso de emerg^encia.
Considere A, B, C, D, E, F, G e H como os bairros da cidade que
dever~ao ser atendidos pelas ambul^ancias e os caminhos entre os
bairros descritos da seguinte forma:
entre A e B com 3 km de distancia; A e D com 9 km de distancia;
A e H com 6 km de distancia; B e C com 2 km de distancia; B
e D com 5 km de distancia; B e H com 8 km de distancia; C e
D com 1 km de distancia; D e F com 3 km de distancia; D e G
com 7 km de distancia; E e F com 4 km de distancia; F e G com
9 km de distancia; G e H com 5 km de distancia;
Represente esta situaca~o por um grafo e, determine qual seria o
ponto adequado para a instalaca~o do Pronto Socorro na cidade de
tal forma que, a dist^ancia percorrida a partir deste pronto socorro
ate um bairro, seja mnima?
48
Resoluc~ao :
A situaca~o pode ser modelada como mostra a gura 5.3.
Figura 5.3:
Pela matriz de custo e possvel descobrir a localizaca~o do centro
de emerg^encia (dm e a dist^ancia maxima entre os vertices)
A
B
C
D
E
F
G
H
A B C D E F
0 3 5 6 13 9
3 0 2 3 10 6
5 2 0 1 7 4
6 8 1 0 7 3
13 10 7 7 0 4
9 6 4 3 4 0
11 10 8 7 13 9
6 8 10 12 17 14
G
11
10
8
7
13
9
0
5
H
6
8
10
12
17
14
5
0
dm
13
10
10
12
17
14
11
17
De acordo com a matriz de custo camos a saber que os possveis
pontos para a instalaca~o do centro de emerg^encia, s~ao B e C , isto
e, tanto B como C t^em as menores dist^ancias entre os restantes.
49
Consideraco~es Finais
Orientando-se nos objectivos tracados, ao terminar o trabalho, constatamos
que, cumprindo as exig^encias do Regulamento do Trabalho de Fim do Curso,
conseguimos elaborar e apresentar um documento - sntese das ideias basicas
da Teoria dos Grafos, ilustrando-as com exemplos - problemas que, do nosso
ponto de vista, incentivam o interesse no tema escolhido.
Tendo em conta a insuci^encia no pas da bibliograa cientca nas areas
exactas, a presente Monograa pode servir como um material didactico para
a iniciac~ao do estudo da Teoria dos Grafos.
Para ser um instrumento de apoio completo, mais solido, sugerimos aos interessados no assunto, dar suas validas contribuic~oes.
50
Refer^encias Bibliogracas
[1] Cardoso, Domingos Moreira; Teoria dos Grafos e Aplicaco~es, Dep.
Matematica, U. Aveiro
[2] De Carvalho, Marco Antonio Garcia; Teoria dos Grafos - Uma Introduca~o CESET Limeira, SP Brasil (2005)
[3] Diestel, Reinhard; Graph Theory, Springer - Verlag Heidelberg New
York (Electronic Version 2005)
[4] Feolo, Paulo, Exerccios de Teoria dos Grafos IME, USP 2005
[5] Feolo, Paulo; Kohayakawa, Yoshiharu; Wakabayashi, Yoshiko;
Uma introduca~o Suscinta a Teoria dos Grafos
[6] Pinto, Jose Sousa; Topicos de Matematica Discreta (Texto de Apoio
2005/2006) Dep. Matematica, U. Aveiro 199
51