Sortierung bei Prim

tdchnk
Neuling
Neuling
Beiträge: 8
Registriert: 22. Jun 2016 14:14

Sortierung bei Prim

Beitrag von tdchnk » 22. Jun 2016 14:34

Während angegeben ist, dass Q und V lexikographisch sortiert sind, ist mir unklar, nach welchen Kriterien Kanten mit gleicher Kantenlänge zum gleichen Knoten ausgewählt werden.
Im angehängten Fall, wird in der nächsten Iteration die Kante (c,j) zu E hinzugefügt, obwohl (c,f) nach den mir bekannten Kriterien gleichwertig zu betrachten wäre. Nun ist meine Frage also, worauf man in einem solchen Fall achten sollte, um auf das richtige Ergebnis zu kommen.
Dateianhänge
Screenshot (5).png
Screenshot (5).png (86.58 KiB) 1215 mal betrachtet

diego2404
Erstie
Erstie
Beiträge: 12
Registriert: 30. Apr 2015 10:27

Re: Sortierung bei Prim

Beitrag von diego2404 » 24. Jun 2016 10:33

Hi,

(c,j) wird als nächste Kante gewählt, weil b mit j vor f verbunden wurde.

Die lexikographische Wahl wird erst dann eingesetzt, wenn man AUS einem Knoten 2 gleichlange Möglichkeiten hat.

z.B
a --- 4 ---> b
a --- 4 ---> c
als erste wählt man dann (a,b)

LG,
Diego

suiram122
Neuling
Neuling
Beiträge: 1
Registriert: 6. Jul 2016 21:12

Re: Sortierung bei Prim

Beitrag von suiram122 » 6. Jul 2016 21:25

Wieso nimmt Prim die Kante (b,d), obwohl c zuerst mit j verbunden war?
screenshot_prim.png
screenshot_prim.png (44.22 KiB) 1035 mal betrachtet

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Sortierung bei Prim

Beitrag von SophiaLi1 » 23. Sep 2017 17:43

Ich hab ein ähnliches Problem:

PrimFehler.JPG
PrimFehler.JPG (40.05 KiB) 753 mal betrachtet
Nabla hat zuerst die Kante (b,j) genommen, während ich (b,f) genommen habe. Beide Kanten sind gleich lang und lexikographisch wäre (b,f) vor (b,j). Mir scheint es, als wäre hier ein Fehler in Nabla.
Dateianhänge
PrimFehler2.JPG
PrimFehler2.JPG (17.6 KiB) 753 mal betrachtet

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: Sortierung bei Prim

Beitrag von Hans123 » 25. Sep 2017 12:23

b,f macht doch auch keinen Sinn, wenn f schon in deinem Spannbaum ist?

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: Sortierung bei Prim

Beitrag von Hans123 » 25. Sep 2017 12:48

Laut Herr Weihes offiziellem Video zu Prim hat man im Übrigen 'freie Wahl', wenn mehrere Kanten die gleiche Länge haben. Da die Klausur ja nicht den Nablaprüfalgorithmus verwendet sondern von hoffentlich fähigen Leuten korrigiert wird, sollte das also eigentlich ohnehin kein Problem sein, da dann alle Lösungen richtig wären.

Antworten

Zurück zu „Archiv“