1. Dado o dígrafo G=(V, E) sendo V=M, N, O, P, Q, R, S e
E= & (M, S),(N, O),(P, R),(N, S),(O, M),(N, Q),(O, M), & (P, P),(S, M),(O, N),(S, M),(N, R),(P, M),(M, S)
(a) Especifique, caso exista, um caminho simples desde o vértice M até o vértice S.
(b) Especifique, caso exista, um ciclo simples, envolvendo pelo menos 4 nós.
© O dígrafo é conexo ou não conexo?
(d) Qual o grau dos vértices N e R.
(e) Represente o dígrafo utilizando representação por lista de adjacência.
(f) Represente o dígrafo utilizando representação por matriz de adjacência.

Passo 1

O enunciado nos dá um dígrafo G com vértices V = {M, N, O, P, Q, R, S} e arestas direcionadas E = {(M,S),(N,O),(P,R),(N,S),(O,M),(N,Q),(O,M),(P,P),(S,M),(O,N),(S,M),(N,R),(P,M),(M,S)}. O conteúdo envolve: definição de caminho simples, ciclo simples em dígrafos, noções de conectividade (forte e fraca), grau de entrada/saída de vértices e representações por lista e matriz de adjacência.

Passo 2

Para (a) basta escolher um caminho simples de M até S. Observando que existe diretamente a aresta (M,S), um caminho simples é
M to S

Passo 3

Para (b) procuramos um ciclo simples contendo pelo menos 4 nós. Ao listar todas as possíveis cadeias fechadas sem repetir vértices, os únicos ciclos que aparecem são M→S→M (2 nós), N→O→N (2 nós) e o laço P→P (1 nó). Não há nenhum ciclo com 4 ou mais vértices, logo não existe.

Passo 4

Para © verificamos conectividade. Como dígrafo, G não é fortemente conexo (por exemplo, não há caminho dirigido de S até Q), mas, se ignorarmos as direções (conectividade fraca), o grafo subjacente é conectado. Portanto, G não é fortemente conexo mas é fracamente conexo.

Passo 5

Para (d) calculamos grau de entrada (d⁻) e de saída (d⁺):
  • Para N: saem arestas N→O, N→S, N→Q, N→R, então d⁺(N)=4; entra apenas O→N, logo d⁻(N)=1.
  • Para R: não sai nenhuma aresta de R, então d⁺®=0; entram N→R e P→R, logo d⁻®=2.

Passo 6

Para (e) a lista de adjacência (considerando arestas únicas) fica:
M: {S}
N: {O, S, Q, R}
O: {M, N}
P: {P, M, R}
Q: {}
R: {}
S: {M}

Passo 7

Para (f) tomando a ordem de vértices (M, N, O, P, Q, R, S), a matriz de adjacência A (com 1 se há aresta i→j, 0 caso contrário) é
A = 0 &0 &0 &0 &0 &0 &1 0 &0 &1 &0 &1 &1 &1 1 &1 &0 &0 &0 &0 &0 1 &0 &0 &1 &0 &1 &0 0 &0 &0 &0 &0 &0 &0 0 &0 &0 &0 &0 &0 &0 1 &0 &0 &0 &0 &0 &0

Resposta

(a) Um caminho simples é M→S.
(b) Não existe ciclo simples com pelo menos 4 nós.
© G não é fortemente conexo, mas é fracamente conexo.
(d) Para N: d⁺(N)=4, d⁻(N)=1; para R: d⁺®=0, d⁻®=2.
(e) Lista de adjacência:
M: {S}
N: {O, S, Q, R}
O: {M, N}
P: {P, M, R}
Q: {}
R: {}
S: {M}
(f) Matriz de adjacência (ordem M,N,O,P,Q,R,S):
0&0&0&0&0&0&1 0&0&1&0&1&1&1 1&1&0&0&0&0&0 1&0&0&1&0&1&0 0&0&0&0&0&0&0 0&0&0&0&0&0&0 1&0&0&0&0&0&0

Exercícios relacionados