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.

Jeżeli mamy spójne składowe i wybieramy z każdej składowej po
wierzchołku, to możemy tak zrobić dla B i C. Natomiast dla A należy
usunąć wierzchołek 1 i zostawić 0 i 2.
Inny przykład: wierzchołki połączone w kolejkę:
0-1-2-3-4-5-6-7-8
Po operacji ma zostać: 0,2,4,6,8 - czyli co drugi
Jak to zalgorytmizować? Czy jest to znany problem? Jeśli tak, pod jaką
nazwą szukać?