Tabelle 4.5. Ausgangsmatrix des Beispiels 4.2

Bei Anwendung der in 3.2.1. genannten Zerlegungs-, Reihenfolge- und Symmetrieregeln lassen sich die 181440 (=362880 / 2) symmetrischen Graphen in 945 Teilgraphen zerlegen. Diese geringe Anzahl von 945 Teilgraphen läßt sich ggf. auch ohne technische Hilfsmittel vollständig berechnen und dann nach der Summe der Kantenlängen (Ausprägung des Kantenmerkmals) sortieren:

Tabelle 4.6. Teilgraphen sortiert nach Summe der Kantenlängen ( Auszug)

Betrachtet man die Häufigkeitsverteilung der Kantensummen, so zeigen die Ausprägungen die Form einer Normalverteilung. Für die Berechnungen ist diese Tatsache besonders günstig, weil an den Rändern nur einige wenige Teilgraphen für Feststellung des optimalen Gesamtgraphen beteiligt sind. 
Im Vergleich ist dazu auch die Häufigkeitsverteilung der 181.440 Gesamtgraphen angeführt.

Tabelle 4.7. Häufigkeitsverteilung

(Anzahl der Gesamtgraphen ergänzt am 07.07.2005)

Bemerkung:
Die Häufigkeitsverteilung läßt sich graphisch - wegen der extrem unterschiedlichen Anzahl von Teilgraphen und Gesamtgraphen - nur andeutungsweise darstellen.

Erster Schritt:
Der kleinste Komplement-Teilgraph zum kleinsten Teilgraphen Nr.1 ist der Teilgraph Nr.11. Die Gesamtsumme beider Summen der Kantenlängen ist 76 + 100 = 176. Alle übrigen 934 Teilgraphen von Nr. 12 (S=101) bis Nr. 945 (S=433) scheiden damit für die Feststellung des kleinsten Graphen aus.

Weitere Iterationsschritte:
In weiteren Iterationsschritten sind Graphen zu suchen, die den bisherigen Minimalwert von S=176 unterschreiten. Ein Graph kann ggf. dann eine kleinere Kantenlänge von S=176 haben, wenn Teilgraphen mit Kantenlängen von weniger als der Hälfte von 176 = 88 existieren. Nur die Teilgraphen Nr.2 (S=77) , Nr.3 (S=79) und Nr.4 (S=83) sind kleiner als S=88, so dass maximal drei weitere Iterationsschritte durchzuführen sind.

Zweiter Iterationsschritt:
Zum Teilgraphen Nr.2 mit einer Kantenlänge von S=77 können höchstens die Teilgraphen Nr.3 bis Nr.9 mit Kantenlängen von weniger als S=99 (176-77) Komplement-Teilgraphen sein. Weil alle Teilgraphen Kanten des Teilgraphen Nr. 2 enthalten, scheidet der Teilgraph Nr. 2 für die Lösung aus.

Dritter Iterationsschritt:
Der Teilgraph Nr. 3 mit einer Kantenlänge von S=79 bildet mit dem Teilgraphen Nr.7 mit S=96 einen Graphen, dessen Gesamtkantenlänge nur S=175 beträgt. Sie ist neuer Ausgangswert.

Vierter und letzter Iterationsschritt:
Zum Teilgraphen Nr.4 (S=83) kann ggf. nur der Teilgraph Nr.5 (175 -83 = 92) Komplement-Teilgraph sein. In beiden Teilgraphen ist jedoch die Kante 4-6 enthalten, so dass beide zusammen keinen Graphen bilden können.

Ergebnis:
Nachdem alle relevanten Teilgraphen überprüft wurden, ist der optimale Graph mit S=175, bestehend aus den Teilgraphen Nr.3 (S=79) und Nr.7 (S=96) gefunden. Für Graphen mit nur 10 Knoten ist eine Kantenminimierung und ggf. Umnummerierung der Knoten nicht erforderlich.

Bemerkung:
Jede Kante kommt in den Teilgraphen gleich häufig (genau 105-mal) vor. Mit zunehmender Knoten-Nummer verringert sich die Zahl der von diesem Knoten ausgehenden Kanten. Z.B. gehen vom Knoten Nr. 1 die Kanten 1-2 bis 1-10  (= 9 Kanten), vom Knoten Nr.2 die Kanten 2-3 bis 2-10 (= 8 Kanten) und vom Knoten Nr. 3 die Kanten 3-4 bis 3-10 (= 7 Kanten), usw. aus.

Die Beziehung zwischen Anfangsknoten einer Kante und Kantenplatz sowie die Anzahl der Kanten je Kantenplatz zeigt die folgende Übersicht:

Tabelle 4.8. Beziehung der Kanten zum Kantenplatz

Jeder Knoten kann entweder als Anfangsknoten oder als Endknoten einer Kante im Teilgraphen auftreten, insgesamt also immer 945-mal. Als Anfangsknoten tritt der Knoten Nr. 1 in jeder ersten Kante der 945 Teilgraphen auf, als Endknoten tritt er nie auf. Der folgende Knoten Nr. 2 tritt als Anfangsknoten nur noch in 840 von 945 Teilgraphen auf und 105 Mal als Endknoten, usw..   Schließlich tritt der Knoten Nr. 10 als Anfangsknoten nie auf, dafür in jedem der 945 Teilgraphen als Endknoten.

(Stand: 07.07.2005)

Anmerkungen und Erläuterungen