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

>On 01.07.2014 16:02, Borneq wrote:
>> Najpierw opiszę poprzednie zadanie, z którym sobie dobrze radzi algorytm
>> o nazwie "Znajdowanie spójnych składowych w grafie"
>> http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol018.ph
p
>>
>> Mamy graf o wierzchołkach 0..7
>> poszczególne wierzchołki są ze sobą połączone (połączenia dwukierunkowe)
>> 0 z 1
>> 1 z 2
>> 3 z 4
>> 5 z 6
>> 6 z 7
>> 7 z 5
>> Powyższy algorytm dzieli graf na składowe
>> A: 0,1,2
>> B: 3,4
>> C: 5,6,7
>>
>> 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_se
t#Finding_maximum_independent_sets
>
>Na zachętę, problem NP-trudny;-)
>
>pzdr
>bartekltg

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

A.L.