MO417 - Questão para a prova oral
Número: 115
Enunciado:
Seja G = (V, E) um grafo orientado ou não
orientado. Denotando por δ(u, v) a distáncia
entre os vértices u e v, medida em número de
arestas, é INCORRETO afirmar:
- Seja s ∈ V um vértice arbitrário. Então, para qualquer aresta (u, v) ∈ E,
δ(s, v) ≤ δ(s, u) + 1
- Suponha que a busca em largura estão rodando em G a partir de um dado vértice inicial s ∈ V.
Em seguida ao término, para cada vértice v ∈ V, o valor d[v] computado pela busca em largura satisfaz d[v] ≥ δ(s, v).
- Para grafos orientados ou não orientados, a representação por lista de adjacência tem a propriedade desejada de que a quantidade de memória que ela requer é Θ(V + E)
- Suponha que os vértices vi, vj são
enfileirados durante a execução da busca em largura,
e que vi é enfileirado antes de vj. Então d[vi] ≤ d[vj]
- NDA
Definições úteis:
δ(s, v) é a distância do menor caminho (shortest-path distance) de s até v com o menor múmero de arestas em qualquer caminho do vértice s para o vértice v; se não há caminho de s para v, então δ(s, v) = ∞.
d[u] é a distância do vértice inicial (fonte) s para o vértice u computada pelo algoritmo de busca em largura.
Autor(a): Jonathas Campi Costa