Partitionieren Sie einen Graphen in knotendisjunkte Zyklen

Zugehöriges Problem: Der Satz von Veblen besagt, dass "ein Graph eine Zykluszerlegung nur dann zulässt, wenn sie gerade ist". Die Zyklen sind kantendisjunkt, aber nicht notwendigerweise knotendisjunkt. Anders ausgedrückt: "Die Kantenmenge eines Graphen kann genau dann in Zyklen unterteilt werden, wenn jeder Scheitelpunkt einen geraden Grad hat."

Mein Problem: Ich frage mich, ob jemand die Partition eines Graphen in knotendisjunkte Zyklen untersucht hat. Das heißt, die Scheitelpunkte eines Graphen G werden in V 1 , V 2 , ⋯ , V k unterteilt , und jeder durch V i induzierte Untergraph ist hamiltonisch.$V$$G$$V_1, V_2, \cdots, V_k$$V_i$

Ist es NP-schwer oder einfach?

Weiteres Problem: Die Teilung in Dreiecke ist NP-vollständig. (Seite 68 von "Computer und Störanfälligkeit")

Vielen Dank für Ihre Beratung im Voraus. ^^

Eine Unterteilung in vertex-disjunkte Zyklen ist dasselbe wie ein 2-regulärer Subgraph, der üblicherweise als 2-Faktor bezeichnet wird. Es kann (falls vorhanden) in der Polynomzeit durch einen Algorithmus gefunden werden, der auf Matching basiert. ZB siehe diesen Link .

ETA Nov 2013: Aus den nachstehenden Kommentaren geht hervor, dass die Reduzierung von der oben verlinkten Quelle falsch ist. Die Aussage, dass das Problem auf eine perfekte Übereinstimmung reduziert werden kann, bleibt jedoch richtig. Die korrekte Reduktion findet sich in WT Tutte (1954), "Ein kurzer Beweis des Faktorsatzes für endliche Graphen", Kanadier J. Math. 6: 347–352 .

Ersetze jeden Vertex mit Grad d durch einen vollständigen zweigliedrigen Graphen G v = K d $v$$d$ und repräsentieren jede Kanteuvdes ursprünglichen Graphen durch eine Kante von einem Scheitelpunkt von G u bis zu einem Scheitelpunkt von G v (auf der Seite der Bipartition mitdScheitelpunkten) in der Weise, dass jeder Scheitelpunkt von G v Auf dieser Seite der Bipartition tritt genau eine solche Kante auf.$G_v=K_{d,\,d-2}$$uv$$G_u$$G_v$$d$$G_v$

Dann muss eine perfekte Übereinstimmung im modifizierten Graphen die Eckpunkte auf ihrer Seite der Bipartition von G v mit d - 2 von den d Eckpunkten auf der anderen Seite abgleichen , wobei genau zwei freie Eckpunkte übrig bleiben, mit denen abgeglichen werden müssen ihre Nachbarn in anderen Untergraphen G u . Auf diese Weise entsprechen die perfekten Übereinstimmungen des modifizierten Diagramms 1-zu-1 den Zyklusabdeckungen des ursprünglichen Diagramms.$d-2$$G_v$$d-2$$d$$G_u$