[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
=========================================================================