Conectividade e Blocos em Grafos

Prévia do material em texto

Teoria dos Grafos
CONECTIVIDADE
Corte de vértices
� Seja G=(V,E) um grafo conexo.
� Um subconjunto V´de V é um corte de vértices de 
G se G-V´é desconexo.
� Um grafo completo não possui corte de vértices.
� Para um grafo G qualquer:
Um subconjunto V´de V é um corte de vértices de 
G se 
w(G) < w(G-V´)
Conectividade de vértices: cV(G)
� Se G tem algum par de vértices não adjacentes
definimos cV(G) como o tamanho do menor corte de 
vértices de G.
� Se G é completo (G=Kn), definimos cV(G)=n-1.
� Se G é trivial ou desconexo, definimos cV(G)=0
� G é dito k-conexo (em vértices) se cV(G)≥ k
� Qualquer grafo (não trivial) conexo é 1-conexo
Conectividade por arestas:cE(G)
� Tamanho do menor corte de arestas de um 
grafo.
� Se G é trivial ou desconexo, CE(G).
� G é k-conexo por arestas se CE(G)≥ k.
Teorema: κ ≤ κ’ ≤ δ
Prova:
� Se G é trivial, cV(G)=CE(G)= δ.
� Caso contrário, o conjunto de arestas
incidentes ao vértice de grau δ constitui um 
corte de δ arestas de G.
Teorema: cV(G) ≤ cE(G) ≤ δδδδ
Prova: (aula)
Exemplo:
Exemplo:
δ=4
Exemplo:
δ=4
cE(G)=3
Exemplo:
δ=4
cE(G)=3
Exemplo:
δ=4
cE(G)=3
cV(G)=2
Exemplo:
δ=4
cE(G)=3
cV(G)=2
Blocos
� Um grafo conexo sem sem articulações
é dito um bloco. 
Blocos
� Um grafo conexo sem articulações é
dito um bloco. 
� Todo bloco com pelo menos 3 vértices
é 2-conexo.
Blocos
� Um grafo conexo sem articulações é
dito um bloco. 
� Todo bloco com pelo menos 3 vértices
é 2-conexo.
� Um bloco de um grafo é um subgrafo
que é um bloco e que é maximal em
relação a esta propriedade. 
Blocos
� Um grafo conexo sem articulações é dito um 
bloco. 
� Todo bloco com pelo menos 3 vértices é 2-
conexo.
� Um bloco de um grafo é um subgrafo que é
um bloco e que é maximal em relação a esta
propriedade.
� Todo grafo é a união de seus blocos.