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!