Aula02_grafos

Prévia do material em texto

Teoria dos Grafos
Valeriano A. de Oliveira
So
orro Rangel
Silvio A. de Araujo
Departamento de Matemáti
a Apli
ada
antunes�ibil
e.unesp.br, so
orro�ibil
e.unesp.br, saraujo�ibil
e.unesp.br
AULA 2
Subgrafos; Trajetos, 
aminhos e 
ir
uitos; Grafos 
onexos;
Operações 
om grafos
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Subgrafos
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
De�nição 1. Um grafo H(V ′, A′) é um subgrafo de um grafo G(V,A)
se todos os vérti
es e todas as arestas de H perten
em a G
(V ′ ⊆ V, A′ ⊆ A), e 
ada aresta de H possui as mesmas extremidades
que em G. Denotamos um subgrafo através da mesma notação usada
para 
onjuntos, isto é H ⊂ G.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
Exemplo 2. Dado o grafo
1
2
3
4 5
a b
c d
e f
6
7
8 9 10
11
G:
os seguintes grafos são subgrafos de G:
1
3
4 5
a b
d
e f
6
9 10
11
G1:
2 5
a b
c d
e
8
G2:
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
As seguintes observações podem ser feitas:
1. Todo grafo é um subgrafo de si próprio.
2. Um subgrafo de um subgrafo de um grafo G também é um subgrafo
de G.
3. Um vérti
e de um grafo G é um subgrafo de G.
4. Uma aresta de um grafo G é um subgrafo de G.
De�nição 3. Dois subgrafos de um grafo G, G1 e G2, são
aresta-disjuntos se eles não possuem arestas em 
omum. Se G1 e G2 não
possuírem vérti
es em 
omum, os dois subgrafos são 
hamados de
vérti
e-disjuntos.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Exer
í
io: Considere os grafos
a
c d
e
G3: a
d
e
G4: b
c
f
G5:
Determine quais são:
- Aresta-disjuntos:
- Vérti
es-disjuntos:
Trajetos, Caminhos e
Cir
uitos
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Vamos dis
utir aqui alguns tipos espe
iais de subgrafos de um grafo G.
Quando dis
utimos o problema das Pontes de Königsbergh, estávamos
interessados em determinar um roteiro que passasse por todas as pontes
apenas uma vez. Se estudarmos este problema através de grafos, vamos
pre
isar de alguns 
on
eitos para a
har a solução do problema.
De�nição 4. Dado um grafo G(V,A), um passeio em G 
onsiste de
uma sequên
ia �nita alternada de vérti
es e arestas, 
omeçando e
terminando por vérti
es, tal que 
ada aresta é in
idente ao vérti
e que a
pre
ede e ao que a su
ede.
De�nição 5. Dado um grafo G(V,A), um trajeto em G 
onsiste de
uma sequên
ia �nita alternada de vérti
es e arestas, 
omeçando e
terminando por vérti
es, tal que 
ada aresta apare
e apenas uma vez e é
in
idente ao vérti
e que a pre
ede e ao que a su
ede.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
Exer
í
io: Considere o grafo G abaixo
1
2
3
4 5
a b
c d
e f
6
7
8 9 10
11
G:
Determine:
- um trajeto onde há repetição de vérti
es.
- um trajeto onde não há repetição de vérti
es.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
De�nição 6. Dado um grafo G(V,A), um 
aminho em G 
onsiste de
uma sequên
ia �nita alternada de vérti
es e arestas, 
omeçando e
terminando por vérti
es, tal que 
ada aresta é in
idente ao vérti
e que a
pre
ede e ao que a su
ede e não há repetição de vérti
es. Em outras
palavras, um 
aminho é um trajeto onde não repetição de vérti
es.
Exer
í
io: Considere o grafo G do Exemplo 6. Identi�que 
aminhos
entre os vérti
es a e f .
Observação: Em grafos simples podemos men
ionar um 
aminho ou
trajeto listando apenas os vérti
es (ou arestas), sem menção explí
ita às
arestas (ou vérti
es).
Questões:
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
1. Qual é o grau dos vérti
es perten
entes a um 
aminho?
Os vérti
es �nais de um 
aminho possuem grau 1 e os demais,
vérti
es intermediários, possuem grau 2.
2. Qual é o 
omprimento de um 
aminho/trajeto em grafos não
valorados? E em grafos valorados?
Para grafos não valorados o 
omprimento é igual ao número de
arestas in
luídas no 
aminho, e em grafos valorados é igual à soma
dos valores das arestas.
Questões:
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
1. Qual é o grau dos vérti
es perten
entes a um 
aminho?
Os vérti
es �nais de um 
aminho possuem grau 1 e os demais,
vérti
es intermediários, possuem grau 2.
2. Qual é o 
omprimento de um 
aminho/trajeto em grafos não
valorados? E em grafos valorados?
Para grafos não valorados o 
omprimento é igual ao número de
arestas in
luídas no 
aminho, e em grafos valorados é igual à soma
dos valores das arestas.
Questões:
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
1. Qual é o grau dos vérti
es perten
entes a um 
aminho?
Os vérti
es �nais de um 
aminho possuem grau 1 e os demais,
vérti
es intermediários, possuem grau 2.
2. Qual é o 
omprimento de um 
aminho/trajeto em grafos não
valorados? E em grafos valorados?
Para grafos não valorados o 
omprimento é igual ao número de
arestas in
luídas no 
aminho, e em grafos valorados é igual à soma
dos valores das arestas.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
De�nição 7. Um trajeto no qual o vérti
e ini
ial e o �nal são iguais é
hamado de trajeto fe
hado.
De�nição 8. Um trajeto fe
hado no qual nenhum vérti
e (
om ex
eção
do ini
ial e do �nal) apare
e mais de uma vez é 
hamado de Ci
lo
(
ir
uito ou 
aminho fe
hado).
Exemplo 9. A sequên
ia {c, a, d, e, c} é um exemplo de 
i
lo no grafo
do Exemplo 6. Já a sequên
ia {a, b, d, a, e, c, a} é um 
ontra-exemplo.
Observe neste 
ontra-exemplo que o vérti
e ini
ial é . . . . . . e o vérti
e
�nal é . . . . . .. Qual é o 4o vérti
e desta sequên
ia? Esta sequên
ia não é
um 
i
lo pois o 4
o
vérti
e apare
e mais de vez.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
Estes 
on
eitos podem ser resumidos através do seguinte diagrama:
Subgrafo
Trajeto
Caminho Circuito
Exer
í
ios:
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
1. Considere o grafo:
1
2
3
4 5
ab
c
d
e
f
6
g
h
i
j
(a) Liste todos os trajetos existentes entre os vérti
es 5 e 6.
(b) Liste todos os 
aminhos existentes entre os vérti
es 5 e 6.
(
) Quais dos trajetos obtidos no item (a) são 
aminhos?
(d) Dê o 
omprimento de 
ada um dos 
aminhos do item (b).
2. Sejam a, b e c três vérti
es distintos em um grafo. Se existe um
aminho entre a e b e também existe um 
aminho entre b e c,
mostre queexiste um 
aminho entre a e c.
Grafos Conexos
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
Considere os grafos abaixo:
v1
v2
v1
v2
G1 G2
E possível a
har um 
aminho entre os verti
es v1 e v2?
De�nição 10. Um grafo é dito 
onexo se existir pelo menos um
aminho entre 
ada par de vérti
es do grafo. Caso 
ontrário, o grafo é
hamado de des
onexo.
O grafo G1 a
ima é 
onexo, e o grafo G2 é des
onexo.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
Cada um dos subgrafos 
onexos maximais de um grafo des
onexo é
hamado de uma 
omponente do grafo. Ou seja, uma 
omponente é um
subgrafo 
onexo que não esteja estritamente 
ontido em outros
subgrafos 
onexos.
1
Dado um grafo qualquer, 
omo determinar se o grafo é 
onexo?
Teorema 11. Um grafo G(V,A) é des
onexo se e somente se seu
onjunto de vérti
es V puder ser parti
ionado em dois 
onjuntos
disjuntos e não-vazios, V1 e V2, de forma que não exista uma aresta 
om
uma extremidade em V1 e outra extremidade em V2.
1
Sejam S e S′ tais que S′ ⊂ S. S′ é maximal em relação a uma propriedade P
quando S′ satisfaz P e não existe S′′ ⊃ S′ que tambem satisfaça P .
Demonstração
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
[⇒] Suponhamos que G seja des
onexo e mostremos que existe uma
partição de V , V1 e V2, tal que não existe uma aresta 
om uma
extremidade em V1 e outra extremidade em V2.
Seja G um grafo des
onexo. Pre
isamos en
ontrar uma partição de V
que satisfaça a propriedade a
ima.
Considere um vérti
e vi ∈ V qualquer. Forme o 
onjunto V1 
om todos
os vérti
es de V que estejam ligados a vi por um 
aminho.
Como G é des
onexo, V1 não 
ontém todos os vérti
es de G. Assim os
vérti
es restantes formam um 
onjunto não-vazio V2, e não existe
nenhuma aresta de G 
om uma extremidade em V1 e outra em V2.
Portanto V1 e V2 formam a partição desejada.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
[⇐] Suponhamos que exista uma partição de V , V1 e V2, tal que não
existe uma aresta 
om uma extremidade em V1 e outra extremidade em
V2 e mostremos que G é des
onexo.
Considere dois vérti
es quaisquer em V , por exemplo vi e vj, tais que
vi ∈ V1 e vj ∈ V2.
Não pode existir nenhum 
aminho entre vi e vj, pois se existisse, haveria
uma aresta 
om uma extremidade em V1 e outra em V2.
Portanto se uma partição existe então o grafo é des
onexo.
vi
vj
V1 V2
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
Questão: Qual é o número máximo de arestas que um grafo simples
om n vérti
es pode ter?
Cada vérti
e pode ser ligado p�r uma aresta a 
ada um dos outros
vérti
es do grafo, isto é aos outros (n− 1). Isto nos dá (n− 1) arestas.
Com existem n vérti
es, teremos então n(n− 1) arestas. No entanto,
ada aresta interliga dois vérti
es e portanto está sendo 
onsiderada duas
vezes. Assim, para obtermos o número 
orreto de arestas é ne
essário
dividir o valor que temos até o momento por 2. O número máximo de
aresta é então:
n(n− 1)/2.
Teorema 12. Seja G um grafo simples 
om n vérti
es. Se G possui k
omponentes, então o número m de arestas de G satisfaz
n− k ≤ m ≤ (n− k)(n− k + 1)/2.
Demonstração
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Vamos provar m ≥ n− k por indução sobre o número de arestas de G.
É 
laro que o resultado é verdadeiro para um grafo nulo (m = 0).
Suponha que a desigaldade é verdadeira para todo grafo 
om menos do
que m0 arestas, onde m0 é um inteiro positivo.
Vamos supor ainda, sem perda de generalidade, que G possui o menor
número de arestas possível, no sentido de que a retirada de qualquer
aresta de G aumenta o número de 
omponentes em uma unidade.
Neste 
aso, o grafo resultante teria os mesmos n vérti
es, k + 1
omponentes e m0 − 1 aretas.
Segue da hipótese de indução que
m0 − 1 ≥ n− (k + 1)⇔ m0 ≥ n− k.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
Agora mostremos que vale a segunda desigualdade, supondo, sem perda
de generalidade, que 
ada 
omponente de G é um grafo 
ompleto.
Suponhamos que existam dois 
omponentes Ci e Cj 
om ni e nj
vérti
es, respe
tivamente, onde ni ≥ nj > 1.
Se tro
armos Ci e Cj por grafos 
ompletos 
om ni + 1 e nj − 1 vérti
es,
então o número total de vérti
es permane
e o mesmo, e o número de
arestas é alterado para
[(ni+1)ni−ni(ni−1)]/2−[nj(nj−1)−(nj−1)(nj−2)]/2 = ni−nj+1 > 0.
Segue que, para que o número máximo de arestas seja atingido, G deve
onsistir de um grafo 
ompleto 
om n− (k − 1) vérti
es e k − 1 vérti
es
isolados.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 23
Exemplo 13. Para n = 6 e k = 2:
(a) Componente 1: K4, Componente 2: uma aresta;
(b) Componente 1: K3, Componente 2: K3;
(
) Componente 1: K5, Componente 2: 1 vérti
e.
Exer
í
ios:
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 24
1. Desenhe um grafo 
onexo que se torna des
onexo quando qualquer
aresta é removida.
2. Mostre que um grafo 
onexo G se mantém 
onexo após a remoção
de uma aresta aj se e somente se a aresta perten
e a algum 
ir
uito
de G.
3. Mostre que qualquer grafo simples 
om n vérti
es e mais do que
(n− 1)(n− 2)/2 arestas é 
onexo.
Operações 
om grafos
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 26
De�nição 14. A união de dois grafos G1(V1, A1) e G2(V2, A2) é um
grafo G3(V3, A3) onde:
G3 = G1 ∪G2, V3 = V1 ∪ V2 e A3 = A1 ∪ A2.
De�nição 15. A interse
ção de dois grafos G1(V1, A1) e G2(V2, A2) é
um grafo G3(V3, A3) onde:
G3 = G1 ∩G2, V3 = V1 ∩ V2 e A3 = A1 ∩ A2.
Observação 16. Se V3 = ∅, dizemos que a interse
ção entre G1 e
G2, G1 ∩G2, é vazia.
Pelas de�nições dadas é fá
il veri�
ar que as operações de união e
interse
ção de grafos são 
omutativas, isto é:
G1 ∪G2 = G2 ∪G1,
G1 ∩G2 = G2 ∩G1.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 27
Exemplo 17. Determine a união e a interse
ção dos grafos dados
abaixo:
v1
v2 v3
v4 v5
G1:
v1
v2
v3 v5
v6
G2:
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 28
De�nição 18. Um grafo G é dito de
omposto em dois sub-grafos G1 e
G2 se:
G1 ∪G2 = G e G1 ∩G2 = grafo nulo.
Ou seja, 
ada aresta de G perten
e a G1 ou a G2. Alguns vérti
es no
entanto podem perten
er aos dois.
Exemplo 19. O grafo G1 do exemplo anterior é de
omposto nos
subgrafos G1a e G1b abaixo:
G1a:
G1b:
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 29
De�nição 20. Se aj é uma aresta de um dado grafo G, então G− aj é
um sub-grafo de G obtido pela remoção da aresta aj do grafo G.
Sevi é um vérti
e de G, então G− vi é um sub-grafo de G obtido pela
remoção do vérti
e vi do grafo G.
• A remoção de um vérti
e impli
a na remoção das arestas a ele
in
identes.
De maneira similar é possível in
luir vérti
es e arestas em um grafo.
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 30
De�nição 21. A soma de dois grafos G1(V1, A1) e G2(V2, A2) é um
grafo G3(V3, A3) onde:
G3 = G1+G2, V3 = V1∪V2 e A3 = A1∪A2∪{(vi, vj) : vi ∈ V1, vj ∈ V2}.
De�nição 22. A soma direta de dois grafos G1(V1, A1) e G2(V2, A2) é
um grafo G3(V3, A3) onde:
G3 = G1 ⊕G2, V3 = V1 ∪ V2 e A3 = [A1 ∪ A2] \ [A1 ∩ A2]
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 31
Exemplo 23. A seguir estão exempli�
adas algumas das operações
de�nidas.
G:
1
2
3
4
5
6
G - (2,6):
1
2
3
4
5
6
G - 1:
2
3
4
5
6
G + (1,4):
1
2
3
4
5
6
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 32
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 33
De�nição 24. A fusão de um par de vérti
es a e b em um Grafo G é
feita substituindo os dois vérti
es por um úni
o vérti
e ab , de tal forma
que toda aresta que era in
idente no vérti
e a e/ou no vérti
e b passa a
ser in
idente no novo vérti
e ab.
Observação 25. A fusão de vérti
es em um grafo não altera seu
número de arestas, apenas diminui o número de vérti
es.
De�nição 26. A 
ontração de dois vérti
es a e b é feita através da
fusão dos vérti
es a e b e a remoção dos loops e arestas paralelas que
são formadas no pro
esso.
De�nição 27. A 
ontração de uma aresta (a, b) é feita removendo-se a
aresta (a, b) e fazendo a 
ontração dos vérti
es a e b. É denotado por
G \ (a, b).
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 34
Exemplo 28. Na �gura abaixo temos, à esquerda, um grafo G; no
entro, o grafo obtido após a fusão dos vérti
es 1 e 2; e à direita o grafo
obtido após a 
ontração da aresta (1, 2).
G: 1 2
3 4
56
12
3 4
56
12
3 4
56
Subgrafos Trajetos, Caminhos e Cir
uitos Grafos Conexos Operações 
om grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 35
Exer
í
ios: Considere o grafo:
1
2
3
4 5
ab
c
d
e
f
6
g
h
i
j
1. Considere os 
aminhos de�nidos no exer
í
io anterior (tópi
o
Sub-grafos) para este mesmo grafo. Agrupe os 
aminhos obtidos em
onjuntos de 
aminhos arestas disjuntos. Mostre que a união de dois
aminhos aresta-disjuntos entre dois pares de vérti
es forma um
ir
uito ou é a união de 
ir
uitos.
2. Remova o vérti
e 5 deste grafo.
3. A
res
ente a aresta (2, 7).
4. De
omponha este grafo em três sub-grafos.
5. Contraia a aresta (2, 3).
	Subgrafos
	
	
	
	
	Trajetos, Caminhos e Circuitos
	
	
	
	Questões:
	
	
	Exercícios:
	Grafos Conexos
	
	
	Demonstração
	
	
	Demonstração
	
	
	Exercícios:
	Operações com grafos