Teoria dos Grafos
Grafos Dirigidos
•Grafos
•Grafos Dirigidos
Dirigidos ou
ou Dígrafos:
Dígrafos:
–Conjunto
–Conjunto finito
finito não-vazio
não-vazio de
de vértices.
vértices.
–Conjunto
–Conjunto finito
finito de
de pares
pares ordenados
ordenados de
de vértices.
vértices.
–Chamamos
de
arcos
em
vez
de
arestas.
–Chamamos de arcos em vez de arestas.
–Um
–Um arco
arco (v,
(v, w)
w) éé reduzido
reduzido para
para vw.
vw.
–D
–D == (V,
(V, A)
A)
Grafos Dirigidos (Digrafos)
d
a
V = {a, b, c, d}
A = {ab, bb, bc, cb, cb, ca, dc}
b
c
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Grafos Dirigidos
Exemplo
•• Dígrafo
Dígrafo Simples:
Simples:
–– Todos
Todos os
os arcos
arcos são
são distintos.
distintos.
–– Não
Não existem
existem auto-laços.
auto-laços.
•• Para
Para obter
obter oo grafo
grafo correspondente
correspondente de
deum
um dígrafo:
dígrafo:
–– Eliminar
Eliminar as
as direções
direções dos
dos arcos.
arcos.
–– Não
Não necessariamente
necessariamente oo grafo
grafo correspondente
correspondente aa um
um dígrafo
dígrafo
simples
simples éé simples.
simples.
d
d
a
a
b
c
b
Dígrafo
Simples
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
4
Teoria dos Grafos
2
5
3
6
1
2
2
5
3
6
4
2
5
4
6
6
4
Grafo correspondente.
Não é simples.
Teoria dos Grafos
Representação por Lista de Adjacência
1
© Jorge Figueiredo, DSC/UFCG
Representação por Matriz de Adjacência
1
2
3
5
4
© Jorge Figueiredo, DSC/UFCG
c
Teoria dos Grafos
5
6
1
2
3
4
5
6
1
0
0
0
0
0
0
2
1
0
0
1
0
0
3
0
0
0
0
0
0
4
1
0
0
0
1
0
5
0
1
1
0
0
0
6
0
0
1
0
0
1
© Jorge Figueiredo, DSC/UFCG
1
Representação por Matriz de Incidência
1
e1
e2
2
4
e6
1 2 3 4 5 6 7
1 1 1 0 0 0 0 0
2 0 -1 -1 1 0 0 0
3 0 0 0 0 0 1 1
4 -1 0 1 0 -1 0 0
5 0 0 0 -1 1 -1 0
6 0 0 0 0 0 0 -1
e7
5
e5
•Os
•Os vértices
vértices de
de um
um dígrafo
dígrafo possuem:
possuem:
–Grau
–Grau de
de entrada:
entrada: número
número de
de arcos
arcos que
que chegam
chegam no
no
vértice.
vértice. (indeg(v))
(indeg(v))
–Grau
–Grau de
de saída:
saída: número
número de
de arcos
arcos que
que partem
partem do
do
vértice.
vértice. (outdeg(v))
(outdeg(v))
•Da
•Da mesma
mesma forma:
forma:
–Seqüência
–Seqüência de
de graus
graus de
de entrada.
entrada.
–Seqüência
–Seqüência de
de graus
graus de
de saída.
saída.
3
e4
e3
Grau de Vértices
6
e8
8
0
0
0
0
0
0
Proposição:
i
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
b
c
© Jorge Figueiredo, DSC/UFCG
Outros Conceitos
indeg(a) = 1
outdeg(a) = 1
indeg(b) = 4
outdeg(b) = 2
a
) = | A|
Teoria dos Grafos
Exemplo
d
i
seqüência indeg = 0, 1, 2, 4
seqüência outdeg = 1, 1, 2, 3
•Dois
•Dois dígrafos
dígrafos são
são isomórficos
isomórficos se:
se:
–Existe
–Existe um
um isomorfismo
isomorfismo entre
entre os
os respectivos
respectivos grafos
grafos
correspondentes.
correspondentes.
–Preserva
–Preserva aa ordem
ordem dos
dos vértices
vértices em
em cada
cada arco.
arco.
•Os
•Os conceitos
conceitos de
de passeio,
passeio, caminho,
caminho, ciclos,
ciclos, etc.
etc. são
são
semelhantes:
semelhantes:
–Deve
–Deve respeitar
respeitar aa orientação
orientação dos
dos arcos.
arcos.
|A| = 7
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
Exemplo
Digrafos Conectados
•D1
•D1 ee D2
D2 não
não são
são isomórficos.
isomórficos.
d
d
a
b
a
c
D1
© Jorge Figueiredo, DSC/UFCG
•• Um
Um dígrafo
dígrafo DD éé conectado
conectado se:
se:
–– Grafo
Grafo correspondente
correspondente éé conectado.
conectado.
•• DD éé fortemente
fortemente conectado
conectado se
se para
para quaisquer
quaisquer dois
dois vértices
vértices vv ee
w,
w, existe
existe um
um caminho
caminho entre
entre vv ee w.
w.
•• DD éé Euleriano
Euleriano se
se ee somente:
somente:
–– Fortemente
Fortemente conectado.
conectado.
–– indeg(vi)
indeg(vi) == outdeg(vi),
outdeg(vi), para
para todo
todo i.i.
D2
Exemplo de uma trilha: dcbca
Exemplo de um ciclo: cabc
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
2
Exemplo
d
a
b
Torneio
D1 é conectado.
D1 não é fortemente conectado.
D1 não é Euleriano.
c
a
b
D2 é conectado.
D2 é fortemente conectado.
D1 é Euleriano.
c
D2
•• Um
Um torneio
torneio éé um
um dígrafo
dígrafo em
em que
que para
para quaisquer
quaisquer 22
vértices
vértices distintos
distintos vv ee w,
w, existe
existe exatamente
exatamente um
um arco
arco
entre
entre eles:
eles: ou
ou vw
vw ou
ou wv.
wv.
•• O
O score
score de
de um
um vértice
vértice vv em
em um
um torneio
torneio éé igual
igual aa
outdeg(v).
outdeg(v).
•• AA seqüência
seqüência de
de score
score éé aa seqüência
seqüência de
de graus
graus de
de
saída.
saída.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
Exemplo
Mais Sobre Torneios
a
e
b
d
Torneio de tamanho 5.
score(a) = 3
score(b) = 2
seqüência de score = 0, 2, 2, 3, 3
•• Teorema:
Teorema: todo
todo torneio
torneio tem
tem um
um caminho
caminho Hamiltoniano.
Hamiltoniano.
•• Um
Um torneio
torneio éé transitivo
transitivo se
se ee somente
somente se:
se:
–– Sempre
Sempre que
que uv
uv ee vw
vw são
são arcos,
arcos, uw
uw também
também é.
é.
•• ÉÉ equivalente
dizer
de
um
torneio
T:
equivalente dizer de um torneio T:
–– TT tem
tem um
um único
único caminho
caminho Hamiltoniano.
Hamiltoniano.
–– TT éé transitivo.
transitivo.
–– Todo
Todo jogador
jogador (vértice)
(vértice) em
em TT tem
tem um
um score
score diferente.
diferente.
c
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
Exercício
© Jorge Figueiredo, DSC/UFCG
Exercício
1.
1. Professor
Professor Alencar
Alencar éé muito
muito metódico.
metódico. Todos
Todos os
os dias
dias pela
pela
manhã,
manhã, ele
ele segue
segue oo mesmo
mesmo ritual
ritual para
parase
se vestir.
vestir. Faz
Faz parte
parte
do
do seu
seu vestuário:
vestuário: cueca,
cueca, calça,
calça, cinto,
cinto, camisa,
camisa, gravata,
gravata,
paletó,
paletó, meias
meias ee sapato,
sapato, além
além de
de um
um vistoso
vistoso relógio
relógio de
de pulso.
pulso.
Ele
Ele sempre
sempre veste
veste aa cueca
cueca antes
antes de
de por
poras
as meias
meias ee aa calça.
calça.
Os
Os sapatos
sapatos são
são calçados
calçados após
após oo professor
professor ter
ter vestido
vestido aa
cueca,
cueca, calça
calça ee meias.
meias. O
O cinto
cinto vai
vai depois
depois da
da calça
calça ee da
da
camisa.
camisa. O
O relógio
relógio pode
pode ser
ser colocado
colocado em
em qualquer
qualquer momento.
momento.
O
O paletó
paletó só
só éé vestido
vestido depois
depois do
do cinto
cinto ee da
da gravata
gravata que
que éé
colocada
colocada depois
depois da
da camisa.
camisa. Modele
Modele aa rotina
rotina do
do Professor
Professor
Alencar
Alencar usando
usando grafos.
grafos.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
© Jorge Figueiredo, DSC/UFCG
2.
2. Considere
Considereaafigura
figuraabaixo
abaixoque
quemostra
mostraaaplanta
plantabaixa
baixade
deuma
umacasa.
casa.
ÉÉpossível
possívelidentificar
identificarportas
portasque
quedividem
dividemos
osdiversos
diversoscômodos
cômodosda
da
casa
casaeeportas
portasque
quedão
dãoacesso
acessoààparte
parteexterna
externada
dacasa.
casa.Utilize
Utilizeaa
teoria
dos
grafos
para
determinar
se
é
possível
começar
do
lado
teoria dos grafos para determinar se é possível começar do lado
de
defora
forada
dacasa,
casa,entrar
entrarna
nacasa
casaeevisitar
visitarcada
cadacômodo
cômodouma
umaúnica
única
vez
vez(sem
(semdeixar
deixaraacasa)
casa)e,
e,finalmente
finalmentesair
sairda
dacasa.
casa.Justifique.
Justifique.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
3