Das Finden des Fehlers in einer Reduzierung von Hamilton-Zyklus auf Hamilton-Zyklus in zweigliedrigen Graphen

  • Ich versuche, ein Problem für eine Klasse zu lösen, das folgendermaßen angegeben wird:

    Ein zweigeteilter Graph ist ein ungerichteter Graph, in dem jeder Zyklus gerade Länge hat. Wir versuchen zu zeigen, dass das Problem des Hamilton-Zyklus (ein Zyklus, der jeden Knoten genau einmal durchläuft) polynomial auf das Problem des Hamilton-Zyklus in zweiteiligen Graphen reduziert. Wir benötigen eine Funktion $ T: \ {\ text {graphs} \} \ an \ {\ text {zweigeteilte Graphen} \} $, sodass $ T $ in der Polynomialzeit und für jedes Diagramm berechnet werden kann $ G $, $ G $ hat einen Hamilton-Zyklus, wenn $ T (G) $ einen Hamilton-Zyklus hat. Sei $ T (G) $ der zweigeteilte Graph, der durch das Einfügen eines neuen Scheitelpunkts an jeder Kante erhalten wird. Was ist an dieser Transformation falsch?

    Ich denke, das Problem bei der Transformation besteht darin, dass Sie für $ T (G) $ einfügen müssen eine Kante zwischen jedem Paar von Scheitelpunkten und nicht nur einen neuen Scheitelpunkt an jeder Kante einfügen. Ich bin eigentlich ein bisschen verblüfft. Jeder Rat wäre sehr dankbar!

    28 April 2012
    Kaveh
2 answers
  • Das Problem ist, dass ein Hamilton-Zyklus alle alle Scheitelpunkte durchlaufen muss: Wenn der Zyklus im ursprünglichen Graphen keinen Rand $ e $ hat, dann teilen Sie den Scheitelpunkt, den Sie $ e teilen $ with wird nicht genommen, wenn Sie dieselbe Route wählen. Dies bedeutet, dass der resultierende Zyklus nicht Hamiltonian ist.

    27 April 2012
    Justin Standard
  • Ist es möglich, dass die Transformation korrekt aber sinnlos ist? Betrachten Sie Barettes Vermutung :

    Wenn ein planarer Graph zweigeteilt und kubisch ist, aber nur 2-verbunden ist, ist er möglicherweise kein Hamiltonianer, und es ist NP-vollständig, die Hamiltonizität für diese Graphen zu testen.

    (möglicherweise aus dem Kontext entfernt - siehe Wikipedia-Eintrag). Ist es möglich, dass Sie nur ein bekanntes NP-Komplettproblem auf ein anderes bekanntes NP-Komplettproblem reduzieren?

    27 April 2012
    Raphael