Nos exercícios de 8 a 10, determine um subgrafo maximal bidirecional completo, se houver um, para o digráfico com a matriz de adjacência dada.

Passo 1

Fala pessoal, tudo certinho? vamos responder mais uma questão, então prepara o material e vamos responder!!

A matriz de adjacência A ( G ) é dada por

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

Supondo que S = s i j 5 × 5 seja a matriz que s i j = 1 se e somente se ( i , j ) e ( j , i ) como entradas da matriz de adjacência sejam iguais a 1. Caso contrário, s i j = 0 , portanto

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

Portanto, temos que

S 3 = 0 0 0 2 0 0 0 1 1 0 0 1 0 1 0 0 2 1 0 1 2 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0

Com isso, nós temos que

S 3 = 0 0 0 2 0 0 0 3 3 0 0 3 0 3 0 0 0 3 0 3 2 0 0 0 0

Passo 2

Desde que s 22 3 = s 33 3 = s 44 3 = 2 > 0 , portanto, pelo teorema apresentado no capítulo, P 2 , P 3 , P 4 pertencem a um conjunto e P 1 , P 5 não pertencem a nenhum conjunto. Para a matriz de adjacência, descobrimos que existe uma aresta direcionada de P i para P j para i , j = 2,3 , 4 ; i ≠ j . Portanto, { P 2 , P 3 , P 4 } é um conjunto. Este é o único conjunto { P 2 , P 3 , P 4 } no grafo representado na matriz de adjacência acima.

Resposta

{ P 2 , P 3 , P 4 }