Teoria dos Grafos
Definições
•• Dois
Dois tipos
tipos de
de elementos:
elementos:
–– Vértices
Vértices ou
ou nós.
nós.
–– Arestas.
.
Arestas
Arestas.
Definições e Conceitos Básicos
v3
v1
v4
v2
v5
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
v6
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Grafo Simples
Grafo Simples
G
G == (V,
(V, E)
E)
VV éé um
um conjunto
conjunto finito
finito não-vazio
não-vazio de
de vértices.
vértices.
EE éé um
conjunto
finito
de
arestas.
um conjunto finito de arestas.
Se
Se ee ЄЄ E,
E, éé um
um conjunto
conjunto da
da forma:
forma:
ee == {{ v,
v, w}
w} == vw
vw == wv,
wv, onde
onde v,w
v,w ЄЄ V.
V.
ee éé incidente
incidente aa vv ee w.
w.
vv ee ww são
são adjacentes
adjacentes ou
ou vizinhos.
vizinhos.
v3
v1
v4
v2
V = {v1, v2, v3, v4, v5, v6}
e1
v5
v6
E = {v1v2, v1v3, v2v3, v2v4, v2v5,
v3v4}
e1 é incidente a v2 e v5
v1, v3, v4 e v5 são adjacentes a v2
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Graus de Vértices
Graus de Vértices
•• Grau
Grau de
de um
um vértice
vértice vv (deg(v))
(deg(v)) éé oo número
número de
de arestas
arestas que
que
incidem
incidem em
em v.
v.
–– Vértice
Vértice ímpar.
ímpar.
–– Vértice
Vértice par.
par.
–– Vértice
Vértice isolado.
isolado.
•• Um
Um grafo
grafo éé regular
regular (k-regular)
(k-regular) se
se todos
todos os
os seus
seus vértices
vértices tem
tem
oo mesmo
mesmo grau
grau (k).
(k).
•• Seqüência
Seqüência de
de graus
graus de
de um
um grafo
grafo consiste
consiste em
em escrever
escrever em
em
ordem
ordem crescente
crescente os
os graus
graus de
de seus
seus vértices.
vértices.
v3
v1
v4
v2
v6 é um vértice isolado. deg(v6) =
0
e1
v5
v6
v2 é um vértice par. deg(v2) = 4
v5 é um vértice ímpar. deg(v5) = 1
Seqüência de graus = 0, 1, 2, 2, 3, 4
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
1
Outros Tipos de Grafos
•• Pseudo-grafos:
Pseudo-grafos:
–– Multigrafos.
Multigrafos.
–– Grafos
Grafos com
com auto-laços.
auto-laços.
•• Grafos
Grafos dirigidos.
dirigidos.
•• Não
Não existe
existe terminologia
terminologia padronizada.
padronizada.
v3
v1
Auto-laço
v4
v2
e1
v5
v6
deg(v4) = 4
deg(v3) = 5
Vamos usar o termo grafo para representar grafos finitos, não dirigidos,
com auto-laços e múltiplas arestas.
Multigrafo
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Proposições Importantes
•A
•A partir
partir do
doconceito
conceito de
de adjacência
adjacência eegraus
graus de
de vértices.
vértices.
•Prova
•Prova éé intuitiva.
intuitiva.
•Como
•Como conseqüência:
conseqüência: número
número de
de vértices
vérticesímpares
ímpares éé par.
par.
v3
v1
v4
v2
№ de vértices ímpares = 2 = v3 e
v5
Proposição de Euler:
v5
n
deg vi
v6
Σ deg(vi) = 2 + 4 + 3 + 2 + 1 + 0 = 12 = 2 x
6
2E
i 1
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Isomorfismo de Grafos
Isomorfismo de Grafos
•• Dois
Dois grafos
grafos são
são isomórficos:
isomórficos:
–– São
São essencialmente
essencialmente iguais.
iguais.
–– Correspondência
Correspondência entre
entre os
os vértices
vértices ee arestas.
arestas.
•• Sejam
Sejam G1=
G1= (V1,
(V1, E1)
E1) ee G2
G2 == (V2,
(V2, E2):
E2):
–– G1
G1 ≈≈ G2,
G2, se
se existir
existir uma
uma bijeção
bijeção f:f: V1
V1 →
→ V2:
V2:
•• Se
Se vw
vw éé uma
uma aresta
aresta de
de E1,
E1, então
então f(v)f(w)
f(v)f(w) éé aresta
aresta de
de
E2.
E2.
•• Toda
Toda aresta
aresta em
em E2
E2 tem
tem aa forma
forma de
de f(v)f(w)
f(v)f(w) para
para
alguma
alguma aresta
aresta vw
vw єE1.
єE1.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
u
v
w
x
y
z
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
2
Isomorfismo de Grafos
Isomorfismo de Grafos
u
v
w
x
y
z
•• Isomorfismo
Isomorfismo preserva:
preserva:
–– Simetria:
Simetria: G1
G1 ≈≈ G2
G2 ↔
↔ G2
G2 ≈≈ G1.
G1.
–– Reflexividade:
Reflexividade: G
G ≈≈ G.
G.
–– Transitividade:
Transitividade: G1
G1 ≈≈ G2
G2 ee G2
G2 ≈≈ G3
G3 →
→ G1
G1 ≈≈ G3.
G3.
•• Proposições
Proposições válidas
válidas se
se G1
G1 ≈≈ G2:
G2:
–– G1
G1 ee G2
G2 têm
têm oo mesmo
mesmo número
número de
de vértices.
vértices.
–– G1
G1 ee G2
G2 têm
têm aa mesma
mesma seqüência
seqüência de
de graus.
graus.
–– G1
G1 ee G2
G2 têm
têm oo mesmo
mesmo número
número de
de arestas.
arestas.
f(u) = azul, f(v) = roxo, f(w) = vermelho
f(x) = verde, f(y) = amarelo, f(z) = rosa
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Subgrafos
Subgrafos
•• G1
G1 == (V1,
(V1, E1)
E1) éé subgrafo
subgrafo de
de G2
G2 == (V2,
(V2, E2)
E2) sss:
sss:
–– V1
V1 éé subconjunto
subconjunto de
de V2;
V2; e,
e,
–– E1
E1 éé subconjunto
subconjunto de
de E2.
E2.
•• Subgrafos
Subgrafos podem
podem ser
ser obtidos
obtidos através
através da
da remoção
remoção de
de arestas
arestas
ee vértices.
vértices.
u
v
w
u
v
w
u
x
y
z
x
y
z
x
G1
G2
w
y
z
G3
G2 = G1 \ {uz}
G3 = G1 \ {v}
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
Grafos Completos e nulos
© Jorge Figueiredo, DSC/UFCG
Grafos Bipartidos
•• Grafo
Grafo nulo
nulo éé aquele
aquele em
em que
que EE == Ø.
Ø.
•• Um
Um grafo
grafo simples
simples éé completo
completo se
se qualquer
qualquer par
par de
de vértices
vértices
distintos
distintos éé adjacente.
adjacente.
–– Grafo
Grafo completo
completo de
de nn vértices
vértices éé dito
dito KKnn..
•• Grafo
Grafo bipartido
bipartido éé aquele
aquele em
em que
que VV pode
pode ser
ser dividido
dividido em
em dois
dois
subconjuntos
subconjuntos disjuntos
disjuntos não
não vazios
vazios V1
V1 ee V2.
V2.
–– Cada
Cada aresta
aresta conecta
conecta um
um vértice
vértice de
de V1
V1 ee um
um vértice
vértice de
de V2.
V2.
•• Grafo
Grafo bipartido
bipartido completo:
completo: cada
cada um
um dos
dos elementos
elementos de
de V1
V1 éé
adjacente
adjacente aa cada
cada um
um dos
dos elementos
elementos de
de V2.
V2.
K4
K3
Teoria dos Grafos
K5
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
3
Complemento de um Grafo
Grafos Bipartidos
u
x
v
w
y
z
V1 = {u, v, w}
V2 = {x, y, z}
•• Seja
Seja G
G um
um grafo
grafo simples:
simples:
–– G
é
complemento
G é complemento de
de G
G se:
se:
•• VV == V;
V; e,
e,
•• Dois
Dois vértices
vértices são
são adjacentes
adjacentes em
em G
G se
se ee somente
somente se
se
eles
eles não
não são
são adjacentes
adjacentes em
em G.
G.
K3,3
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Exercício
1.
1. Considere
Considere as
as 88 primeiras
primeiras letras
letras do
do seu
seu nome.
nome. Construa
Construa um
um
grafo
grafo em
em que:
que:
•• Toda
Toda vogal
vogal éé adjacente
adjacente aa toda
toda consoante.
consoante.
•• Nenhuma
Nenhuma vogal
vogal éé adjacente
adjacente aa outra
outra vogal.
vogal.
•• Nenhum
Nenhum consoante
consoante éé adjacente
adjacente aa outra
outra consoante.
consoante.
a)
a)
b)
b)
c)
c)
Teoria dos Grafos
Defina
Defina formalmente
formalmente esse
esse grafo.
grafo.
Determine
Determine oo complemento
complemento desse
desse grafo.
grafo.
ÉÉ um
um grafo
grafo bipartido?
bipartido? Justifique.
Justifique.
© Jorge Figueiredo, DSC/UFCG
4