Flashcard FC303225
Como contar o número de percursos de exatamente k arestas entre dois vértices em um grafo, quando há arestas múltiplas e a ordem das arestas importa?
Orientação no Plano, no Espaço e no Tempo
FGV · 2024
Como contar o número de percursos de exatamente k arestas entre dois vértices em um grafo, quando há arestas múltiplas e a ordem das arestas importa?
Mostrar resposta e comentário
Resposta
Contando todas as sequências de arestas de comprimento k que ligam os vértices, multiplicando as opções em cada etapa e somando os casos mutuamente exclusivos.Explicação:
Identifique as escolhas possíveis em cada uma das k etapas do percurso, contando arestas paralelas como opções distintas. Para cada caminho parcial que leva ao passo i, multiplique o número de opções subsequentes; some os totais dos casos disjuntos (diferentes primeiras escolhas).
Exemplo:
Considere vértices P,Q,R,S com arestas (não orientadas):
- P–Q: 2 arestas paralelas
- Q–S: 1 aresta
- S–R: 1 aresta
- P–R: 1 aresta
Queremos percursos de exatamente 3 arestas de P até R.
Casos:
1) P → Q → S → R: opções = 2 (P–Q) × 1 (Q–S) × 1 (S–R) = \(2\).
2) P → R → S → R: opções = 1 (P–R) × 1 (R–S) × 1 (S–R) = \(1\).
Total = \(2 + 1 = 3\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300315
Conteúdo do catálogo FC Concursos · Atualizado em