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_set
#Finding_maximum_independent_sets

Na zachętę, problem NP-trudny;-)

pzdr
bartekltg