Anjolina Grisi de Oliveira
obs: muitos slides foram cedidos por
Adolfo Almeida Duran (UFBA)
2007
Conectividade
Caminho em um grafo não orientado
– Um caminho de tamanho n de u para v, onde n é um
inteiro positivo, em um grafo não orientado é uma
seqüência de arestas e1,...,en do grafo de forma que
f(e1) = {x0,x1}, f(e2) = {x1,x2}...f(en)={xn-1,xn}, onde x0=u
e xn=v.
G1
Se o grafo é simples,
denotamos o caminho
por sua seqüência de
vértices: x0, x1 ,...xn
Matemática Discreta/Grafos CIn-UFPE
2
Conectividade
• Caminho em um multigrafo direcionado
– Um caminho de tamanho n de u para v, onde n é um
inteiro positivo, em um multigrafo direcionado é uma
seqüência de arestas e1,...,en do grafo de forma que
f(e1) =(x0,x1), f(e2) = (x1,x2)...f(en)=(xn-1,xn), onde x0=u e
xn=v.
Quando não existem
arestas múltiplas, o
caminho pode ser
denotado por uma
seqüência de vértices:
(x2, x5, x4, x1)
Matemática Discreta/Grafos CIn-UFPE
3
Conectividade
Circuito ou ciclo
– Um caminho é um circuito se ele começa e
termina no mesmo vértice.
G1
Circuito: x1,x2,x5,x4,x1
Matemática Discreta/Grafos CIn-UFPE
4
Exemplos de ciclos
1
2
3
4
Ciclo de tamanho 3
1241
1
2
3
4
Ciclo de tamanho 3
1231
Matemática Discreta/Grafos CIn-UFPE
5
• Ciclo (ou circuito)
A seqüência de vértices
(x1, x2, x5, x4, x1)
é um exemplo de ciclo
Matemática Discreta/Grafos CIn-UFPE
6
Caminho (ou circuito) simples
Um caminho ou circuito é chamado de simples se
ele não contem a mesma aresta mais de uma
vez.
Matemática Discreta/Grafos CIn-UFPE
7
Conectividade
Definição para grafos não orientados
– Um grafo não orientado é chamado de conexo
(ou conectado) se existe um caminho entre
cada par de vértices distintos do grafo.
G1
Em uma rede de
computadores, quaisquer
dois computadores podem
se comunicar se e
somente se o grafo da
rede é conexo.
Matemática Discreta/Grafos CIn-UFPE
8
• Grafo desconexo
– O grafo mostrado a seguir não é conexo pois, por
exemplo, não existe um caminho entre x3 e x5.
Matemática Discreta/Grafos CIn-UFPE
9
• Componente conexa
– Um grafo G(V,A) desconexo é formado por pelo menos
dois subgrafos conexos, disjuntos em relação aos vértices
– Cada um destes subgrafos conexos é dito ser uma
componente conexa de G.
Matemática Discreta/Grafos CIn-UFPE
10
Vértice de corte (ou pontos de articulação)
Um vértice é dito ser um vértice de corte se
sua remoção (juntamente com as arestas a
ele conectadas) produz um grafo com mais
componentes conexos. (se o grafo original é
conexo, ele se torna desconexo).
X2 é um vértice de corte
Matemática Discreta/Grafos CIn-UFPE
11
Ponte
Uma aresta é dita ser uma ponte se sua
remoção produz um grafo com mais
componentes conexos.
(X1,X4) é uma ponte
Matemática Discreta/Grafos CIn-UFPE
12
• Grafo fortemente conexo
– No caso de grafos orientados (digrafos), um grafo é dito
ser fortemente conexo se existe um caminho de a para b
e de b para a, para cada par a,b de vértices do grafo.
– ou seja, se cada par de vértices participa de um circuito.
– Isto significa que cada vértice pode ser alcançável
partindo-se de qualquer outro vértice do grafo.
Matemática Discreta/Grafos CIn-UFPE
13
•Grafo fracamente conexo
Um grafo direcionado G(V,A) é chamado de
fracamente conexo se existe um caminho entre
cada par de vértices no grafo não orientado
subjacente.
Cada um destes
subgrafos é
fortemente conexo.
No entanto, o grafo
todo é apenas
fracamente conexo.
Matemática Discreta/Grafos CIn-UFPE
14
• Caminhos e Isomorfismo
– A existência de circuitos simples com um tamanho n é
uma invariante
Matemática Discreta/Grafos CIn-UFPE
15
• Caminhos e Isomorfismo
- Além disso, caminhos podem ser usados para construir
mapeamentos, que podem ser isomorfismos.
u2
v1
u1
u3
u5
u4
v5
v2
v4
v3
Caminho1: u1, u4, u3,u2, u5
Caminho2: v3, v2, v1,v5, v4
Matemática Discreta/Grafos CIn-UFPE
16
• Contando caminhos entre vértices
• Teorema: Seja G um grafo cuja matriz de adjacência A usa a
seguinte ordem nos vértices: v1,v2,...,vn. A quantidade de
caminhos diferentes de tamanho r de vi para vj, onde r é um
inteiro positivo é igual a ai,j entrada da matriz Ar
a
b
d
c
a,b,a,b,d
a,b,a,c,d
a,b,d,b,d
a,b,d,c,d
a,c,a,b,d
a,c,a,c,d
a,c,d,b,d
a,c,d,c,d
Matemática Discreta/Grafos CIn-UFPE
17
Circuito Euleriano
Um circuito euleriano em um grafo G é um
circuito simples que contem cada aresta de G.
Matemática Discreta/Grafos CIn-UFPE
18
Teorema (Euler 1736)
Um multigrafo conectado G possui um circuito
euleriano se e somente se o grau de cada vértice
de G é par.
Prova:
Ida: Seja G um grafo euleriano. Por cada ocorrência de
vértice do circuito euleriano, existe uma aresta que chega
nesse vértice e outra que sai desse vértice. Como toda
aresta faz parte do circuito, isto é, nenhuma aresta fica
fora do ciclo, necessariamente o número de arestas por
cada vértice é par.
Matemática Discreta/Grafos CIn-UFPE
19
Volta: Suponhamos que todos os vértices possuem
grau par. Seja vi um vértice do grafo. Tentemos, a partir
de vi, construir um caminho que não passa duas vezes
pela mesma aresta, e até que não seja possível
continuar. Como todos os vértices possuem um grau
par, sempre será possível entrar e sair de um vértice. A
única exceção é o vértice vi onde o caminho vai
terminar. Se esse caminho, que chamaremos C1,
contém todas as arestas de G, temos um ciclo
euleriano. Senão, retiramos de G todas as arestas que
fazem parte de C1. No grafo resultante G', todos os
vértices também possuem grau par e necessariamente
um deles faz parte de C1, senão o grafo não seria
conexo.
Matemática Discreta/Grafos CIn-UFPE
20
Volta (cont.): Recomeçamos o mesmo processo com o
grafo G', partindo de um vértice comum com C1,
obtendo assim um novo circuito C2. A figura abaixo
mostra que dois circuitos que têm um vértice em
comum podem formar um circuito único: chegando no
vértice comum em um dos dois circuitos, continuamos
o percurso no outro circuito. Continuando esse
processo, necessariamente obteremos um circuito
único que contém todas as arestas de G.
Matemática Discreta/Grafos CIn-UFPE
21
• As pontes de Königsberg
É possível sair de uma das ilhas, passar uma
única vez por cada uma das pontes e retornar ao
ponto de origem ?
Matemática Discreta/Grafos CIn-UFPE
22
• As pontes de Königsberg
Como nem todos os vértices têm grau par, o grafo
não é euleriano. Logo, é impossível atravessar
todas as pontes uma só vez e voltar ao lugar de
partida
Matemática Discreta/Grafos CIn-UFPE
23
Aplicação em jogos
Como fazer um desenho que comece a partir de um ponto,
retorne a esse ponto e o lápis não seja levantado do
papel?
Podemos construir um circuito Euleriano
Existem vários algoritmos para construir um circuito
Euleriano
Vamos estudar um baseado na prova do teorema de
Euler
Matemática Discreta/Grafos CIn-UFPE
24
Algoritmo de Hierholzer
Algoritmo para a construção de um ciclo euleriano
sugerido a partir da prova do teorema de Euler
Comece em qualquer vértice u e percorra aleatoriamente
as arestas ainda não visitadas a cada vértice visitado até
fechar um ciclo
Se sobrarem arestas não visitadas, recomece a partir de
um vértice do ciclo já formado
Se não existem mais arestas não visitadas, construa o
ciclo euleriano a partir dos ciclos formados, unindo-os a
partir de um vértice comum
Matemática Discreta/Grafos CIn-UFPE
25
Algoritmo de Hierholzer
Algoritmo para a construção de um ciclo euleriano
sugerido a partir da prova do teorema de Euler
Ciclo 1: 1,2,5,9,10,11,6,3,1
Ciclo 2: 2,6,5,10,6,7,12,8,7,4,3,2
Ciclo Euleriano: 1,2,6,5,10,6,7,12,8,7,4,3,2,5,9,10,11,6,3,1
Matemática Discreta/Grafos CIn-UFPE
26
Algoritmo de Hierholzer
1
3
4
2
5
6
9
10
7
8
11
Ciclo 1: 1,2,5,9,10,11,6,3,1
12
Ciclo 2: 2,6,5,10,6,7,12,8,7,4,3,2
Ciclo Euleriano: 1,2,6,5,10,6,7,12,8,7,4,3,2,5,9,10,11,6,3,1
Matemática Discreta/Grafos CIn-UFPE
27
Teorema
Um multigrafo conectado G possui um caminho
euleriano, mas que não é circuito, se e somente se
possui exatamente dois vértices com grau ímpar
i
i
f
f
Matemática Discreta/Grafos CIn-UFPE
28
Caminhos, circuitos Hamiltonianos
Um caminho (ou circuito) em um grafo G(V,E)
é dito ser hamiltoniano se ele passa
exatamente uma vez em cada um dos vértices
de G
Caminho e circuito
hamiltoniano
Apenas caminho
hamiltoniano
Matemática Discreta/Grafos CIn-UFPE
29
Mais exemplos
Circuito e caminho
caminho
Matemática Discreta/Grafos CIn-UFPE
não
hamiltoniano
30
Grafo hamiltoniano
Não existe uma caracterização para identificar grafos
hamiltonianos como existe para os eulerianos
A busca de tal caracterização é um dos maiores
problemas ainda não solucionados da teoria dos
grafos
Matemática Discreta/Grafos CIn-UFPE
31
Grafo hamiltoniano
Muito pouco é conhecido dos grafos hamiltonianos
A maioria dos teoremas existentes são da forma: “Se
G possui arestas suficientes, então G é hamiltoniano”
Eles dão condições suficientes apenas
Se P então Q: P → Q
P é condição suficiente para Q
(basta que P ocorra para Q ocorrer)
Q é condição necessária para P
(se Q não ocorrer então P também não ocorrerá)
Matemática Discreta/Grafos CIn-UFPE
32
Circuito hamiltoniano em grafos completos
Todo grafo completo, que contém mais
de 2 vértices contem um circuito
hamiltoniano
Seja v1,v2,...,vn os vértices de G. Como
existe uma aresta entre qualquer par de
vértices, é possivel, a partir de v1 percorrer
essa sequência até vn e voltar para v1
Matemática Discreta/Grafos CIn-UFPE
33
Teorema (Dirac 1952)
Uma condição suficiente, mas não necessária,
para que um grafo conexo simples G com n (>2)
vértices tenha um circuito hamiltoniano é que o
grau de todo vértice de G seja  n/2
O grafo abaixo, possui um circuito hamiltoniano mas não
respeita a condição do teorema de Dirac
Matemática Discreta/Grafos CIn-UFPE
34
Teorema (Ore 1960)
Uma condição suficiente, mas não necessária, para
que um grafo simples G com n (>2) vértices tenha
um circuito hamiltoniano é que a soma dos graus de
cada par de vértices não adjacentes seja no mínimo
n.
Permite identificar mais grafos com circuitos hamiltonianos
que o anterior, mas demora muito para efetuar os
cálculos. Uma busca por tentativa e erro pode ser mais
eficiente em alguns casos
Matemática Discreta/Grafos CIn-UFPE
35
O adjetivo "hamiltoniano" deve-se ao matemático
irlandês Sir William Rowan Hamilton (1805-1865).
Diz-se que ele inventou um jogo que envolve um
dodecaedro (sólido regular com 20 vértices, 30
arestas e 12 faces).
Hamilton rotulou cada vértice do dodecaedro com o
nome de uma cidade conhecida.
O objetivo do jogo era que o jogador viajasse "ao
redor do mundo" ao determinar uma viagem circular
que incluísse todas as cidades exatamente uma vez,
com a restrição de que só fosse possível viajar de
uma cidade a outra se existisse uma aresta entre os
vértices correspondentes.
Matemática Discreta/Grafos CIn-UFPE
36
A figura abaixo mostra um grafo que
representa este problema, ou seja os vértices
e arestas de um dodecaedro.
Matemática Discreta/Grafos CIn-UFPE
37
Ciclo Hamiltoniano
origem
Matemática Discreta/Grafos CIn-UFPE
38
O problema do Caminho mais curto
Um motorista deseja encontrar o caminho, mais curto
possível, entre duas cidades do Brasil
Caso ele receba um mapa das estradas de rodagem do
Brasil, no qual a distância entre cada par adjacente de
cidades está exposta, como poderíamos determinar uma
rota mais curta entre as cidades desejadas?
Uma maneira possível é enumerar todas as rotas
possíveis que levam de uma cidade à outra, e então
selecionar a menor.
Matemática Discreta/Grafos CIn-UFPE
39
O problema do menor caminho consiste em
determinar um menor caminho entre um
¨
vértice
de origem s  V e todos os vértices v
de V.
Matemática Discreta/Grafos CIn-UFPE
40
Grafos com pesos:
- Cada aresta possui um número associado (peso)
- O tamanho do caminho é a soma dos pesos das
arestas do caminho
u
v
6
3
9
3
s
2
0
4
1
2
7
3
5
5
x
6
11
y
Matemática Discreta/Grafos CIn-UFPE
41
O algoritmo de Dijkstra
O algoritmo de Dijkstra aqui descrito identifica o menor
caminho entre dois vértices de um grafo não orientado.
Se desejamos calcular o menor caminho de a para z em
um grafo conexo simples com pesos, primeiro
encontramos um menor caminho entre a e um primeiro
vértice, depois entre a e um segundo vértice, esse
procedimento é repetido até que seja encontrado um
menor caminho entre a e z.
Matemática Discreta/Grafos CIn-UFPE
42
O algoritmo de Dijkstra
Um conjunto S de vértices é construído inserindo-se um
vértice a cada iteração.
A cada iteração também é adotado um procedimento
para rotular vértices: um vértice w é rotulado com o
tamanho do menor caminho de a até ele, e que contem
somente vértices do conjunto S.
O vértice a ser inserido em S é aquele com o menor
rótulo.
Matemática Discreta/Grafos CIn-UFPE
43
O algoritmo de Dijkstra
O algoritmo começa rotulando a com 0 e os demais
vértices com . Usamos a notação L0(a)=0 e L0(v)= .
(na iteração 0).
A notação Sk é usada para denotar o conjunto S após a
iteração k. Começamos com S0=. O conjunto Sk é
formado a partir de Sk-1 adicionado-se um vértice u que
não está em Sk-1 e possui o menor rótulo.
Após a inclusão de u em Sk, atualizamos os rótulos de
todos os vértices que não estão nesse conjunto da
seguinte maneira: Lk(v) é o tamanho do menor caminho
de a até v que contem apenas os vértices de Sk.
Matemática Discreta/Grafos CIn-UFPE
44
O algoritmo de Dijkstra
Seja v um vértice que não está em Sk. Para atualizar o
rótulo de v, observe que Lk(v) é o tamanho do menor
caminho de a para v e que contém apenas os vértices
que estão em Sk..
Esse caminho ou é o menor caminho que contem
apenas os elementos de Sk-1 (sem a inclusão de u) ou é
o menor caminho de a até u no passo k-1 com adição da
aresta (u,v).
Lk(v) = min(Lk-1(v),Lk-1(u)+ peso(u,v))
Matemática Discreta/Grafos CIn-UFPE
45
O algoritmo de Dijkstra
procedimento Dijkstra
Para i := 1 até n:
L(v)= .
L(a) = 0
S=
Enquanto z S
u := Elemento que S e L(u) é mínimo
S := S  {u}
Para cada vértice v  S :
Se L(u) + peso(u,v) < L(v) então
L(v) = L(u) + peso(u,v)
(observe que L(v) = min(L(v),L(u)+ peso[u,v])
Retornar L(z)
Matemática Discreta/Grafos CIn-UFPE
46
Exemplo: Qual o tamanho do menor caminho de A até D?
0: L(A)=0 e todos os outro é ; S=;
Seja u o nó de menor rótulo.
1: S= S  {u}. Logo, S={A}
B

5
C
4
6
8
1
A
2
D
0
2
3

F
10
E
Matemática Discreta/Grafos CIn-UFPE
47
2: Para cada vértice v  S : (S aqui apenas possui A)
Se L(u) + peso(u,v) < L(v) então
L(v) = L(u) + peso(u,v)
(lembrando que u acabou de ser incluído em S)
Logo: L(B)=4; L(F)=2;
B
(A)
4
5
C
4
6
8
1
A
2
D
0
2
3
F2
(A)
10
E
Matemática Discreta/Grafos CIn-UFPE
48
Próximo passo: colocar em S o nó de menor rótulo
S={A}{F}
Em seguida, atualizar os rótulos a partir de F
L(B)=3; L(C)=10; L(E)=12;
B
(A,F)
(A,F)
34
5
C 10

4
6
8
1
A
2
D
0
2
3
F2
(A)
10
12
E (A,F)
Matemática Discreta/Grafos CIn-UFPE
49
Próximo passo: colocar em S o nó de menor rótulo
S={A,F}{B}
Em seguida, atualizar os rótulos a partir de B:
L(C)=8;
(A,F,B)
(A,F)
B
3
5
C 10
8
4
6
8
1
A
2
D
0
2
3
F2
10
(A)
E
12
(A,F)
Matemática Discreta/Grafos CIn-UFPE
50
Próximo passo: colocar em S o nó de menor rótulo
S={A,F,B}{C}
Em seguida, atualizar os rótulos a partir de C:
L(D)=14; L(E)=10;
(A,F,B)
(A,F)
B
3
5
C8
4
6
8
1
A
2
D
14

0
2
(A,F,B,C)
3
2
F
(A,F)
10
12
E 10
Matemática Discreta/Grafos CIn-UFPE
(A,F,B,C)
51
Próximo passo: colocar em S o nó de menor rótulo
S={A,F,B,C}{E}
Em seguida, atualizar os rótulos a partir de E:
L(D)=13;
B
(A,F)
3
5
C8
(A,F,B)
4
6
1
A
8
2
D
13
14
0
2
(A,F,B,C)
3
10
2
F (A)
E 10
Matemática Discreta/Grafos CIn-UFPE
(A,F,B,C)
52
Exemplo: Menor caminho de A até D
0: L(A)=0 e todos os outro é ; S=;
1: S={A}; L(B)=4; L(F)=2;
2: S={A,F}; L(B)=3; L(C)=10; L(E)=12;
3: S={A,F,B}; L(C)=8;
4: S={A,F,B,C}; L(D)=14; L(E)=10;
5: S={A,F,B,C,E}; L(D)=13;
6: S={A,F,B,C,E,D}
B
5
C
4
6
8
1
A
2
D
(A,F,B,C.E)
13
2
3
F
10
E
Matemática Discreta/Grafos CIn-UFPE
53