Grafos - Conjunto dominante de vértices

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 [e-mail]

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 ı

2. Solucao do Problema
¸˜
Para resolver do problema, foram utilizadas trˆ s diferentes solucoes: gulosa, Backtracking e ¸˜ e Branch and Bound.
2.1. Solucao Gulosa
¸˜
A solucao gulosa foi implementada inicialmente tratando o problema como o de conjunto
¸˜
dominante. Primeiramente, os v´ rtices s˜ o ordenados de acordo com seus graus (quantas e a arestas incidem em um determinado v´ rtice). Ap´ s isso, s˜ o percorridos e, um por um, e o a ´ caso n˜ o tenha sido dominado e n˜ o faz parte da solucao, ele e ent˜ o adicionado a esse a a
¸˜
a conjunto e todos os seus adjacentes s˜ o adicionados aos dominados. Ap´ s percorrer todos a o os v´ rtices, o algoritmo percorre todos os v´ rtices dominados a procura de arestas entre e e
´
eles. Caso encontre, e porque a aresta que liga dois desses v´ rtices dominados ainda n˜ o e a
´
foi percorrida. O v´ rtice de maior grau entre esses dois e ent˜ o adicionado ao conjunto e a solucao e os dominados s˜ o atualizados.
¸˜
a
2.2. Backtracking
O algoritmo Backtracking simula o m´ todo de forca bruta para encontrar a melhor e ¸ solucao. Dado um grafo de n v´ rtices, o algoritmo faz permutacoes entre os n v´ rtices,
¸˜
e
¸˜
e colocando e tirando