Anjolina Grisi de Oliveira
obs: muitos slides foram cedidos por
Adolfo Almeida Duran (UFBA)
2005
• Determine se os seguintes grafos são bipartidos
Matemática Discreta/Grafos CIn-UFPE
2
Grafo bipartido?
v1
v2
v4
v3
Matemática Discreta/Grafos CIn-UFPE
3
Determine se os seguintes grafos são bipartidos
Matemática Discreta/Grafos CIn-UFPE
4
Outros tipos de grafos
Grafo cíclico (ou simplesmente Ciclo)
Um grafo conectado que é regular de grau 2 é
um grafo cíclico (= ciclo)
Cn é um grafo cíclico com n vértices
C6
Matemática Discreta/Grafos CIn-UFPE
5
Grafo roda
O grafo obtido a partir de Cn-1 através da
ligação de cada vértice a um novo vértice v é
um grafo roda em n vértices, Wn
C5
W6
Matemática Discreta/Grafos CIn-UFPE
6
Grafos n-cúbicos
Os grafos n-cúbicos, denotados por Qn, são
grafos cujos vértices representam as 2n
cadeias de bits de tamanho n.
Dois vértices são adjacentes se e somente se
as cadeias de bits que eles representam
diferem em exatamente uma posição de bit.
Matemática Discreta/Grafos CIn-UFPE
7
Grafos Orientados ou Dígrafos
Um dígrafo G(V,A) é um conjunto finito não vazio V de
vértices, e um conjunto A de pares ordenados de
elementos de V. Chamamos o conjunto A de arcos
(também podemos chamar de arestas).
Multigrafo Orientado G(V,A)
Consiste de um conjunto V não vazio de vértices, um
conj. A de arestas e uma função f de A em {(u,v) | u,vV}.
As arestas e1 e e2 são múltiplas se f(e1) = f(e2).
Matemática Discreta/Grafos CIn-UFPE
8
Revisando
Tipo
Arestas Múltiplas?
Laços?
------------------------------------------------------------------Simples
não dir. Não
Não
Multigrafo
não dir. Sim
Não
Pseudografo
não dir, Sim
Sim
Direcionado
dir.
Não
Sim
Multigrafo dir.
dir.
Sim
Sim
Matemática Discreta/Grafos CIn-UFPE
9
• Os vértices de um dígrafo possuem:
– Grau de entrada: número de arcos que chegam no vértice
(grauent(v))
– Grau de saída: número de arcos que partem do vértice
(grausai(v))
Proposição
 grauent(vi) =  grausai(vi) = | A |
Matemática Discreta/Grafos CIn-UFPE
10
Representação de grafos
Embora seja conveniente a
representação de grafos através de
diagramas de pontos ligados por
linhas, tal representação é
inadequada se desejamos armazenar
grandes grafos em um computador
Matemática Discreta/Grafos CIn-UFPE
11
Lista de adjacência
Uma maneira simples de armazenar grafos, é
listando os vértices adjacentes a cada vértice do
grafo
u
y
v
x
w
u: v,y
v: u,y,w
w: v,x,y
x: w,y
y: u,v,w,x
Matemática Discreta/Grafos CIn-UFPE
12
Lista de adjacência em grafos direcionados
Tabela com vértices iniciais e finais (terminais)
y
x
u
w
v
Inic.
u:
v:
w:
x:
y:
Matemática Discreta/Grafos CIn-UFPE
Terminais
u,v
v
y,w
13
Matriz de adjacência
Se G é um grafo com vértices {1,2,3,...,n}, sua matriz
de adjacência é a matriz n X n cujo elemento ij é o
número de arestas ligando o vértice i ao vértice j
Matemática Discreta/Grafos CIn-UFPE
14
Matriz de adjacência
Se G é um grafo direcionado com vértices {1,2,3,...,n},
sua matriz de adjacência é a matriz n X n cujo
elemento ij é o 1 se existe uma arestas onde vi é o
vértice inicial e vj é o vértice final.
Já estudamos esse tipo de matriz na representação de
relações.
Se G é um multigrafo direcionado com vértices
{1,2,3,...,n}, sua matriz de adjacência é a matriz n X n
cujo elemento ij é o número de arestas onde vi é o
vértice inicial e vj é o vértice final.
A matriz de adjacência para grafos com direção não é
necessariamente simétrica.
Matemática Discreta/Grafos CIn-UFPE
15
Matriz de incidência
Se G é um grafo com vértices {1,2,3,...,n} e arestas
{1,2,3,...,m}, sua matriz de incidência é a matriz n X m
cujo elemento ij é igual a
– 1 se a aresta ej é incidente ao vértice vi, ou
– 0, caso contrário
Arestas múltiplas são representadas usando colunas
com entradas idênticas.
Laços são representados usando colunas com
extamente uma entrada igual a 1.
Matemática Discreta/Grafos CIn-UFPE
16
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
17
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 se
denotado por um
seqüência de vértices:
(x2, x5, x4, x1)
Matemática Discreta/Grafos CIn-UFPE
18
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
19
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
20
• Ciclo (ou circuito)
A seqüência de vértices
(x1, x2, x5, x4, x1)
é um exemplo de ciclo
Matemática Discreta/Grafos CIn-UFPE
21
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
22
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
23
• 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
24
• 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
25
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
26
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
27
• 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
28
•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
29
Circuito Euleriano
Um circuito euleriano em um grafo G é um
circuito simples que contem cada aresta de G.
Matemática Discreta/Grafos CIn-UFPE
30
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
31
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
32
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
33
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
34
Algoritmo de Hierholzer
Algoritmo para a construção de um ciclo euleriano
sugerido a partir da prova do teorema de Euler
Matemática Discreta/Grafos CIn-UFPE
35
• 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
36
• 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
37
Algoritmo de Fleury
Algoritmo para a construção de um ciclo euleriano
em um grafo euleriano
Comece em qualquer vértice u e percorra as
arestas de forma aleatória, seguindo sempre as
seguintes regras:
I – apague as arestas depois de passar por elas
II – se aparecer algum vértice isolado, apague-o
também
III – passe por uma ponte somente se não houver
outra alternativa
Matemática Discreta/Grafos CIn-UFPE
38
Algoritmo de Fleury
Algoritmo para a construção de um ciclo euleriano
em um grafo euleriano
Matemática Discreta/Grafos CIn-UFPE
39
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
40
Mais exemplos
Circuito e caminho
caminho
Matemática Discreta/Grafos CIn-UFPE
não
hamiltoniano
41
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
42
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”
Matemática Discreta/Grafos CIn-UFPE
43
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
44
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
45
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
46
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
47
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
48
Alguns Problemas
Como explorar um grafo
Como obter um processo sistemático para caminhar
pelos vértices e arestas de um grafo?
Como caminhar no grafo de modo a visitar todos os
vértices e arestas evitando repetições
desnecessárias de visitas a um mesmo vértice ou
aresta?
Que recursos adicionais são necessários?
Matemática Discreta/Grafos CIn-UFPE
49
Como explorar um grafo
Necessidade de ‘’marcar’’ quando um vértice e uma
aresta já foram visitados ou não
Algoritmo Geral
Busca Geral G(V,E)
1. Escolher e marcar um vértice inicial;
2. Enquanto existir algum vértice v marcado e incidente a
uma aresta (v,w), não explorada, efetuar:
a) escolher o vértice v;
b) explorar a aresta (v,w). Se w não é marcado então
marcar w.
Matemática Discreta/Grafos CIn-UFPE
50
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
51
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
52
O problema do Caminho mais curto
Uma maneira mais eficiente:
Percorra o grafo, partindo do vértice de origem s,
associando a cada vértice um número l(v) indicando a
menor distância entre s e v.
Isso significa que quando chegamos ao vértice v, na
figura abaixo, l(v) será min ( l(u)+6 , l(x)+4 )
u
v
6
3
s
2
1 4 2 7
3
5
x
6
y
Matemática Discreta/Grafos CIn-UFPE
53
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
54
Como obter um caminho mínimo partindo de s para y?
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
55
Outra possibilidade:
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
56
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
57
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
58
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
59
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
60
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
61
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
2
D
3
F
10
E
Matemática Discreta/Grafos CIn-UFPE
62