[Algorytm] Usuwanie największej ilości krawędzi w grafie Opcje

[sweter]

Cześć,

Potrzebuję algorytmu do usuwania największej ilości krawędzi z grafu. Potrzebny jest "na wczoraj", więc prosiłbym o jakiś gotowiec.
Jedyne co na szybko udało mi się dzisiaj wymyślić to usuwanie krawędzi, która będzie miała najmniejsze stopnie wierzchołków v i u. Intuicyjnie wydaje mi się to poprawne, ale nie jestem pewien, czy przy jakimś nietypowym przypadku algorytm nie zwróci błędnej wartości.

Z góry dziękuję za wszelka pomoc (IMG:style_emoticons/default/smile.gif)

[redeemer]

Nie do końca rozumiem co znaczy "usuwanie największej ilości krawędzi z grafu". Może chodzi Ci o minimalne drzewo rozpinające (ang. minimum spanning tree)?

[sweter]

Po prostu chcę usunąć jak najwięcej krawędzi z grafu, tak aby moc ich zbioru była jak większa.
Usunięte krawędzie nie muszą tworzyć żadnej konkretnej struktury, czyli np. drzewa.

[timon27]

Usuń wszystkie.

(Przynajmniej z tego co mówisz wnioskuję takie rozwiązanie. Chcesz usunąć jak najwięcej krawędzi, a jednocześnie nie dajesz żadnego ograniczenia).

Ten post edytował timon27 18.03.2014, 22:00:10