Projeto e An´ lise de Algoritmos (BCC 241) a Trabalho Pr´ tico II a Gabriel L. Franco1
1

Departamento de Computacao - Universidade Federal de Ouro Preto (UFOP)
¸˜
Caixa Postal 35.400 – Ouro Preto – MG – Brazil gabriel lafran@hotmail.com

1. Introducao do Problema
¸˜
´
Conjunto dominante e um problema em grafos que consiste em, dado um grafo G(V, E), para cada v pertencente ao conjunto V de v´ rtices, se v n˜ o e parte do conjunto dominante, e a ´ deve ent˜ o ser um v´ rtice adjacente a um dos v´ rtices desse conjunto. O problema tratado a e e ´
´
nesse trabalho e parecido, mas basea-se no dom´nio das arestas do grafo. O objetivo e ı encontrar o menor conjunto de v´ rtices poss´vel que cobre todas as arestas.
e …exibir mais conteúdo…

ores de solucoes poss´veis. E
¸˜
ı
¸˜ ´
´
A iteracao do algoritmo e similar ao caminhamento em ordem, tamb´ m conhecida como
¸˜
e
´
infixa, em uma arvore.
2.3. Branch and Bound
´
O Branch and Bound tem comportamento parecido com o Backtracking, mas e mais inteligente. Primeiramente pelo fato de n˜ o avaliar todas as poss´veis solucoes, filtrando as a ı
¸˜
que n˜ o s˜ o promissoras, ou seja, que at´ aquele momento j´ e poss´vel saber que n˜ o a a e a´ ı a chegar˜ o a uma solucao que seja melhor do que a melhor encontrada at´ o momento. a ¸˜ e Al´ m disso, o algoritmo recebe como entrada inicial uma solucao obtida anteriormente e ¸˜ por algum m´ todo, no caso desse trabalho o guloso. e 3. An´ lise dos algoritmos a ´
Os dois algoritmos que simulam o caminhamento em arvore s˜ o da ordem de O(2n ) pelo a fato de fazerem permutacoes pelos n v´ rtices do grafo, utilizando 1 para a presenca e 0
¸˜
e
¸
para a ausˆ ncia daquele v´ rtice na solucao. Mesmo que o Branch and Bound faca podas e e
¸˜
¸
´
na arvore, n˜ o verificando todas as poss´veis permutacoes, essa otimizacao n˜ o modifica a ı
¸˜
¸˜ a a ordem do algoritmo e, portanto, o Branch and Bound tamb´ m e da ordem O(2n ). A e ´ an´ lise do algoritmo guloso, dado que foi implementado para o trabalho, carece de uma a an´ lise mais detalhada. a Como explicado anteriormente, o algoritmo primeiro faz a ordenacao dos v´ rtices
¸˜
e
2
´ do grafo de