Es sei der gerichtete Graph ´G = ({a_1, a_2, …, a_n}, E)´ gegeben. Man konstruiere den ungerichteten Graphen

´G' =({a_(1,1), a_(1, 2), a_(1, 3), a_(2, 1), a_(2, 2), a_(2, 3), …, a_(n, 1), a_(n, 2), a_(n, 3)}, E')´ (jedem Knoten ´a_i´ von ´G´ werden drei Knoten ´a_(i,1), a_(i,2), a_(i,3)´ zugeordnet)

mit

´(a_(i,1), a_(i,2)), (a_(i,2), a_(i,3)) in E'´, ´(a_(i,3), a_(j,1)) in E'´ genau dann, wenn ´(a_i, a_j) in E´

(man bemerke, dass ´(a_i, a_j) in E´ und ´(a_j, a_i) in E´ zu ´(a_(i,3), a_(j,1)) in E'´ und ´(a_(j,3), a_(i,1)) in E'´ führt). Die Funktion, die ´G´ in ´G'´ überführt, ist offenbar polynomial, denn es werden ´3n´ Knoten, ´2n´ Kanten ´(a_(i,1), a_(i,2))´ und ´(a_(i,2), a_(i,3))´ und ´#(E)´ Kanten (zu jeder Kante aus ´E´ eine in ´E'´) konstruiert, d.h. dies geht in ´O(n + #(E))´ Schritten.

Es soll nun gezeigt werden, dass die Existenz eines gerichteten Hamiltonkreises in ´G´ die Existenz eines gerichteten Hamiltonkreises in ´G'´ impliziert. Es sei

´a_(i_1), a_(i_2), a_(i_3), …, a_(i_n)´ (1)

ein gerichteter Hamiltonkreis in ´G´, d. h. es gelten

´(a_(i_j), (a_i)_j, a_(i_(j+1))) in E´ für ´1 <= j < n´ und ´(a_(i_n), a_(i_1)) in E´. Dann gibt es nach Konstruktion in ´G'´ den Hamiltonkreis

´(a_(i_1,1), a_(i_1,2), a_(i_1,3), a_(i_2,1), a_(i_2,2), a_(i_2,3), a_(i_3,1), …, a_(i_n,1), a_(i_n,2), a_(i_n,3))´ (2)

Es sei nun umgekehrt ein Hamiltonkreis in ´G'´ existent. Dann hat dieser ohne Beschränkung der Allgemeinheit die Form aus (2) für ´n´ paarweise verschiedene Knoten ´a_(i_1), a_(i_2), …, a_(i_n)´. Dies ist wie folgt zu sehen: Ein jeder Knoten des Kreises kann als Anfang gewählt werden, also auch ´a_(i_1,1)´. Da ein Knoten ´a_(i,2)´ nur mit ´a_(i,1)´ und ´a_(i,3)´ verbunden ist und jeder dieser beiden Knoten nur einmal im Kreis vorkommen darf, muss ´a_(i,1)´, ´a_(i,2)´, ´a_(i,3)´ oder ´a_(i,3)´, ´a_(i,2)´, ´a_(i,1)´ als Teil des Kreises auftauchen. Im ersten Fall muss dann mit einem ´a_(j,1)´ fortgesetzt werden, im anderen mit einem ´a_(j,3)´. Folglich ist die Folge der zweiten Indices

´1,2,3,1,2,3,…,1,2,3´ oder ´3,2,1,3,2,1,…,3,2,1´.

Nach Konstruktion ist dann die Folge (1) ein Hamiltonkreis in ´G´.

Antwort zu anderer aber ähnlicher Frage:

(Zu einer Instanz ´G = (V, E)´ von Hamiltonkreis definieren wir einen Digraphen ´G^** := (V, E^**)´ durch

´E^** := uuu_(u,v in E) {(u,v),(v,u)}´

Besitzt ´G^**´ einen gerichteten Hamiltonkreis, so entspricht diesem natürlich auch ein Hamiltonkreis in ´G´. Umgekehrt gibt es zu jedem Hamiltonkreis in G aber auch einen korrespondierenden Hamiltonkreis in ´G^**´ (genau genommen sogar zwei), wenn man sich auf eine "Durchlaufrichtung" festlegt. Also gilt: ´G^**´ besitzt genau dann einen Hamiltonkreis, wenn G einen besitzt, damit hat man die gewünschte polynomielle Reduktion.)

Reduktion von gerichtet auf ungerichtet durch lokale Ersetztung:

--\   /--         --\                     /--
--- v ---    =>   --- v_in -- v -- v_out  ---
--/   \--         --/                     \--

gerichtet -> ungerichtet

Kann direkt übersetzt werden.

ungerichtet -> gerichtet

Entweder alle Knoten führen in ´v_in´ oder ´v_out´ => In zwei Richtungen duchlaufbar

=> Jeder Hamiltonkreis aus G' kann in einen Hamiltonkreis in ´G^**´ umgewandelt werden.

Polynomieller Algorithmus:

´AA v in V´ add ´v_1´ and ´v_2´ ´AA (a,b) in E´ ersetze durch ´(a_"out", b_"in")´ ´AA v in V´ add ´(v_"in", v)´, ´(v, v_"out")´

=> Bei endlich vielen Knoten polynomiell.