Hat man aufgrund der Rundreise fast immer eine räumliche Vorstellung des Problems, so liegt hier doch für den allgemeinen Fall eine algebraische Aufgabe vor, nämlich die Ermittlung einer Summe aus den gewichteten Kanten.

  
Der Hauptansatz der ZIP-Methode besteht darin, jeden Graphen so in zwei gleichstrukturierte Teilgraphen zu zerlegen, dass ein Teilgraph nur jede zweite Kante des Graphen enthält. Besteht ein Graph aus 1 Komponente mit n Kanten und n Knoten vom Knotengrad 2 (s. 1.2.), so setzt sich jeder Teilgraph aus n/2 Kanten sowie n Knoten mit dem Knotengrad 1 zusammen. Die Anzahl der  Komponenten im Teilgraph ist n/2. 

Zerlegt man alle Graphen, so stellt man fest, dass jeder Teilgraph mehrfach vorkommt, nur jeweils mit unterschiedlicher Reihenfolge der Kanten und bei Symmetrie mit einer anderen Richtung (s. Beispiel mit 6 Knoten). Dabei ist jede Kante im Teilgraphen von allen anderen Kanten unabhängig und kann aufgrund der durch die Zerlegung gewonnenen „Freiheiten“ an beliebiger Stelle und bei Symmetrie außerdem in beliebiger Richtung angeordnet sein, ohne dass sich die Summe aus den gewichteten Kanten ändert. 

Legt man nun beim Teilgraphen eine bestimmte Reihenfolge der Kanten und außerdem bei jeder Kante eine bestimmte Reihenfolge des Anfangs- und Endknoten fest, dann kann jeder Graph so in zwei Teilgraphen zerlegt werden, dass sich jeder der beiden Teilgraphen auf die festgelegte Struktur zurückführen lässt. Daraus folgt, dass nur diejenigen Teilgraphen, die dieser Struktur entsprechen,  berechnet werden müssen. Alle übrigen Teilgraphen bleiben unberücksichtigt. Die Anzahl aller zu berechnenden Teilgraphen wird dadurch minimal im Vergleich zur Anzahl aller möglichen Graphen.

Die Zerlegung hat somit eine quantitative Auswirkung hinsichtlich der minimalen Anzahl der Teilgraphen und gleichzeitig eine qualitative Auswirkung hinsichtlich der Kantenreihenfolge innerhalb der Teilgraphen.

Bemerkungen:

1. Damit ein Graph in zwei gleichstrukturierte Teilgraphen zerlegt werden kann, muss die Anzahl der Knoten geradzahlig sein; ggf. ist ein Pseudoknoten einzufügen.
    

2. Die Frage der Kurzzyklen stellt sich nicht bei der Berechnung der Teilgraphen, sondern erst beim Zusammensetzen zweier Teilgraphen zu einem Graphen.
    

3. Zur besseren Unterscheidung von Graph und Teilgraph wird hier wahlweise für den Graph auch die Bezeichnung „Gesamtgraph“ gewählt.
    

4. Üblicherweise ordnet man die Kanten in der "natürlichen" Reihenfolge der Knoten- bezeichnungen an; d.h. die Kanten werden nach den Bezeichnungen des Anfangs- knoten einer Kante sortiert, bei Symmetrie ist außerdem die Bezeichnung des Anfangsknotens kleiner als die des Endknotens einer Kante. Dabei ist es unerheblich, ob man als Bezeichnung der Knoten Buchstaben oder - wie der Autor - Zahlen verwendet. Durch die festgelegte Struktur werden bei den zu berechnenden Teilgraphen die nominal-skalierten Bezeichnungen der Knoten zu ordinal-skalierten Bezeichnungen.
    

5. In der Literatur findet man gelegentlich für den Teilgraph auch die Bezeichnung "Untergraph". Ein Teilgraph enthält zwar nicht alle Kanten aber alle Knoten des Graphs. Im Gegensatz dazu enthält ein Untergraph nur einen Teil der Knoten eines Graphs. Der Autor hat deshalb die Bezeichnung "Teilgraph " gewählt.

Anmerkungen zum Pseudoknoten

(12.06.2005)