Nos Exercícios de 8 ao 10, determine um subgrafo maximal bidirecional completo, se houver um, para o digráfico coma matriz de adjacência dada.
Passo 1
E aí pessoal, belezinha. Vamos agora trabalhar em algumas questões da teoria de grafos.
Seguindo o que fora desenvolvido no exemplo 12 desta seção, temos que escrever a matriz S, seguindo:
Os únicos elementos que seguem a condição desejada são:
Logo, só esses elementos serão iguais a 1 na matriz S.
Passo 2
Devemos agora, calcular a matriz S3:
Calculando S2:
Passo 3
Sabemos que Pi pertence a um subgrafo maximal bidirecional completo quando o elemento da diagonal principal de S3 for positivo, ou seja, como temos a11 = a44 = 1 > 0 e a22 = a55 = 2 > 0, temos que o subconjunto {P1, P2, P4, P5} é o subgrafo maximal direcional completo da matriz de adjacência que nos foi fornecida.
Resposta
{P1, P2, P4, P5}.