topologische Sortierung

[kelev]

Hallo Gemeinde,

wie bestimme ich die Anzahl der möglichen topologischen Sortierungen in einem Graphen.

Graph gegeben: (a,,(a,c)(b,e),(c,d),(d,e)

z.B. auf wikipedia stehen nur das mehrere existieren, aber wie viele?

danke!

Bearbeitet 12. Juni 2011 von kelev

[martinposer]

Hallo,

vielleicht hilft dir das weiter:

www-i1.informatik.rwth-aachen.de/~algorithmus/algo8.php

[kelev]

tut mir leid, aber wo steht die Anzahl der möglichen topologischen Sortierungen?

Ich kann's nicht finden..

[flashpixx]

Wir kennen die Element a,b,c,d und e nicht, d.h. darüber müssen noch Informationen vor liegen! Deine Tupel müssen somit eine Relation besitzen (siehe dazu den Wikipediaartikel)

[Bubble]

aber wie viele?

Schreib Dir Deinen Graphen auf. Schreibe alle Sortierungen auf. Zähle sie. Fertig