|

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)
|
|