Graphentheorie

Wissenschaft Physik
1

An alle Matheversteher habe ich eine Frage zum topologischenSortieren von Graphen.

Ich habe mir mal den Wikipedia-Artikel angeschaut:

http://de.wikipedia.org/wiki/Topologische_Sortierung…

und habe eine Frage:
Die Beispiele aus dem Wiki-Artikel sind alle mit Knoten A,B,C,D… beschriftet. Spielt bei der Sortierung auch die Gewichtung der Knoten eine Rolle? (A vor B, B vor C,…)

So wie ich das verstanden habe ist die einzige Gewichtung jene, die durch die Vorgänger (eingehende Kanten) bestimmt ist. Also spielt die Numerierung A,B,C… keine Rolle.

Dann habe ich noch eine letzte Frage: Auf der Wiki-Seite gibt es 2 Beispielgraphen: Graph1 und Graph2.

Ist ABGDCEF (Graph1) auch eine richtige Lösung und ABCDE bei Graph2 ebenfalls richtig? Meiner Meinung gibt es ja mehrere Möglichkeiten.

Danke schonmal im Vorfeld. Wenn ich etwas falsch verstanden habe bitte ich um einen Tipp was ich nicht beachtet habe, aber bitte nicht zu mathematisch :wink: Da ich sonst nur Bahnhof verstehe.

Gruß

Sebastian

2

Hallo,

könnte man auch unter Informatik fragen, sollte hier aber auch nicht so verkehrt sein.

http://de.wikipedia.org/wiki/Topologische_Sortierung…

und habe eine Frage:
Die Beispiele aus dem Wiki-Artikel sind alle mit Knoten
A,B,C,D… beschriftet. Spielt bei der Sortierung auch die
Gewichtung der Knoten eine Rolle? (A vor B, B vor C,…)

Nein.

So wie ich das verstanden habe ist die einzige Gewichtung
jene, die durch die Vorgänger (eingehende Kanten) bestimmt
ist. Also spielt die Numerierung A,B,C… keine Rolle.

Richtig.

Dann habe ich noch eine letzte Frage: Auf der Wiki-Seite gibt
es 2 Beispielgraphen: Graph1 und Graph2.

Ist ABGDCEF (Graph1) auch eine richtige Lösung und

Ja.

ABCDE bei
Graph2 ebenfalls richtig? Meiner Meinung gibt es ja mehrere
Möglichkeiten.

Ja.

Grüße,
Moritz

3

Super, dann glaube ich, dass ich es verstanden habe :wink:

Vielen Dank Moritz für die schnelle Hilfe und deine damit verbundene Zeit!

Gruß

Sebastian