W dniu 2014-07-01 16:02, Borneq pisze:
> 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.

Mam pewien pomysł:
Otóż gdy mamy 1 wierzchołek - nic nie musimy robić
gdy mamy połączone 0 z 1 - usuwamy 0 lub 1
gdy mamy 3 wierzchołki, mamy 3 przypadki różniące się tylko identyfikatorami
0-1-2: usuwamy 1
0-2-1: usuwamy 2
1-0-2: usuwamy 0
i przypadek trójkata 0-1-2 i 2 z 0: zostawiamy tylko jeden dowolny
wierzchołek. W pierwszej fazie usuwamy dowolny jeden wierzchołek
sprowadzając do dwóch wierzchołków.
Coś mi mówi, że w każdym kroku usuwamy ten wierzchołek, który ma
najwięcej krawędzi. Czy tak będzie?
Jak to optymalnie zrobić? Szukanie w każdym kroku maksymalnego da czas
kwadratowy, a porządek posortowania po ilości krawędzi zostanie zepsuty
po eliminacji wierzchołka