Flashcard FC303224
Como calcular o número de passeios de comprimento 3 entre dois vértices em um grafo simples usando apenas as listas de adjacência?
Orientação no Plano, no Espaço e no Tempo
FGV · 2024
Como calcular o número de passeios de comprimento 3 entre dois vértices em um grafo simples usando apenas as listas de adjacência?
Mostrar resposta e comentário
Resposta
Somando, para cada vértice adjacente à origem, quantos de seus vizinhos são também vizinhos do destino: \( \displaystyle\sum_{a\in N(s)} |N(a)\cap N(t)|\).Método:
Para cada \(a\in N(s)\) contar \( |N(a)\cap N(t)| \) e somar os resultados.
Exemplo:
Considere vértices \(P,Q,R,S\) com adjacências:
\(N(P)=\{Q,R\}\), \(N(Q)=\{P,R,S\}\), \(N(R)=\{P,Q,S\}\), \(N(S)=\{Q,R\}\).
Queremos passeios de comprimento 3 de \(P\) até \(S\).
Calcule:
\(a=Q:\;N(Q)\cap N(S)=\{P,R,S\}\cap\{Q,R\}=\{R\}\Rightarrow |\,\cdot\,|=1\).
\(a=R:\;N(R)\cap N(S)=\{P,Q,S\}\cap\{Q,R\}=\{Q\}\Rightarrow |\,\cdot\,|=1\).
Logo \(1+1=2\) passeios: \(P\!-\!Q\!-\!R\!-\!S\) e \(P\!-\!R\!-\!Q\!-\!S\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300314
Conteúdo do catálogo FC Concursos · Atualizado em