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 sub-

grafos conexos (componentes conexas)

v1

v2 v3

v1

v2

v3

v4

v5

v6

v7

Conexo Não-Conexo

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

v3

v2

v4

v1

v3+v4

v2

v1 v2+v3+v4 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

v4 v6

v2

v5

v3 v1

v4

v3

v6 v5

v2

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

v1

v4 v6

v2

v5

v3

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}

v1

v2

v3

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

v1

v4 v6

v2

v5

v3

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

v1

v4 v6

v2

v5

v3

v7

Algoritmo: Componentes F-Conexas

• Algoritmo

• P0: Obter a matriz R = [rij], definida como:

• P1: Obter a matriz Q = RT

• P2: Obter o produto R Q, realizado elemento a elemento de

cada matriz

contrário caso 0,

v departir a atingidoser pode v vértice o se 1,r ijij

Algoritmo: Componentes F-Conexas

• Exemplo v3 v1

v2 v4

1100

1100

1111

1111

R

1111

1111

0011

0011

Q

1100

1100

0011

0011

QR

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}

x2* x1*

v3 v1

v2 v4

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

• Ex: {v3, v4}, {v5}

4 3

8 7

1

2

5

6

1

4 3

8 7

2

6

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)}

4 3

8 7

1

2

5

6

4 3

8 7

1

2

5

6

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

2

3

5

6

7 4

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

2

3

5

6

7 4

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

1

2

4

5 3

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)

3 1 2 4

7 5 6 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