Conexidade e Distância

IFRN
Conexidade e Distância
Prof. Edmilson Campos
Conteúdo
• Grafo Conexo
• Componente Conexa e Algoritmos
• Grafo F-Conexo
• Componente F-Conexa
• Antecessor, Sucessor, Fecho Transitivo
• Algoritmo
• Grafo Reduzido
• Conceitos
• Vértice e Aresta de Corte
• Base, Anti-Base, Raiz, Anti-Raiz
• Distância
Grafo Conexo
• Um grafo G(V,A) é dito ser conexo, simplesmente conexo
ou S-Conexo, se há pelo menos uma sequência de
arestas ligando cada par de vértices do grafo
• Um grafo não conexo consiste de dois ou mais subgrafos conexos (componentes conexas)
Conexo
Não-Conexo
v1
v2
v3
v1
v3
v5
v6
v2
v4
v7
Algoritmo: Conexidade
• Reduzir cada componente do grafo a um único vértice.
• Processo de redução seqüencial onde todos os vértices
adjacentes a um dado vértice são fundidos com ele
v1
v2
v1
v3
v4
v3+v4
v1
v2+v3+v4
v2
v1+v2+v3+v4
Algoritmo: Conexidade
• Algoritmo (Goodman)
• P0:[inicialização]
•
H = G; c = 0;
• P1:[Gere a próxima componente conexa]
•
Enquanto (H  )
•
Selecione um vértice v pertencente a H
•
Enquanto (v for adjacente a algum vértice u  H)
•
H = grafo resultante da fusão de u com v;
•
Remova v, isto é, faça H = H - v;
•
c = c + 1;
• P2:[Teste de conexidade]
•
Se (c>1) G é não conexo
•
senão G é conexo
Grafo F-Conexo
• Em dígrafos, o grafo G(V,A) é dito ser fortemente conexo
ou F_Conexo, se todo par de vértices participa de um
circuito (caminho fechado entre os vértices)
• Isto significa que cada vértice pode ser alcançável
partindo-se de qualquer outro vértice de grafo.
v1
v2
v4
v5
v3
v6
v1
v4
v2
v5
v3
v6
Componente Fortemente Conexa
• Um grafo G(V,A) que não é fortemente conexo é formado
por pelo menos dois sub-grafos fortemente conexo
• Cada um desses grafos é dito ser uma componente
fortemente conexa de G
v2
v1
v4
v3
v5
v6
v7
Antecessor e Sucessor
• Antecessor de um vértice
• É todo vj que seja extremidade inicial de uma aresta que termina
em vi
• Ex: Antecessores de v3 = {v1, v2, v4}
• Sucessor de um vértice
• É todo vj que seja extremidade final de uma aresta que inicia em vi
• Ex: Sucessores de v1 = {v2, v3, v4}
v2
v3
v1
v4
Fecho Transitivo Direto
• Fecho Transitivo Direto (FTD)
• O FTD de um vértice v é o conjunto de todos os vértices que
podem ser atingidos por algum caminho iniciando em v
• Ex: FTD(v5) = {v1, v2, v3, v4, v5, v6}
• Note que o próprio vértice faz parte do FTD já que ele é alcançável
partindo-se dele mesmo
v2
v1
v4
v3
v5
v6
v7
Fecho Transitivo Inverso
• Fecho Transitivo Inverso (FTI)
• O FTI de um vértice v é o conjunto de todos os vértices a partir dos
quais se pode atingir v por algum caminho
• Ex: FTI(v5) = {v1, v2, v4, v5, v7}
• Note que o próprio vértice faz parte do FTI já que dele se pode alcançar
ele mesmo
v2
v1
v4
v3
v5
v6
v7
Algoritmo: Componentes F-Conexas
• Algoritmo
• P0: Obter a matriz R = [rij], definida como:
1, se o vértice v j pode ser atingido a partir de vi
rij  
0, caso contrário

• P1: Obter a matriz Q = RT
• P2: Obter o produto R  Q, realizado elemento a elemento de
cada matriz
Algoritmo: Componentes F-Conexas
• Exemplo
1
1
R
0

0
1 1 1
1 1 1
0 1 1

0 1 1
1
1
Q
1

1
v1
v3
v2
v4
1 0 0
1 0 0
1 1 1

1 1 1
1
1
R Q  
0

0
1 0 0
1 0 0
0 1 1

0 1 1
Grafo Reduzido
• Grafo Reduzido G*=(V*, A*)
• Grafo onde cada vértice corresponde a uma componente
fortemente conexa do grafo original
• x1* = {v1, v2}
• x2* = {v3, v4}
v1
v3
x1*
v2
v4
x2*
Vértice de Corte
• Um vértice é dito ser um vértice de corte se sua remoção
(juntamente com as arestas a ele conectadas) provoca
uma redução na conexidade do grafo
• A conectividade do grafo é 1, pois removendo v5
desconectamos o grafo
1
• Ex: {v3, v4}, {v5}
1
4
3
2
4
3
2
5
6
7
6
8
7
8
Aresta de Corte
• Uma aresta é dita ser uma aresta de corte se sua
remoção provoca uma redução na conexidade do grafo
• A conectividade de arestas do grafo é 2, pois removendo
(v3,v5) e (v4,v5) desconectamos o grafo
• Ex: {(v1,v3),(v2,v3),(v4,v5)}
• Ex: {(v3,v5),(v4,v5)}
1
1
4
3
2
4
3
2
5
5
6
7
6
8
7
8
Base
• Uma base de um grafo G(V,A) é um subconjunto B  V,
tal que:
• Dois vértices quaisquer de B não são ligados por nenhum caminho
• Todo vértice não pertencente a B pode ser atingido por um
caminho partindo de B
1
3
2
4
6
5
7
8
B
A
Anti-Base
• Uma anti-base de um grafo G(V,A) é um subconjunto A 
V, tal que:
• Dois vértices quaisquer de A não são ligados por nenhum caminho
• Todo vértice não pertencente a A pode atingir A por um caminho
1
3
2
4
6
5
7
8
B
A
Raiz e Anti-Raiz
• Raiz
• Se a base de um grafo G(V,A) é um conjunto unitário
• Anti-Raiz
• Se a anti-base de um grafo G(V,A) é um conjunto unitário
2
1
3
5
4
B
A
Distância
• Distância d(v,w)
• É o comprimento do menor caminho entre dois vértices v e w
pertencentes ao grafo G(V,A)
• Se não houver caminho, a distância é infinita
• Propriedades
• d(u,v) 0, com d(u,v)=0, se e somente se, u = v
• d(u,v) = d(v,u) para grafos não orientados
• d(u,v) + d(v,w)  d(u,w)
Exercício
• Obter as distâncias
• d(1,8), d(1,4), d(1,3)
1
2
3
4
5
6
7
8
Referências
• Introdução à Teoria dos Grafos
• Márcia Aguiar Rabuske – Editora da UFSC
• Estrutura de Dados e Algoritmos em Java
• Goodrich e Tamassia – Bookman
• Materiais Didáticos
• Prof. André L. Maitelli – UFRN
• Prof. Robinson L. S. Alves – IFRN
• Prof. Gilbert Azevedo - IFRN