Neuer kombinatorischer Lösungsansatz

HOME INHALT DOWNLOAD AUTOR IMPRESSUM

3.3 Mächtigkeiten

Mächtigkeit der Graphfamilie (bei gerichteten Kanten)	= (n-1)!	(1)
Mächtigkeit der Graphfamilie (bei Symmetrie)	= (n-1)! / 2	(2)
Mächtigkeit der Teilgraphfamile (bei gerichteten Kanten)	= 2(n-1)! / (n/2-1)! · 1	(3)^*)
Mächtigkeit der Komplement-Teilgraphfamilie für jeden einzelnen Teilgraph (bei gerichteten K.)	= (n/2-1)! · 1	(4)^*)
Mächtigkeit der Teilgraphfamile (bei Symmetrie)	= (n-1)! / (n/2-1)! · 2^(n/2-1)	(5)^*)
Mächtigkeit der Komplement-Teilgraphfamilie für jeden einzelnen Teilgraph (bei Symmetrie)	= (n/2-1)! · 2^(n/2-1)	(6)^*)

Teilgraph und Komplement-Teilgraph gehören derselben Teilgraphenfamilie an, die um Größenordnungen kleiner sind als die Mächtigkeit der Graphfamilie. Im Vergleich zu diesem Vorteil ist die Anzahl der Berechnung der Teilgraphen für alle Iterationsschritte minimal.

Bemerkung:

Jeder Teilgraph ist auch Komplement zu allen seinen Komplement-Teilgraphen.

Selbst bei Symmetrie wächst mit Zunahme der Knoten bei der Teilgraphfamilie die Mächtigkeit mit 1 · 3 · 5 · 7 · 9 · 11 · .... · (n-1), so dass auch hier eine Grenze erreicht wird, bei der eine Optimallösung nicht mehr berechenbar ist. Ohne Qualitätsverlust muss durch die Zerlegung jedoch nur ein Bruchteil der Graphen berechnet werden. Dies gilt auch bei gerichteten Graphen.

Die Grenze der Berechenbarkeit kann ggf. abhängig von den Ausprägungen des interessierenden Merkmals nach oben verschoben werden. Nach vorsichtiger Schätzung kann man davon ausgehen, dass abhängig von den konkreten Kantenlängen ein optimaler Gesamtgraph dann gefunden wird, wenn es möglich ist, den kleinsten Teilgraphen zu bestimmen.

Anmerkungen und Erläuterungen

^*)Formeln und graphische Darstellung berichtigt: 12.02.2003