Zerlegung eines Gesamtgraphen in zwei gleichstrukturierte Teilgraphen :

Vorbemerkung:
Das interessierende Merkmal eines Graphen stellt sich als seine Funktion dar, nämlich als Summe der Ausprägungen dieses Merkmals seiner Kanten. Die Kanten selbst bestimmen nur eine wohldefinierte Anzahl von Graphen. Bei gerichteten Kanten gibt es genau n Graphen, nämlich beginnend von jedem Knoten je ein Graph in eine Richtung, bei ungerichteten (=symmetrischen) Kanten ergeben sich 2n Graphen, dabei wiederum beginnend von jedem  Knoten je ein Graph in die eine und in die andere Richtung.     

Jeder beliebige Gesamtgraph mit:

• n Kanten

• n Knoten

• alle Knoten vom Knotengrad 2

• 1 Komponente

läßt sich zerlegen in zwei Teilgraphen mit:

• n / 2 Kanten

• n Knoten

• alle Knoten vom Knotengrad 1

• n / 2 Komponenten.

Ein Gesamtgraph, den  zwei o.a. Teilgraphen bilden, ist immer eindeutig. 
Bei Symmetrie wird der Gesamtgraph oder der symmetrische "Gegen-"Gesamtgraph gebildet.

Folgerung:
Die Zerlegung eines Gesamtgraphen und spätere Zusammenführung läßt sich somit ohne Informationsverlust durchführen.

Zusammensetzen der Teilgraphen zu einem Gesamtgraphen:

Gegeben seien:

1. a + b = X  
2. c + d = Y
3. Y < X
4. min(a,b) <= c,d

daraus folgt:

a) Y / 2 < X / 2 (trivial)
b) min (a,b) <= X / 2 
c) max(a,b) >= X / 2 
d) min (c,d) <= Y / 2 < X / 2 
e) max(c,d) < max(a,b)

Übertragung auf das Problem der Teilgraphen:
(gemeint sind hier immer die Ausprägungen: Länge, Kosten u.ä.)

Gegeben seien die Teilgraphen a und b, die den Gesamtgraphen X bilden. 
Daraus folgt, dass der kleinere der beiden Teilgraphen kleiner oder höchstens gleich der Hälfte des Gesamtgraphen X ist. Außerdem ist der größere der beiden Teilgraphen größer oder gleich der Hälfte des Gesamtgraphen X.

Gesucht wird ein Gesamtgraph Y mit den Teilgraphen c und d, der kleiner ist als der Gesamtgraph X. 
Dann ist die Hälfte vom Gesamtgraphen Y kleiner als die Hälfte vom Gesamtgraphen X.
Außerdem muss der kleinere der beiden Teilgraphen (c,d) kleiner oder gleich der Hälfte des Gesamtgraphen Y und gleichzeitig kleiner sein als die Hälfte vom Gesamtgraphen x.

Weiter muss der größere der beiden Teilgraphen (c,d) kleiner sein als der größere Teilgraph (a,b), unter der Voraussetzung, dass der kleinere der Teilgraphen (a,b) kleiner ist als jeder der beiden Teilgraphen (c,d). Dieses ist immer dann der Fall, wenn der Gesamtgraph X den kleinsten aller Teilgraphen enthält. 

Folgerung:
Wird nun im ersten Schritt der kleinste Teilgraph mit seinem kleinsten Komplement-Teilgraph gesucht (und gefunden), dann  liegen alle Teilgraphen eines möglichen kleineren Gesamtgraphen zwischen diesen ersten beiden gefundenen Teilgraphen. Alle über dem im ersten Schritt gefundenen kleinsten Komplement-Teilgraphen liegenden Teilgraphen scheiden für die weiteren Berechnungen aus. Weiter muss der kleinere der möglichen Teilgraphen kleiner sein als die Hälfte des ersten gefundenen Gesamtgraphen.