Ponte Corte Articulação

Prévia do material em texto

Teoria dos Grafos 
(continuação de árvores)
Teorema: Se G é uma árvore então m=n-1
� Por indução em n!!!! (notas de aula)
Corolário: toda árvore não trivial possui 
pelo menos dois vértices de grau um.
� Prova: Seja T uma árvore não trivial.
� Logo d(v) ≥ 1 ∀ v∈V(T).
� Como Σ d(v)=2|E(G)|=2(|V(G)|-1) ou 
seja Σ d(v)=2|V(G)|- 2. 
� Segue que d(v) =1 para pelo menos 
dois vértices v.
Ponte (Aresta de corte)
� Uma Ponte (ou aresta de corte) de G é
uma aresta e tal que ω(G) < ω(G-e). 
� Ex.:
Teorema: Uma aresta e de G é uma 
ponte de G se e somente se não está
contida em nenhum ciclo de G
Prova: ⇒
� Seja e=(v,w) uma ponte de G. 
� Logo ω(G)<ω(G-e), v e w não têm caminho 
que os ligue em G-e. 
� Suponha, por absurdo, que e está contida em 
um ciclo C de G. 
� Nesse caso o caminho P=C-e está em G-e e 
conecta os vértices v e w em G-e. Absurdo! 
� Logo e não está contida em nenhum ciclo de 
G.
Teorema: Uma aresta e de G é uma 
ponte de G se e somente se não está
contida em nenhum ciclo de G
Prova: ⇐
� Suponha (por absurdo) que a aresta e=(v,w) 
não esteja contida em nenhum ciclo de G, e 
que não seja ponte de G. 
� Logo ω(G) = ω(G-e), e como v e w estão 
num mesmo componente em G (porque 
existe a aresta (v,w)), então v e w também 
estão num mesmo componente em G-e.
� Então existe um caminho P entre v e w em 
G-e. Mas P ∪ e é um ciclo em G. Absurdo! 
Logo e é ponte de G.
Corolário: Um grafo conexo é uma árvore 
se e somente se toda aresta é uma ponte
� Prova: (exercício)
Árvore Geradora
� É um subgrafo gerador T de G que é
uma árvore.
subgrafo gerador: V(T)=V(G)
E(T) ⊆ E(G)
Corolário: Todo grafo conexo 
possui uma árvore geradora
Prova:
Seja T um subgrafo gerador conexo minimal de G. 
(vamos mostrar que T é uma árvore).
T é conexo por construção. (Falta mostrar que é acíclico)
Suponha que T contém um ciclo C. Seja e uma aresta
qualquer de C. Essa aresta e não é ponte de T (por 
teorema).
Logo T-e é gerador (não removemos vértices) e conexo.
Então T não é minimal. Contradição!
Portanto T é acíclico. Logo T é uma árvore.
Corolário: Se G é conexo, 
então m ≥ n-1
� Prova: (exercício)
Teorema: Seja T uma árvore geradora de um 
grafo conexo G e seja e uma aresta de G, 
e ∉T. Então T+e contém um único ciclo.
Prova:
� Como T é acíclico, e T é subgrafo gerador 
minimal conexo de G, a inclusão de qq aresta 
em T cria ciclos. Cada ciclo de T+e contém e. 
� C é um ciclo de T+e sse C-e é um caminho 
em T ligando os extremos de e.
� Por teorema anterior, T tem um único 
caminho desse tipo, logo T+e contém um 
único ciclo.
Articulação (ou vértice de corte)
� Um vértice v de G (onde G não é um 
grafo trivial) é uma articulação de G se 
w(G-v) > w(G).
Teorema: Um vértice v de uma árvore G 
é uma articulação se e somente se 
d(v) > 1
Prova:
� (→) Se v é articulação então existem 2 
vértices x,y tal que todo caminho entre 
x,y contém v.
� Logo, v deve possuir grau > 1.
Teorema: Um vértice v de uma árvore G é uma 
articulação se e somente se d(v) > 1
� (←) d(v) >1, então existem pelo menos 2 vértices 
u,w adjacentes a v.
� Como T é uma árvore, o caminho entre u,w é único e 
nesse caso é uvw.
� Logo, retirando-se v, u e w ficam desconectados. 
� Portanto, v é articulação. 
v
w
u
Corolário: Todo grafo conexo e não trivial 
tem pelo menos 2 vértices que não são 
articulações
� G contém uma árvore geradora T.
� T contém pelo menos dois vértices de grau 1 (e que não 
são articulações)
� Seja v qualquer um desses vértices
� w(T-v)=1
Como T é uma árvore geradora de G, T-v é um subgrafo
gerador de G-v e portanto w(G-v) ≤ w(T-v).
Logo, w(G-v)=1, e v não é uma articulação de G.
Como G tem pelo menos 2 vértices de grau 1, o 
resultado segue.