Drzewa rozpinające
- leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
Drzewa rozpinające
Cześć!
Mam za zadanie podać przykład spójnego nieskierowanego grafu ważonego \(\displaystyle{ G}\) takiego, że \(\displaystyle{ |V(G)| \ge 6}\) oraz
a) istnieje dokładnie jedno minimalne drzewo rozpinające grafu \(\displaystyle{ G}\).
b) istnieją co najmniej dwa różne minimalne drzewa rozpinające grafu \(\displaystyle{ G}\).
Dumam nad tym i dumam jednak nie mogę tego narysować. Proszę o pomoc.
Mam za zadanie podać przykład spójnego nieskierowanego grafu ważonego \(\displaystyle{ G}\) takiego, że \(\displaystyle{ |V(G)| \ge 6}\) oraz
a) istnieje dokładnie jedno minimalne drzewo rozpinające grafu \(\displaystyle{ G}\).
b) istnieją co najmniej dwa różne minimalne drzewa rozpinające grafu \(\displaystyle{ G}\).
Dumam nad tym i dumam jednak nie mogę tego narysować. Proszę o pomoc.
Ostatnio zmieniony 16 sty 2014, o 20:43 przez leszczu450, łącznie zmieniany 1 raz.
- leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
Drzewa rozpinające
Zordon, a czy Wy przypadku a) nie wystarczy narysować drzewa o 6 wierzchołkach i dowolnych wagach? Wtedy drzewem rozpinającym będzie to samo drzewo. A wagami się nie ma co przejmować bo i tak to drzewo jest jedno więc i minimalne. Może tak być? Czy coś mi umyka?-- 16 sty 2014, o 20:34 --+ MST ? To z angielskiego ? Pierwsze co mi przychodzi do głowy to minimal spanning tree.
- leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
Drzewa rozpinające
Zordon, dziękuję za pomoc. Przy okazji minmalnych drzew rozpinających, algorytm Kruskala to zachłanna metoda . Istnieją dynamiczne?
- leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
Drzewa rozpinające
Zordon, chodzi mi o programowanie zachłanne i dynamiczne.
Ja za definicję programowania zachłannego miałem to, że do rozwiązania problemu wybieramy w danym miejscu jedynie lokalnie najlepszą decyzję. Problem wyboru zajęć poddaje się programowaniu zachłannemu.
Zaś programowanie dynamiczne- podzielenie problemu na mniejsze, prostsze. Zebranie wyników na przykład w tablicy i na ich podstawie rozwiązać problem wyjściowy.
Ja za definicję programowania zachłannego miałem to, że do rozwiązania problemu wybieramy w danym miejscu jedynie lokalnie najlepszą decyzję. Problem wyboru zajęć poddaje się programowaniu zachłannemu.
Zaś programowanie dynamiczne- podzielenie problemu na mniejsze, prostsze. Zebranie wyników na przykład w tablicy i na ich podstawie rozwiązać problem wyjściowy.
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Drzewa rozpinające
No więc sam widzisz jak rozmyte są te pojęcia. Nie ma sensu klasyfikowanie algorytmów w ten sposób. Wszystkie popularne algorytmy do szukania MST mają nutę zachłanności. Raczej ciężko się w nich doszukiwać programowania dynamicznego. To ma nawet pewną przyczynę teoretyczną, mianowicie graf ze strukturą zbiorów acyklicznych stanowi matroid. Z kolei, mówiąc najbardziej ogólnie, zachłanne wybory w matroidzie są optymalne.
- leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
Drzewa rozpinające
Zordon, pojęcie matroidu jest mi nieznane. Wikipedia coś tam o tym mówi, jednak nie wiem jak odnosi się to do teorii grafów i problemów znajdowania MST. Niemniej jednak bardzo dziękuję za pomoc. Problem został rozwiązany : )