Aula11_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 11
Conjuntos de Corte e Cone
tividade
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Conjuntos de Corte
Conjuntos de Corte Cone
tividade
De�nição e Exemplos
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
Ao estudarmos árvores geradoras, estávamos interessados em um tipo
espe
ial de subgrafo de um grafo 
onexo: um subgrafo que mantivesse
todos os vérti
es do grafo interligados. Neste tópi
o, estamos
interessados em um outro tipo de situação: subgrafos 
uja remoção do
grafo separa alguns vérti
es de outros.
De�nição 1. Em grafo 
onexo G, um 
orte de arestas (ou
simplesmente 
onjunto de 
orte) é um 
onjunto de arestas 
uja
remoção torna o grafo G des
onexo, desde que nenhum sub
onjunto
próprio destas arestas tenha a mesma propriedade
De�nição e Exemplos
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
Exemplo:
Apli
ação 1: Suponha que os vérti
es representam 6 
idades interligadas
por 
abos de �bra óti
a. Desejamos saber quais são os pontos fra
os
desta rede, isto é, pontos que ne
essitam de 
abos adi
ionais. Estamos
pro
urando, entre todos os 
ortes de arestas deste grafo, aquele 
om o
menor número de arestas. Neste 
aso, a 
idade v3 ne
essita de mais
abos.
Exemplo:Como são os 
orte de arestas de uma árvore?
Propriedades
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
Questão: Considere uma árvore geradora T em um grafo 
onexo G e um
orte de arestas S qualquer deste grafo. Existe alguma aresta em 
omum
entre T e S? Sim, pois 
aso 
ontrário a remoção das arestas em S do
grafo G não resultaria em um grafo des
onexo.
Teorema 2. Todo 
orte de arestas de um grafo 
onexo G 
ontém pelo
menos uma aresta em 
omum 
om qualquer árvore geradora de G.
Exemplo: Veri�
ar o teorema para a seguinte árvore geradora T:
Propriedades
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Para identi�
ar os pontos fra
os de uma rede é ne
essário en
ontrar
todos os 
ortes de aresta de G. Como fazer isso?
De�nição 3. Seja um grafo G e T uma árvore geradora de G. Um
onjunto de 
orte fundamental relativo à arvore T, é um 
onjunto
de 
orte de G que 
ontém apenas uma aresta em 
omum 
om a árvore
geradora T.
Propriedades
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
Exemplo : Seja G:
Seja T:
Propriedades
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Vamos 
onsiderar a aresta e. A remoção da aresta e de T parti
iona o
onjunto de vérti
es de T em:
Ou seja, {e} é um 
orte de arestas de T.
Como determinar um 
orte de arestas fundamental de G relativo a T que
ontenha a aresta e? Basta en
ontrarmos o 
onjunto de arestas
ontendo o ramo {e} e que provoque a mesma partição no 
onjunto de
vérti
es de G: {d, e, f}
Propriedades
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
Perguntas:
1. Quantos 
orte de arestas fundamentais existem? n−1, ou seja 5.
Quais são eles? {a, b}, {d, e, f}, {a, c, d}, {f, g, h}, {f, h, k}
2. Qual é a relação entre 
ortes de aresta fundamentais e 
ir
uitos
fundamentais?
Podem ser obtidos a partir de uma árvore geradora de G.
Todo elo de uma árvore geradora de�ne um 
ir
uito fundamental.
Todo ramo de uma árvore geradora de�ne um 
orte de aresta
fundamental.
3. Como obter todos os 
ortes de arestas de um grafo G?
Propriedades
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
De�nição 4. A soma direta de dois 
ortes de arestas em um grafo
é igual a um ter
eiro 
orte de arestas ou a união aresta-disjunta de dois
ortes de arestas.
Exemplo: Seja o grafo G e árvore T do exemplo anterior.
{d, e, f} ⊕ {f, g, h} = {d, e, g, h} é um 
orte de arestas mas não é
fundamental
{a, b} ⊕ {b, c, e, f} = {a, c, e, f} é um 
orte de arestas mas não é
fundamental
{d, e, h, k} ⊕ {f, g, h} = {d, e, f, g, k} não é um 
orte de arestas mas é
união aresta-disjunta de dois 
ortes de aresta {d, e, f} ∪ {g, k}.
Assim, é possível gerar todos os 
ortes de arestas de um grafo G a partir
dos 
ortes de arestas fundamentais relativos a uma dada árvore geradora
de G.
Exer
í
io
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
Considere o Grafo:
a) Determine uma árvore geradora deste grafo e liste todos os sete 
ortes
de arestas fundamentais relativos a esta árvore.
b) Usando a operação de soma direta, determine todos os outros 
ortes
de arestas deste grafo
Cone
tividade
Conjuntos de Corte Cone
tividade
De�nições e exemplos
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
No estudo de 
one
tividade, entre outros aspe
tos, estamos interessados
em estudar a vulnerabilidade de um grafo.
Podemos observar que 
ada 
orte de arestas tem um determinado
número de arestas. Estamos interessados no 
orte de arestas que possui
o menor número de elementos.
De�nição 5. O número de arestas no menor 
orte de arestas de um
grafo G é 
hamado de Cone
tividade de Aresta (CA) .
De�nições e exemplos
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
Exemplo:
1. Qual é a 
one
tividade de arestas de uma árvore?
2. Qual é a 
one
tividade de arestas do grafo de exer
í
io anterior?
3. Qual é a 
one
tividade de arestas dos grafos dos dois exemplos
anteriores?
4. Qual é a 
one
tividade de arestas do grafo a seguir?
De�nições e exemplos
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
Exemplo:
Observamos que não é possível obter um subgrafo des
onexo removendo
apenas 1 aresta de G. No entanto, é possível obter um subgrafo
des
onexo, através da remoção de um vérti
e. Assim, podemos de�nir a
one
tividade de vérti
es do grafo.
De�nições e exemplos
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
De�nição 6. Em um grafo 
onexo G, um 
orte de vérti
es é um
onjunto de vérti
es 
uja remoção torna o grafo G des
onexo, desde que
nenhum sub
onjunto próprio tenha a mesma propriedade. O número de
vérti
es no menor 
orte de vérti
es é 
hamado de Cone
tividade de
Vérti
es (CV )
Exemplo: A 
one
tividade de vérti
es de 
ada um dos grafos do exemplo
anterior é: a) árvore CV=1 b) CV=4 
) CV=1 e CV=2 d) CV=1
De�nições e exemplos
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
De�nição 7. Um grafo 
onexo é separável se a 
one
tividade de
vérti
es é igual a 1.
Exemplo: O grafo item d do Exemplo anterior é separável.
Apli
ação: Suponha que existam n estações para serem ligadas através
de m linhas (linhas de telefone, túneis, estradas, et
) tal que
m ≥ (n− 1). Qual é a melhor maneira de se fazer a 
onexão?
Pre
isamos de um grafo 
om n vérti
es, m arestas e 
om o maior valor
possível para CA e CV . O grafo do exemplo d tem 8 vérti
es e 16
arestas e CV=1 e CA=3. Ao passo que o grafo do exer
í
io anterior tem
CA=CV=4. Ou seja, este último grafo, representa uma forma melhor de
se obter a 
onexão.
É ne
essário destruir 4 estações ou 4 linhas para quebrar a 
omuni
ação
entre as estações. Qual é o maior valor possível para CV eCA?
Propriedades
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
Teorema 8. A 
one
tividade de arestas de um grafo é menor ou igual
ao grau do vérti
e de grau mínimo do grafo.
Prova: Seja vmin o vérti
e de grau mínimo do grafo. Seja δ o grau deste
vérti
e. Para separar este vérti
e dos demais vérti
es do grafo é
ne
essário remover as δ arestas in
identes em vi . Portanto, CA ≤ δ.
Teorema 9. A 
one
tividade de vérti
es em um grafo G é menor ou
igual à 
one
tividade de arestas.
Propriedades
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
Usando os Teoremas 3 e 4 temos podemos estabele
er a seguinte
relação: CV ≤ CA ≤ δ
Mais ainda, é possível mostrar que CV ≤ CA ≤ 2m/n.
Exer
í
io
Determine a 
one
tividade vérti
es e de arestas do grafo abaixo. Observe
que a desigualdade a
ima é satisfeita estritamente.
Para obter um grafo 
om o maior valor possível para CV , ini
ialmente
onstrua um grafo regular de grau ⌊2m/n⌋, em seguida a
res
ente as
arestas restantes.
De�nição
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
De�nição 10. Um grafo G é k-
onexo em arestas (ou vérti
es)
quando sua 
one
tividade de arestas (ou vérti
es) é ≥ k .
Exer
í
ios: veri�
ar a 
one
tividade de arestas e vérti
es dos grafos a
seguir
Propriedades
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Teorema 11. Um grafo G é k-
onexo se e somente se existem pelo
menos k 
aminhos disjuntos (ex
eto nos extremos) entre 
ada par de
vérti
es de G.
Exemplo: No grafo de exemplo anterior (item d) temos:
{u,(u,v),v,(v,x),x} e {u,(u,w),w,(w,x),x} entre os vérti
es u e x.
Apli
ação: Considere que mensageiros devem ser enviados entre duas
idades a e b . Como algumas estradas podem estar bloqueadas,
queremos que 
ada mensageiro use estradas diferentes. Quantos
mensageiros podem ser enviados?
Considere um grafo onde os vérti
es são as 
idades e as arestas
representam estradas. O número de mensageiros que podem ser enviados
é igual ao número de 
aminhos aresta-disjuntos entre os vérti
es a e b .
Este número pode ser determinado usando os resultados a
ima.
Exer
í
io
Conjuntos de Corte Cone
tividade
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
Seja o grafo:
1. En
ontre 3 
aminhos aresta-disjuntos entre s e t .
2. En
ontre um 
orte de arestas 
ontendo 3 arestas que separe s e t .
3. Qual é o maior número possível de 
aminhos disjuntos entre s e t ?
	Conjuntos de Corte
	Definição e Exemplos
	Definição e Exemplos
	Propriedades 
	Propriedades
	Propriedades
	Propriedades
	Propriedades
	Propriedades
	Exercício
	Conectividade
	Definições e exemplos
	Definições e exemplos
	Definições e exemplos
	Definições e exemplos
	Propriedades
	Propriedades
	Definição
	Propriedades
	Exercício