Topologisch sortieren |
| 05.05.2009, 19:28 | gaus87 | Auf diesen Beitrag antworten » |
| Topologisch sortieren Der mit Hilfe der folgenden Knoten- und Kantenmenge beschriebene Graph soll topologisch sortiert werden: V = {a, b, c, d, e} und E = {(a, b), (a, c), (a, d), (b, c), (b, d), (d, c)}. Wie ich das ganze topologisch sortieren muss ist mir klar. Aber was soll ich mit dem e machen? Ist ja nicht mit dem Graphen verbunden.... Lg |
||
| 05.05.2009, 19:51 | Mathespezialschüler | Auf diesen Beitrag antworten » |
Guck dir die Definition einer topologischen Sortierung nochmal genau an. Dann sieht man auch, was man mit dem machen kann. |
||
| 05.05.2009, 20:04 | gaus87 | Auf diesen Beitrag antworten » |
Naja, haben in der Vorlesung nur dashier gekriegt: Algorithmus: Topologisches Sortieren Gegeben: Gerichteter Graph G = {V, E} ohne Zyklus. Gesucht: Nummerierung der Knoten {v1, ... , vn} : (vi, vj) e E => i<j (i, j = 1, ..., n), und dann noch den Algorithmus dazu, der eigentlich nur folgendes aussagt: Finde Senke v des Restgraphen, nenne sie vj, streiche v und alle Kanten, die nach v kommen, aus dem Restgraphen. Danach kam noch ein Beispiel ohne separatem Knoten.... |
||
| 05.05.2009, 20:05 | gaus87 | Auf diesen Beitrag antworten » |
Hab jetzt halt einfach mal e als Senke aufgefasst und sich selbst zugeordnet, weiß aber nicht ob das richtig ist |
||
| 05.05.2009, 22:10 | Mathespezialschüler | Auf diesen Beitrag antworten » |
Also laut der Definition, die bei Wikipedia steht, kannst du mit machen, was du willst. Laut dieser Definition ist nämlich eine topologische Ordnung des Graphen eine echte Obermenge , die eine strenge Totalordnung definiert. |
||
| 06.05.2009, 16:26 | gaus87 | Auf diesen Beitrag antworten » |
joa danke 
|
||
| Anzeige | ||
|
|
||
|
|
