1 Prova

Prévia do material em texto

Universidade Federal da Bahia
MATA53 - Teoria dos Grafos
Professor Rafael Augusto de Melo
Primeira avaliação - 2017.1
Instruções: Escreva suas respostas de maneira clara, objetiva e organi-
zada. Defina todas as estruturas auxiliares necessárias para os seus algorit-
mos. A maior nota posśıvel para uma resposta dependerá da complexidade
do algoritmo implementado, i.e., um algoritmo correto mas pouco eficiente
não garante nota máxima na questão. A interpretação das questões faz parte
da avaliação.
Questão 1: Implemente um algoritmo de tempo O(V + E) para calcular
o grafo de componentes de um grafo dirigido G = (V,E). Certifique-se de
que haja no máximo uma aresta entre dois vértices no grafo de componentes
produzido pelo seu algoritmo.
Questão 2: Implemente um algoritmo linear que determina (sim ou não)
se um grafo não direcionado G = (V,E) é bipartido. Discorra sobre sua
corretude.
Questão 3: Dado um grafo simples não-orientado G com pesos nas arestas,
o problema da árvore geradora minimax consiste em encontrar uma árvore
geradora T de G que minimize o peso da aresta de maior peso de T . Imple-
mente um algoritmo eficiente para resolver o problema da árvore geradora
minimax. Discorra sobre sua corretude.
Questão 4: Seja um circuito euleriano W = v0e1v1e2v2...emvm de um
grafo G, onde vm = v0. Suponha que vi = v0, tal que 0 < i < m. Mostre
que v0Wviemvm−1
←−
Wvi também é um circuito euleriano de G.
1