Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

> [Algorytm] Usuwanie największej ilości krawędzi w grafie
sweter
post
Post #1





Grupa: Zarejestrowani
Postów: 623
Pomógł: 11
Dołączył: 1.01.2009
Skąd: Wrocław

Ostrzeżenie: (0%)
-----


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)
Go to the top of the page
+Quote Post
 
Start new topic
Odpowiedzi
redeemer
post
Post #2





Grupa: Zarejestrowani
Postów: 915
Pomógł: 210
Dołączył: 8.09.2009
Skąd: Tomaszów Lubelski/Wrocław

Ostrzeżenie: (0%)
-----


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)?
Go to the top of the page
+Quote Post

Posty w temacie


Reply to this topicStart new topic
2 Użytkowników czyta ten temat (2 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 



RSS Aktualny czas: 16.10.2025 - 14:34