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

Dies kann dadurch geschehen, dass ein beliebiger Knoten ("Ursprungsknoten") verdoppelt wird, indem der neu eingefügte Pseudoknoten dieselben Kantenausprägungen ("Kosten") zu den übrigen Knoten des Graphs erhält wie der Ursprungsknoten. Die Kosten der Kante  zwischen dem Ursprungsknoten und dem Pseudoknoten ("Pseudokante") sind minimal zu setzen (i.d.R. = 0).

Der Autor bedankt sich ausdrücklich bei Andreas Füllbeck, der den Nachweis geführt hat, dass es ggf. nicht ausreicht, den Wert der Pseudokante auf  "0" zu setzen. Unter Umständen ist es erforderlich, als Minimalsetzung einen hinreichend großen negativen Wert anzunehmen, der sicherstellt, dass die Pseudokante im erweiterten minimalen Gesamtgraphen enthalten ist.

Nachdem der minimale erweiterte Gesamtgraph ermittelt ist, wird der Pseudoknoten wieder eliminiert und der Wert der Pseudokante von der Summe des Wertes des erweiterten minimalen Gesamtgraphen wieder abgezogen.  

(26.06.2005)