Teoria dos grafos
Introdução
De um modo geral, a área de algoritmos em grafos pode ser considerada como aquela cujo
interesse principal é resolver problemas algorítmicos em grafos, tendo em mente uma
preocupação computacional. Ou seja, o objetivo principal é encontrar algoritmos, eficientes
se possível, para resolver um dado problema em grafos.
Há problemas não algorítmicos em grafos em que o conceito de eficiência torna-se sem
sentido. Por outro lado, a preocupação pela eficiência, na área de algoritmos, se traduz
também na formulação de problemas algorítmicos em grafos que talvez se encontrem fora
de interesses para a teoria. Não obstante, uma melhora na eficiência de um algoritmo para
um dado problema em grafos somente pode ser obtida através de um melhor conhecimento
teórico do problema.
O marco inicial da teoria dos grafos é um problema algorítmico. É o conhecido problema
da ponte de Königsberg resolvido por Euler em 1736. No rio Pregel, junto à cidade de
Königsberg (atual Kaliningrado) na então Prússia, existem duas ilhas formando portanto
quatro regiões distinguíveis da terra, A, B, C e D. Há um total de sete pontes interligandoas. O problema consiste em, partindo de uma dessas regiões, determinar um trajeto pelas
pontes segundo o qual se possa retornar à região de partida, após atravessar cada ponte
somente uma vez. Euler mostrou que não existe tal trajeto, ao utilizar um modelo em grafos
para uma generalização deste problema. Através deste modelo ele verificou que existe o
desejado trajeto se e somente se em cada região concorrer um número par de pontes.
Grafos
Um grafo G = (V, E) consiste de um conjunto finito e não vazio de vértices,V(G), e uma
família finita, E(G) de pares não ordenados de vértices chamados arestas.
A ordem de um grafo é a quantidade de vértices, e seu tamanho é a quantidade de arestas.
Se u e v são dois vértices de um grafo e se o par não ordenado {u, v} é uma aresta denotada
por e, diz-se que u e v são incidentes a e e e é incidente a ambos u e v.
O grau de um vértice v de G é o número de arestas incidentes à v, laços contados duas
vezes. Denota-se por d(v) ou deg(v).
Adj(v) denota o conjunto de vértices adjacentes à v: |Adj(v)| = d(v).
Exemplos: V(G) = {a, b, c, d, e}
E(G) = {(a, b), (b, c), (c, d), (b, d), (d, c)}
c
a
grau= 1
a
a
b
d
b
3
c
3
d
1
e
e
2
c
e
a
b
d
a
b
c
d
e
e
c
b
d
Duas ou mais arestas que unem o mesmo par de vértices distintos são chamadas de arestas
paralelas. Uma aresta que une dois vértices não distintos é chamado de laço. Um grafo
simples não possui arestas paralelas nem laços.
V(G) = {a, b, c, d}
E(G) = {(a, b), (a, b), (b, a), (b, c), (c, d), (d, d)}
b
a
c
d
Um grafo orientado (dirigido) ou dígrafo consiste de um conjunto finito V de vértices e
um conjunto E de pares ordenados de vértices distintos chamados arcos. Se o par
ordenado {u, v} é um arco a, diz-se que o arco a é orientado de u para v. O arco a é
adjacente ao vértice u e é adjacente ao vértice v.
V(G) = {a, b, c, d}
E(G) = {<a, b>, <a, b>, <b, a>, <b, c>, <c, d>, <d, d>}
b
a
d
c
Um grafo conexo é aquele composto por apenas um único componente (pedaço). Um grafo
desconexo possui mais de um componente.
a
a
f
d
c
b
f
d
c
b
e
e
Um grafo completo Kn é um grafo com n vértices no qual há exatamente uma aresta
juntando todos os pares de vértices.
O grafo K1 com um vértice e nenhuma aresta é chamada como grafo trivial.
O complemento de um grafo simples G, denotado por G, é o grafo simples tal que
V(G) = V(G)
(u, v) ∈ E(G) <==> (u, v) ∉ E(G)
a
b
d
c
a
b
d
c
Seja S ⊆ V(G). S é um conjunto independente se não existir aresta entre quaisquer dois
vértices de S, em G.
a
b
{b, d} é um conjunto independente de G
{a, c} é um conjunto independente de G
d
c
Um subgrafo H de um grafo G=(V, G) é um grafo tal que V(H) ⊆ V(G) e E(H) ⊆ E(G).
a
b
d
c
a
b
c
a
Se, além de ser um subgrafo, H possui toda aresta (a, b) de G com ambos os extremos em
V(H), dizemos que H é um subgrafo induzido ou gerado de G. Denota-se H = G[V(H)]
Um subgrafo gerador de G é um subgrafo H tal que V(H) = V(G)
a
b
d
a
b
c
não é induzido
é gerador
a
c
é induzido
não é gerador
a
b
d
não é induzido
não é gerador
c
é induzido
é gerador
Teorema 1: ∀ G, ∑ d(v) = 2m (m = quantidade de arestas)
v ∈ V(G)
cada aresta contribui com exatamente 2 unidades na soma dos graus.
à = 2m
Corolário 1: o número de vértices de grau ímpar em um grafo é par.
Consideremos dois conjuntos de V(G): P, formado pelos vértices de grau par e, I, formado
pelos vértices de grau ímpar
2m = ∑ d(v)
=
v ∈ V(G)
é par
∑ d(v) + ∑ d(v)
v∈P
v∈I
é par
obrigatoriamente é par
Portanto, |I| é par.
Um grafo G é regular se todos os vértices têm o mesmo grau. Em particular, se o grau de
cada vértice é r, então G é regular de grau r ou r-regular.
O símbolo ∆(G) denota o maior grau dos vértices de G, o símbolo δ(G) denota o menor
grau de G.
Se G é k-regular então, ∆(G) = δ(G) = k.
grau 0 à 0-regular
grau 3
3-regular
Kn é regular?
| Kn | = ?
Se G é um grafo simples, qual é o maior valor para ∆(G)?
Quantas arestas possui um grafo simples, k-regular com n vértices?
Um grafo bipartido é um grafo simples no qual o conjunto de vértices pode ser
particionado em dois conjuntos X e Y tal que todas as arestas estão entre um vértice de X e
um vértice Y; é representado como G = (X, Y, E).
O grafo bipartido completo Km,n é o grafo (X, Y, E) com m vértices em X e n vértices em
Y no qual há um aresta entre todos os vértices de X e todos os vértices de Y. A união de
dois grafos G1 = (V1, E1) e G2 = (V2, E2) é o grafo G = G1 ∪ G2 = (V, E), onde V é a união
de V1 e V2 e E é a união de E1 e E2.
bipartido completo
Quantos vértices e quantas arestas possui Km,n?
| V(Km,n )| = ?
| E(Km,n )| = ?
Isomorfismos de grafos
Grafos iguais: 2 grafos G e H são iguais se V(G) = V(H) e E(G) = E(H).
a
b
c
2
1
2
1
a
G
b
c
H
(1,b) ∈ E(G) e (1,b) ∈ E(H). Não são iguais, mas são isomorfos.
Dois grafos G e H são isomorfos se existem 2 funções bijetivas f:V(G) à V(H),
g:E(G)àE(H), tais que para toda aresta α em G, se u e v são os extremos de α, então f(u) e
f(V) são os extremos de g(α) em H. O par (f,g) é um isomorfismo de G em H.
α
u
g(α)
f, g
v
f(u)
f(v)
Se os grafos G e H são simples, então G e H são isomorfos se existir uma bijeção
f:V(G)àV(H) tal que se (u, v) ∈ E(G) então f(u), f(v)) ∈ E(H), ou seja, f preserva a relação
de adjacência.
-
G e H são isomorfos?
a
b
z
c
x
q
w
a
-
b
G
G, H e I são isomorfos?
c
y
t
k
H
G
-
Isomorfismo é uma relação de equivalência? (reflexiva, simétrica, transitiva)
-
quantos grafos simples distintos existem com três vértices: 1, 2, 3?
-
quantos grafos existem, a menos de isomolrfismos, com três vértices: 1, 2, 3?
-
se G ≅ H è |V(G)| = |V(H)| e |E(G)| = |E(H)|
-
para cada n > 1 quantos grafos completos com n vértices existem a menos de
ismorfismos?
-
Um grafo é auto-complementar se G ≅ G. Dê exemplos de grafos auto-complementares.
Automorfismo
Um automorfismo é um isomorfismo de G em G. Então, um automorfismo é uma
permutação dos vértices de G que preserva adjacências.
a
e
f
e
j
b
j
d
g
i
f
h
h
g
d
c
c
b
f(a)=b f(b)=c f(c)=d f(d)=e f(e)=a
f(f)=g f(g)=h f(h)=i f(i)=j f(j)=k
f é um automorfismo de G em G (rotaçãso de 72°)
Quais são os automorfismos de um triângulo com vértices (1,2,3)?
1
3
à
2
a
i
3
f: 1 2 3
231
2
1
2
1
3
1
3
2
1
2
3
3
1
2
2
3
1
Automorfismo (C3) = Aut(∆) = {1, (123), (132), (12), (13), (23)} = S3, grupo com a
operação de combinação de funções (elemento neutro e inverso).
(123) . (132) = 1
-
quais são os automorfismos de G:
a
b
d
-
quais são os automorfismos do C4?
c
Passeio
Um passeio P é uma seqüência finita e não-vazia (vo, α1, v1, α2, v2, ..., αk, vk) cujos
elementos são alternadamente vértices e arestas e tal que para todo 1<= i <= k vi-1 e vi são
extremos de αi.
Dizemos que P é um passeio de vo à vk.
Se k = 0, P é um passeio degenerado.
|P| = k. O comprimento de P é k.
α1
1
α4
α7
α6
4
2
α3
1α12α23α32α11α43α54α64α64 é um passeio
α2
1α12α33α54α64α71α43 é uma trilha
3
α5
Se as arestas α1, α2, ..., αk são 2 a 2 distintas, P é uma trilha (não pode repetir aresta). E,
além disso, os vértices forem 2 a 2 distintos, P é um caminho.
1α12α33α54 é um caminho
Se |P| > 0 e vo = vk, então P é um passeio fechado ou trilha fechada.
Trilhas fechadas: 1α12α23α41, 2α23α32, 1α74α53α41, 1α43α54α64α71
Se P é uma trilha fechada e os ‘vertices são distintos, então P é um ciclo ou circuito.
1α12α33α41 (ciclo)
2α23α32 (ciclo induzido)
1α74α53α41 (ciclo)
Se o grafo G for simples, a seqüencia de vértices determina o passeio.
-
demonstre que se existe um passeio de u a v em G, então existe um caminho de u a v
em G.
todo grafo simples G contém um caminho de comprimeto δ(G); se δ(G) >= 2, G contém
um ciclo de comprimento pelo menos δ(G) + 1.
Conexão
Sejam G um grafo e u e v dois vértices de G. Dizemos que u e v são oligados (conectados)
se existe um caminho de u a v em G.
Lema: ligação é uma relação de equivalência.
Demonstração:
reflexiva: ∀u ∈ V(G), u é ligado a u.
OK! P = (u) degenerado
simétrica: ∀u ∈ V(G), se existe um caminho P = (u=vo, α1, v1, α2, v2, ..., αn, vn=v)
de u a v em G, então existe um caminho Q de v a u em G.
Q = P-1 = (v, αn, ..., v2, α2, v1, α1, u) caminho reverso de P
transitiva: ∀u, v, w ∈ V(G), se existe um caminho P = (u=vo, α1, v1, ..., αn, vn=v) de
u a v em G e se existe um caminho Q = (v=v’o, β1, v’1, ..., βn, v’n=w) de v a w em G è
existe um caminho R de v a w em G.
Grafos Bipartidos
Teorema 2: um grafo é bipartido se e somente se não possui ciclos ímpares.
Dem.: suponha G bipartido com bipartição {X, Y}
Seja C = {u0, u1, ..., uk, uo} um ciclo em G
Sem perda de generalidade, seja u0 em X
Se |C| é ímpar è k = 2a (par) è uk ∈ X, mas existe (u0, uk) ∈ E(G), contradizendo
G ser grafo bipartido.