Teoria dos grafos: algorítmo de Malgrange

Pessoal, vou mostrar como identificar as componentes conexas de um grafo (f-conexas) usando o algorítimo de Malgrange.

O grafo:

Repare que no grafo que utilizaremos temos os pontos de A à H e os “vértices” possuem direção (indicada pelas setas nas pontas). Alguns vértices possuem mais de uma direção. Repare no que liga os pontos H e F, por exemplo. Deve-se prestar muita atenção nisso ou, no final, o exercício pode ficar errado! Vamos em frente.

Passo 1: A tabela

O próximo passo é montar uma tabela para visualizar melhor as ligações entre os pontos:

 

A B C D E F G H
A 1
1
B 1
C 1 1 1
D 1
E 1 1 1
F 1 1
G 1
H 1 1

Entenda como preencher (pelo grafo):

Primeiro faremos considerando quem MANDA pela COLUNA 1 e marcaremos na tabela quem RECEBE pelas demais colunas.

A manda para B e G.
B manda para H.
C para B, D e H.

Siga a mesma lógica para terminar.

Bom, com a tabela devidamente preenchida, vamos construir a matriz de adjacência:

Passo 2: R+

Agora vamos construir a 1ª fase. Um grafo pode possuir mais de uma. Vamos fazer o R+, o R- e depois o R+∩R-.

O R+(A) trabalhará com a tabela da mesma forma que utilizamos para preencher a mesma, ou seja, você olha o elemento em questão na 1ª coluna e verifica a relação com os outros elementos nas demais colunas (onde tiver o número 1).

Vale lembrar de começar sempre com o primeiro elemento, no nosso caso o A.

R+(A) = {A}

Sempre começamos com o elemento de dentro dos parênteses (que é o primeiro da nossa tabela) dentro das chaves também.

Agora a análise é a seguinte: Com quem o A tem conexão? Olhe a tabela e verá o número 1 marcado nas colunas B e G. Logo temos:

R+(A) = {A,B,G}

Já terminamos a análise do A. O próximo é o B e a pergunta é a mesma: Com quem o B tem conexão? Com o H:

R+(A) = {A,B,G,H}

E o G? Com o F. (Sempre na ordem dos elementos para não se perder!)

R+(A) = {A,B,G,H,F}

E o H? Com o B e F. Repare que o B e F já estão na matriz, logo, não é necessário e nem permitido adicioná-los novamente.

R+(A) = {A,B,G,H,F}

O mesmo ocorre com o último elemento a ser analisado: F? Com A e H.

R+(A) = {A,B,G,H,F}

Passo 3: R-

Agora, o que muda, é a forma de olhar a tabela. Vamos utilizar os elementos da 1ª linha e procurar por seus correspondentes (onde temos 1) nas demais linhas.
Obs.: Como já detalhei bem a R+, serei mais direto na construção da R-.
Obs. 2: Assim como a R+, a R- é função do primeiro elemento e é iniciada por ele.

R-(A) = {A}

O A (“colunamente”) tem ligação com quais elementos? F.
E o F? Com E, G e H.
etc…

Terminando o preenchimento, teremos:

R-(A) = {A,F,E,G,H,D,B,C}

Passo 4: R+∩R-

Vamos agora encontrar a intersecção (∩), ou seja, tudo que tem no R+(A) e também no R-(A):

R+(A)∩R-(A) = {A,B,G,H,F}

A forma de apresentar na prova, essa primeira parte seria:

1ª Fase
R+(A) = {A,B,G,H,F}
R-(A) = {A,F,E,G,H,D,B,C}
R+(A)∩R-(A) = {A,B,G,H,F}

Passo 4: Próxima fase

Bom, terminamos uma fase.”Mas como eu sei se teremos outra fase?”, você deve estar se perguntando agora. É simples!

Quais elementos temos? -> A,B,C,D,E,F,G e H.
Quais elementos estão na ∩ da 1ª fase? -> A,B,F,G e H.
Estão todos os elementos na ∩? -> Não!
Quais faltam? -> C,D e E.

Então teremos que fazer mais uma fase. (Ou mais 2, 3…N, até que os todos elementos sejam utilizados nas intersecções).

O nosso primeiro elemento, agora será o primeiro dos que sobraram, logo, será o argumento das funções R.

Novamente, como já detalhei a 1ª fase, esta segue a mesma lógica da anterior. Salvo o detalhes dos parênteses com os elementos na primeira linha. Veja:

2ª Fase (C,D,E)
R+(C) = {C,D,E}
R-(C) = {C,D,E}
R+(C)∩R-(C) = {C,D,E}

Mas as 3 linhas ficaram iguais, é sempre assim!? Não! Foi pura coincidência. Preguiça tira nota! Cuidado!

Muito Importante: O C, por exemplo, tem ligação com B e H, que não aparecem na matriz. Porquê?! Porque eles fazem parte da intersecção anterior: R+(A)∩R-(A) = {A,B,G,H,F}.

A partir da 2ª  se um elemento está dentro da chave (como na 1ª fase) ou está em qualquer resultado de intersecções (de n fases anteriores) ele não deve ser adicionado.

Então, já que nessa última intersecção entram todos os elementos que faltavam para que todos fossem utilizados em intersecções, não teremos mais fases e podemos dar a resposta da seguinte forma:

As componentes f-conexas são: {{A,B,G,H,F},{C,D,E}}.

Bom, espero que tenham gostado da explicação e que este artigo possa ser últil para alguém.

Gostaria de receber comentários, também, pois deu um trabalhão isso aqui e seria legal eu saber se foi útil pra alguém.

Estou aberto a qualquer sugestão. Bons estudos a todos!

Imperdivel!