1. Escrever um procedimento linear para, dado um grafo conexo não direcionado G = (V, E) que contém exatamente um ciclo, direcionar as arestas deste grafo de forma que os graus de entrada de todos os vértices no grafo direcionado gerado na saída sejam no máximo 1.

2. Seja T uma árvore enraizada não direcionada ( não necessariamente binária), representada pelas listas de adjacências. A cada vértice de T é associado um caracter tomado de um alfabeto finito. Seja P uma cadeia de caracteres representada por um array.
Faça um algoritmo para descobrir se o padrão P aparece pelo menos uma vez em um caminho da raiz até uma folha.
O algoritmo deve rodar em tempo O (n + m) no pior caso, onde n é o número de vértices na árvore, e m é o tamanho do padrão.
(Veja dica do Problema 7.34 no Udi Manber.)

3. Modificar o procedimento da Fig. 7.17 do livro de Udi Manber para dado um grafo não direcionado simples G = (V, E), identificar as arestas que compõem os caminhos mais curtos de um vértice dado n para cada um dos vétices de G. Caso haja mais de um caminho possível, um caminho com o menor número de arestas deve ter preferência.
IMPORTANTE: O custo do algoritmo modificado deve ser exatamente o mesmo custo do algoritmo na Fig. 7.17 referenciado.
Problema relacionado

Retorna à página principal do curso

[Última alteração em 08.novembro.99 por katia.]