Teoria dos Grafos
Exemplos de Aplicação de Grafos
•• Planejamento
Planejamento eficiente
eficiente de
de roteamento
roteamento de
de pacotes
pacotes na
na
Internet.
Internet.
•• Definir
Definir melhor
melhor rota
rota de
de distribuição
distribuição de
de correspondência
correspondência nos
nos
postos
postos de
de distribuição
distribuição da
da ECT.
ECT.
•• Determinar
Determinar se
se uma
uma mensagem
mensagem pode
pode ser
ser trocada
trocada por
por dois
dois
computadores
computadores em
em uma
uma rede
rede (possivelmente
(possivelmente usando
usando links
links
intermediários)
intermediários)
Caminhos e Conectividade de Grafos
Idéia básica: determinar alcançabilidade entre os vértices
através de caminhamento em arestas.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Passeio (walk)
Passeio (walk)
•• Um
Um passeio
passeio em
em um
um grafo
grafo G=
G= (V,
(V, E)
E) éé uma
uma seqüência
seqüência
alternada
alternada de
de vértices
vértices ee arestas
arestas que
que começa
começa ee termina
termina com
com
vértices.
vértices.
•• AA seqüência
…, vvkk ,, ∀∀ vv11,, …,
…, vvkk ∈∈ V,
V, éé um
um passeio
passeio de
de vv11 aa
seqüência vv11,, …,
) ∈ E, 1 ≤ j ≤ |k – 1|.
vvkk ,, se
se (v
(vj,j, vvj+1
j+1) ∈ E, 1 ≤ j ≤ |k – 1|.
•• Um
Um passeio
passeio com
com kk vértices
vértices possui
possui kk –– 11 arestas.
arestas.
–– Neste
(v22,, vv33),),
Neste caso
caso teríamos
teríamos as
as seguintes
seguintes arestas:
arestas: (v
(v11,, vv22)) ,, (v
,v)
…,
…, (v
(vk-1
k-1, vkk)
•• O
O comprimento
comprimento de
de um
um passeio
passeio éé oo número
número de
de arestas
arestas do
do
passeio.
passeio.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
2
1
v
3
u
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Passeio (walk)
Passeio (walk)
2
1
4
v
3
u
5
4
Passeio: a seqüência u, 1, 4, 5, v
Teoria dos Grafos
2
1
v
3
u
5
4
5
O que dizer da seqüência u, 1, 4, 3, 5, 4, 3, 5, v ?
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
1
Caminho (Path)
Trilha (Trail), Circuito e Ciclo
•• Um
Um caminho
caminho ou
ou caminho
caminho simples
simples em
em um
um grafo
grafo éé um
um passeio
passeio
em
em que
que todos
todos os
os seus
seus vértices
vértices são
são distintos.
distintos.
•• Uma
Uma trilha
trilha ou
ou trajeto
trajeto em
em um
um grafo
grafo éé um
um passeio
passeio em
em que
que
todas
todas as
as suas
suas arestas
arestas são
são distintas.
distintas.
•• Um
Um trajeto
trajeto fechado
fechado ou
ou circuito
circuito em
em um
um grafo
grafo éé um
um trajeto
trajeto em
em
que
que oo vértice
vértice inicial
inicial ee oo vértice
vértice final
final são
são iguais.
iguais.
•• Um
Um cricuito
cricuito em
em que
que todos
todos os
os vértices
vértices são
são distintos
distintos (com
(com
exceção
exceção do
do primeiro
primeiro ee do
do último)
último) éé chamado
chamado de
de ciclo.
ciclo.
•• Um
Um grafo
grafo acíclico
acíclico éé aquele
aquele que
que não
não possui
possui ciclos.
ciclos.
•• Um
Um triângulo
triângulo éé um
um ciclo
ciclo de
de tamanho
tamanho 3.
3.
2
1
v
3
u
5
4
O passeio u, 1, 4, 3, 5, 4, 3, 5, v não constitui um caminho.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Grafos Conectados (ou Conexos)
•Um
•Um grafo
grafoééconectado
conectadose
seeesomente
somentese
seexiste
existe um
um caminho
caminho
entre
entre qualquer
qualquer par
par de
de vértices
vértices do
do grafo.
grafo.
•Um
•Umcomponente
componente de
de um
um grafo
grafo éé um
um subgrafo
subgrafo conectado
conectado
maximal.
maximal.
•Um
grafo
com
apenas
um
componente
é
um
grafo
•Um grafo com apenas um componente é um grafoconectado.
conectado.
a
b
d
c
e
f
Forneça exemplos de:
-Passeio que não é nem trilha nem caminho.
-Passeio que é trilha e não é caminho.
-Passeio fechado que não é circuito.
-Circuito que não é ciclo.
-Triângulo.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
Grafo Euleriano
Grafo Euleriano
•• Um
Um grafo
grafo conectado
conectado G
G éé dito
dito Euleriano
Euleriano se
se existe
existe uma
uma trilha
trilha
fechada
fechada contendo
contendo cada
cada uma
uma das
das arestas
arestas de
de G.
G.
•• O
O problema
problema das
das pontes
pontes (lembram
(lembram da
da primeira
primeira aula?)
aula?) éé
equivalente
equivalente aa identificar
identificar se
se oo grafo
grafo correspondente
correspondente éé
Euleriano.
Euleriano.
•• O
O KK55 éé Euleriano?
Euleriano?
Teorema: Um Grafo Conectado G é Euleriano se e somente se o
grau de cada vértice é par.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
© Jorge Figueiredo, DSC/UFCG
K5
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
2
Grafo Hamiltoniano
Exercício
•• Um
Um Grafo
Grafo Hamiltoniano
Hamiltoniano éé um
um grafo
grafo que
que contém
contém uma
uma trilha
trilha
fechada,
fechada, passando
passando exatamente
exatamente uma
uma única
única vez
vez em
em cada
cada um
um
dos
dos vértices.
vértices.
1.
1. Um
Um grafo
grafo G
G == (V,
(V, E)
E) éé conexo
conexo se
se ee somente
somente se
se possui
possui um
um
vértice
vértice vv ∈∈ V,
V, tal
tal que
que para
para cada
cada vértice
vértice ww ∈∈ VV existe
existe um
um
caminho
caminho de
de ww aa v.
v. Justifique.
Justifique.
2.
2. Prove
Prove que
que todo
todo grafo
grafo conexo
conexo com
com nn vértices
vértices tem
tem pelo
pelo
menos
menos nn -- 11 arestas.
arestas.
Teorema (Ore, 1960): Se G é um grafo com n (≥3) vértices, e se
deg(v) + deg(w) ≥ n para cada par de vértices não-adjacentes v e
w, então G é Hamiltoniano.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
3