Drzewa rozpinające

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
leszczu450
Użytkownik
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

Post autor: leszczu450 »

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.
Ostatnio zmieniony 16 sty 2014, o 20:43 przez leszczu450, łącznie zmieniany 1 raz.
Awatar użytkownika
Zordon
Użytkownik
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

Post autor: Zordon »

a) wystarczy żeby wagi były parami różne, wtedy można udowodnić, że jest tylko jedno MST
b) graf pełny, wszystkie wagi 1
Awatar użytkownika
leszczu450
Użytkownik
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

Post autor: leszczu450 »

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.
Awatar użytkownika
Zordon
Użytkownik
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

Post autor: Zordon »

Tak, MST to z angielskiego. A co do a) to masz rację naturalnie.
Awatar użytkownika
leszczu450
Użytkownik
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

Post autor: leszczu450 »

Zordon, dziękuję za pomoc. Przy okazji minmalnych drzew rozpinających, algorytm Kruskala to zachłanna metoda . Istnieją dynamiczne?
Awatar użytkownika
Zordon
Użytkownik
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

Post autor: Zordon »

Co rozumiesz przez "dynamiczne"? Nie ma formalnego podziału algorytmów na takie klasy: "zachłanne", ...
Awatar użytkownika
leszczu450
Użytkownik
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

Post autor: leszczu450 »

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.
Awatar użytkownika
Zordon
Użytkownik
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

Post autor: Zordon »

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.
Awatar użytkownika
leszczu450
Użytkownik
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

Post autor: leszczu450 »

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 : )
ODPOWIEDZ