Zeige, dass das Problem der Existenz eines Hamiltonkreises für gerichtete Graphen (Gibt es einen gerichteten Weg, der alle Knoten durchläuft und im gleichen Knoten anfängt und endet?) polynomial auf das Problem der Existenz eines Hamiltonkreises in ungerichteten Graphen transformierbar ist.

Hint 1
Man verwende im ungerichteten Graphen mehrere Kopien eines Knoten des gerichteten Graphen

Solutions
  • 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.

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Explain
  • Duration: 40min
  • Credits: 4
  • Difficulty: 0.7
  • Tags: hpi hamiltonian path
  • Note:
    HPI, 2014-06-26, Theoretische Informatik 2, Blatt 11, Aufgabe 3
  • Created By: adius
  • Created At:
    2014-07-23 12:59:24 UTC
  • Last Modified:
    2014-07-23 12:59:24 UTC