 [Algorytm] Usuwanie największej ilości krawędzi w grafie |
| [Algorytm] Usuwanie największej ilości krawędzi w grafie |
  18.03.2014, 07:57:24
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 
-------------------- |
 |
 
|
 |
|
18.03.2014, 10:59:21
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)?
-------------------- |
|
|
|
|
18.03.2014, 11:18:15
Post
#3
|
|
|
Grupa: Zarejestrowani Postów: 623 Pomógł: 11 Dołączył: 1.01.2009 Skąd: Wrocław Ostrzeżenie: (0%)
|
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. -------------------- |
|
|
|
|
18.03.2014, 21:57:40
Post
#4
|
|
 Grupa: Zarejestrowani Postów: 578 Pomógł: 69 Dołączył: 15.04.2007 Skąd: Wrocław Ostrzeżenie: (0%)
|
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 |
|
|
|
 |
|
Wersja Lo-Fi | Aktualny czas: 19.07.2025 - 20:55 |
