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.

A = 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0

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:

S = s i j ,   c o m   s i j = s j i = 1   s e   a i j = a j i = 1 ,   o n d e   A   é   a   m a t r i z   d e   a d j a c ê n c i a

q u e   o   e n u n c i a d o   n o s   f o r n e c e u .   V e r i f i c a n d o   A   v i s u a l m e n t e   t e r e m o s :

S = 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0

Os únicos elementos que seguem a condição desejada são:

a 12 = a 21 ;   a 2 5 = a 52 ;   a 45 = a 54

Logo, só esses elementos serão iguais a 1 na matriz S.

Passo 2

Devemos agora, calcular a matriz S3:

S 3 = S 2 ∙ S

Calculando S2:

S 2 = 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 ∙ 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 =

= 0 + 1 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 1 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 1 + 0 + 0 + 0 + 1 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 1 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 1 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 1 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 1 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 0 + 0 + 0 + 0 0 + 1 + 0 + 1 + 0 =

= 1 0 0 0 1 0 2 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 2

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