On Tue, 01 Jul 2014 21:09:14 +0200, bartekltg <b...@g...com>
wrote:

>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.

A jezel zbior niezalezny jest pusty ("complete graph")?

Byc moze cegos nie rozumiem z problemu OP.

Zalozmy graf A-B, B-C, C-A, eliminujemy A a wiec krawedzie A-C, A-B,
zostaje B-C,. wiec eliminujemy B i zostaje C. Tego sie nie dostanie
twoim sposobem, bo zbior niezalezny grafu A-B-C jest pusty.

Byc moze OP powinien byc bardziej precyzyjny. Bardziej uwazne czytanie
postu OP nic nie da, przynakmniej ja nie moge nic wyczytac

A.L.