697364_Unidade 4 - Conectividade

Prévia do material em texto

1
Unidade VI
Conectividade (1)
Pontifícia Universidade Católica de Minas Gerais
Prof. Pasteur Jr. e Prof. Max do Val 
Machado
1 Conjunto de transparências baseado no material da Profa. Raquel Mini
2
Cut-set
• Cut-set de um grafo conexo G: é um 
conjunto de arestas de G cuja remoção 
desconecta G. Um cut-set não pode ter
subconjuntos que sejam cut-set.
• Um cut-set particiona os vértices do grafo 
em 2 subconjuntos disjuntos
3
• Exemplo: Dada uma rede de comunicação, 
telecomunicações ou transportes, como 
medir a robustez da rede?
• Olhamos todos os cut-sets do grafo e 
aquele com menor número de arestas é o 
mais vulnerável
{a,b,g}
{a,b,e,f}
{d,h,f}
{k}
a
g
b c
e d
f
k
h
Cut-set
4
Conectividade e 
Separabilidade
• Conectividade de aresta λ(G): 
corresponde ao menor número de arestas 
do grafo cuja remoção o desconecta. É o 
número de aresta do menor cut-set
• Conectividade de vértice K(G) (ou 
simplesmente conectividade): corresponde 
ao menor número de vértices do grafo cuja 
remoção o desconecta
• Grafo K-conexo: grafo de conectividade de 
vértice igual a K.
• Grafo separável: grafo com conectividade 
de vértice igual a 1.
5
Conectividade e 
Separabilidade
λ(G)=2 K(G) =2
λ(G)=2 K(G) = 1 (separável)
6
Conectividade e 
Separabilidade
• O vértice que desconecta o grafo separável 
é chamado de ponto de articulação ou cut-
vértice.
• TEOREMA 1: A conectividade de aresta de 
um grafo G não pode exceder ao grau do 
vértice de menor grau.
• TEOREMA 2: A conectividade de vértice 
não pode exceder a conectividade de 
aresta de G.
• Seja δ(G) o menor grau de vértice em G. 
Para todo grafo conexo G tem-se:
K(G) ≤ λ(G) ≤ δ(G)
7
Conectividade e 
Separabilidade
• TEOREMA 3: A máxima conectividade 
de vértice de um grafo G com n
vértices e e arestas (e ≥ n-1) é
• Portanto,
K(G) ≤ λ(G) ≤ 



n
e2




n
e2
8
Conectividade e 
Separabilidade
• Aplicação: Oito computadores serão 
conectados por linhas remotas privadas, 16 
linhas são disponíveis. Como organizar a 
rede de computadores de maneira que ela 
fique o mais invulnerável (robusta) possível 
a falha nas máquinas individuais ou nas 
linhas de comunicação?
Modelagem: Como construir um grafo G
com 8 vértices e 16 arestas de forma a 
maximizar λ(G) e K(G) ?