[obm-l] Algoritmo em grafo

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Oi...

Suponha que tenhamos um grafo G=(V, E) e queiramos obter S contido em V tal
que para toda aresta e em E uma das pontas de e esteja em S.

Um algoritmo (guloso) que eu proponho para fazer isso é:
inicie S = Ø
escolha um vértice u com grau máximo, este vértice vai para S e elimine o
vértice u e todas arestas que saem dele do grafo G e repita o processo até
que o conjunto de arestas fique fazio.

A pergunta é: em relação a min{|S| : para todo e=(u, v) em E,  {u, v} inter
S != Ø} qual seria o tamanho do S encontrado por este algoritmo... ou seja,
em relação ao(s) conjunto(s) S ótimo(s) qual a aproximação que este
algoritmo nos dá?

[ ]'s

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================