On 01.07.2014 20:59, A.L. wrote:
> On Tue, 01 Jul 2014 18:46:08 +0200, bartekltg <b...@g...com>

****

>>> Nowy problem:
>>> - nie można eliminować krawędzi gdy nie eliminujemy wierzchołków
>>> - eliminując wierzchołek, eliminujemy krawędzie połączone z tym
>>> wierzchołkiem
>>> Chodzi o to, aby wyeliminować najmniejszą możliwą liczbę wierzchołków,
>>> aby wszystkie pozostałe były samotne i nie było żadnej krawędzi w grafie.

****

>> Problem rzeczywiście ma nazwę i jest jako tako rozpoznany.
>>
>> http://en.wikipedia.org/wiki/Maximum_independent_set
#Finding_maximum_independent_sets
>>
>> Na zachętę, problem NP-trudny;-)


> To jest inny problem niz postawiony pzrez OP. OP chce eliminowac
> wierzcholki, ten problem jak wyzej niczego nie eliminuje. W tym
> problemie, dla DANEGO grafu poszukuje sie wierzcholkow nie polaczonych
> krawedzia

Przeczytaj to raz jeszcze. To dokładnie ten sam problem.
Dla danego grafu wyznaczasz zbiór niezależny i wyrzucasz wszystkie
wierzchołki do niego nie należące, wydawało mi się, że to oczywiste
uzupełnienie.

Każda krawędź w grafie ma co najmniej jeden konic w dopełnieniu zbioru
niezależnego, więc zostanie usunięta. Dostajesz to, o co pyta Borneq.

pzdr
bartekltg