HOME INHALT DOWNLOAD AUTOR IMPRESSUM

vorwärts zurück3.4 Zusammenfassung des neuen Lösungsansatzes


 

english version


Aufgrund der Zerlegung jedes Gesamtgraphen in zwei gleichstrukturierte Teilgraphen erhält  jede weitere Kante einen Freiheitsgrad hinsichtlich ihres Platzes im Teilgraphen. Weil jede Berechnung mit dem Knoten Nr. 1 beginnt, ist die Zahl der Freiheitsgrade um 1 kleiner als die Zahl der Kanten. Liegt Symmetrie vor, so gewinnt man für jede (bis auf die erste) Kante zusätzlich einen Freiheitsgrad hinsichtlich ihrer Richtung. Diese gewonnenen Freiheiten ermöglichen es, alle Gesamtgraphen auf ein vergleichsweises Minimum von Teilgraphen zurückzuführen.

Der Preis für die Zerlegung ist die später notwendige Zusammenführung zweier Teilgraphen wieder zu einem Gesamtgraphen. Dieser Aufwand ist jedoch minimal im Vergleich zum Gewinn, der durch die kürzeren Berechnungen der Teilgraphen erzielt wird. 

Dabei kommen zu der minimalen Anzahl von Teilgraphen zwei weitere Besonderheiten den Berechnungen entgegen:
1. 
Zum einen hat die Häufigkeitsverteilung der Zahlenwerte aller Teilgraphen (wie auch bei den Gesamtgraphen) in etwa die Form einer Normalverteilung, so dass an dem hier interessierenden unteren Rand der Verteilung nur vergleichsweise wenige Teilgraphen vorhanden sind. 
2. 
Als weitere Besonderheit kann man die triviale Tatsache ausnutzen, dass bei zwei Summanden der Wert des kleineren Summanden maximal die Hälfte der Summe beider Summanden erreichen kann. Ausgehend vom bereits errechneten kleinsten Gesamtgraphen kann man also die Berechnung der Teilgraphen auf diejenigen Teilgraphen beschränken,  deren  Zahlenwert höchstens die Hälfte des kleinsten bereits gefundenen Gesamtgraphen erreicht. 

Weiter kann die Rechenzeit durch geschickte Nummerierung der Knoten und durch die in der einer oder anderen Form bekannte Verminderung der Kanten um einen Fixbetrag zusätzlich verkürzt werden. 

Die eigentliche Besonderheit der ZIP-Methode liegt aber in der Reduzierung der Zahl aller Gesamtgraphen auf eine minimale Zahl  von Teilgraphen. Die ZIP-Methode ersetzt nicht unbedingt andere Verfahren, sondern kann mit diesen kombiniert bzw. ihnen ggf. vorgeschaltet werden.

(24.05.2003)

vorwärts zurück