Pós-graduação em Ciência da Computação – UFU
Disciplina – Análise de Algoritmos
Profa. Sandra de Amo
Exercícios– AULA 14
Exercicio 1.
a) Construa a lista de adjacências para cada vértice do grafo.
b) Aplique o algoritmo de busca em profundidade no seguinte grafo G, mostrando
a cada passo o estado do array Visitados e as listas de adjacências dos vértices.
A cada vez que uma aresta (v,u) é escolhida na lista L_v de adjacências do
vértice v, esta aresta é retirada da lista ! (a melhor estrutura para se utilizar
aqui é uma pilha. A operação pop é utilizada para retirar o primeiro elemento
da pilha).
c) Retorne, para cada vértice v os números Pre[v] e Pos[v]. Os números Prev[v] em
ordem crescente correspondem à ordem em que os vértices do grafo são visitados.
d) Construa um array de m posições, m = |E| (número de arestas), contendo 0s ou 1s,
dependendo se a aresta correspondente à posição é percorrida em sentido positivo
(aresta de árvore) ou não (aresta de backtracking). A ordem das arestas corresponde à
ordem em que aparecem nas listas de adjacências. Por exemplo, suponha que
tenhamos 4 vértices A, B, C,D (nesta ordem) e 4 arestas e que as respectivas listas de
adjacência são:
L_A = [B, C]
L_B = [A, D]
L_C = [A, D]
L_D = [B,C]
Então a ordem das arestas é a seguinte: <(A,B), (A,C), (B,D), (C,D)>
Exercício 2. Mostre por indução em k: “Para todo k ≥ 0, se um vértice w dista k passos do
vértice v então no final da execução de Explore(G,v) a variável visited(w) = true.” (Utilizamos
este resultado na prova de que o algoritmo Explore é correto, isto é, produz EXATAMENTE
todos os vértices alcançáveis a partir de v no grafo G).
Exercício 3. Em um grafo não dirigido, define-se o grau de um vértice v (denotado por d (v))
como sendo o número de vizinhos de v. Exemplo, no grafo do exercicio 1, d (A) = 2.
a) Mostre que :
b) Use a parte (a) para mostrar que o número de vértices com grau impar é par.
c) Quais os vértices do grafo do Exercicio 1 que têm grau impar ?
Exercício 4. Utilizando a rotina Explore(G,v), dê o pseudo-código dos algoritmos para
resolver os seguintes problemas de grafos:
a) Dados dois vértices em um grafo (dirigido ou não), determinar se existe um caminho
ligando estes vértices.
Input: G, u,v
Output: “Yes” se existe caminho ligando u a v, “Não” em caso contrário
b) Determinar o número de componentes conexas de um grafo G (dirigido ou não)
(vimos em sala de aula !)
Input: G
Output: N = número de componentes conexas de G
c) Determinar se G é conexo (G dirigido ou não).
Input: G
Output: “Yes” se G é conexo, “Não” em caso contrário
Exercicio 5. Adapte o exercicio 4(a) para que um caminho entre u e v seja retornado pelo
algoritmo, caso existir. Mostre que:
a) o caminho retornado depende da ordem considerada nos vértices. Caso a ordem
seja alterada, um caminho diferente poderá ser retornado.
b) Mostre que o caminho retornado (fixada uma ordem nos vértices), nem sempre é o
mais curto.
c) Proponha um algoritmo que retorne o caminho mais curto entre dois vértices,
utilizando a rotina proposta no exercicio 4(a). Veja que (pela discussão em 5(a))
para cada ordem considerada nos vértices, a rotina pode ser aplicada em tempo
linear, produzindo um caminho entre u e v.
d) Calcule a complexidade do algoritmo proposto em (c).
Exercicio 6: Um grafo não-dirigido é bipartite se o conjunto de vértices pode ser particionado em
dois subconjuntos disjuntos V1, V2 tais que vértices de um mesmo subconjunto não são ligados por
arestas.
a) Dê um algoritmo linear (em |V| e em |E|) para determinar se um grafo nãodirigido é bipartite.
b) Mostre que um grafo não-dirigido é bipartite se e somente se pode ser colorido
com 2 cores.
Exercicio 7: Tem-se 3 reservatórios com tamanhos de 10 litros, 7 litros e 4 litros respectivamente.
Os reservatórios de 7 e 4 litros estão inicialmente cheios e o de 10 litros está inicialmente vazio.
Somente 1 tipo de operação é permitido: despejar o conteúdo de um reservatório A em outro B até
que o reservatório A fique vazio ou que B fique cheio. Queremos saber se existe uma sequência de
operações que no final deixam 2 litros no reservatório de 7 litros e 2 litros no reservatório de 4
litros.
a) Modele este problema como um problema de grafos, especificando quais são os vértices e
as arestas, e enunciando a questão que se quer responder.
b) Que algoritmo deve ser aplicado para resolver o problema de grafos do item (a) ?
c) Encontre a resposta, aplicando o algoritmo.