Partitionner un graphique en cycles nœud-disjoint

Problème connexe: le théorème de Veblen déclare qu '"un graphique admet une décomposition de cycle si et seulement s'il est pair". Les cycles sont disjoints sur les bords, mais pas nécessairement disjoints sur les nœuds. Autrement dit, "L'ensemble des bords d'un graphe peut être partitionné en cycles si et seulement si chaque sommet a un degré pair."

Mon problème: je me demande si quelqu'un a étudié la partition d'un graphique en cycles nœud-disjoints. Autrement dit, partitionnez les sommets d'un graphe en , et chaque sous-graphe induit par est hamiltonien. $V$ $G$ $V_1, V_2, \cdots, V_k$ $V_i$

Est-ce NP-difficile ou facile?

Problème plus connexe: la partition en triangle est NP-complète. (Page 68 de "Ordinateurs et intractabilité")

Merci pour vos conseils à l'avance. ^^

cc.complexity-theory graph-theory co.combinatorics Peng Zhang
la source

Il y a une réduction facile à l'appariement. Exercice bien connu en algorithmes.

Chandra Chekuri

Est-ce votre problème: en.wikipedia.org/wiki/Vertex_cycle_cover ?

Thomas Ahle

@ThomasAhle Merci, je n'étais pas au courant de cette page wiki. Il est appelé «couverture de cycle disjoint» mentionné dans cette page wiki.

Peng Zhang

Une partition en cycles vertex-disjoints est la même chose qu'un sous-graphe 2-régulier, plus communément appelé facteur 2. Il peut être trouvé (s'il existe) en temps polynomial par un algorithme basé sur l'appariement. ~~Voir par exemple ce lien .~~

ETA Nov 2013: Il semble d'après les commentaires ci-dessous que la réduction de la source liée ci-dessus est erronée. Toutefois, l'affirmation selon laquelle le problème peut être réduit à une correspondance parfaite reste correcte. La réduction correcte se trouve dans WT Tutte (1954), "A short proof of the factor theorem for finite graphs", Canadian J. Math. 6: 347–352 .

Remplacez chaque sommet par le degré par un graphe bipartite complet , et représentez chaque arête du graphe d'origine par une arête d'un sommet de à un sommet de (sur le côté de la bipartition avec sommets) de telle sorte que chaque sommet de de ce côté de la bipartition ait exactement un de ces bords qui lui est incident. $v$ $d$ $G_v=K_{d,\,d-2}$ $uv$ $G_u$ $G_v$ $d$ $G_v$

Ensuite, une correspondance parfaite dans le graphique modifié doit faire correspondre les sommets de leur côté de la bipartition de avec sur les sommets de l'autre côté, laissant exactement deux sommets libres qui doivent être mis en correspondance avec leur voisins dans d'autres sous-graphes . De cette façon, les correspondances parfaites du graphique modifié correspondent 1 pour 1 aux couvertures de cycle du graphique d'origine. $d-2$ $G_v$ $d-2$ $d$ $G_u$

David Eppstein
la source

Je ne comprends pas. Toutes les mentions que j'ai trouvées sur cet algorithme commencent par calculer une tournée euler. Cependant, il y a beaucoup de graphiques qui peuvent être parcourus à vélo sans avoir une tournée euler. Est-ce également en P si nous n'exigeons pas que toutes les arêtes soient utilisées?

Thomas Ahle

Avez-vous lu l'article auquel j'ai lié? Je ne vois aucune mention des tournées d'Euler là-bas.

David Eppstein

C'est juste un peu difficile à comprendre. Lorsque vous construisez en changeant chaque arête en arête de en ( ) comment savez-vous quelle extrémité mettre en et laquelle mettre en ? Le papier semble "juste prendre le second", mais ce n'est pas un graphique dirigé ..

E^{'}

$E'$

(i, j)

$(i,j)$

V

$V$

V^{'}

$V'$

(i, j^{'})

$(i,j')$

V

$V$

V^{'}

$V'$

Thomas Ahle

Je veux dire, je pourrais également convertir chaque bord non orienté en un bord dirigé dans chaque direction, mais la correspondance pourrait alors me donner beaucoup de cycles de "longueur 2", non?

Thomas Ahle

@ThomasAhle a apparemment mélangé les termes; ce que je voulais dire, c'est un graphe couvrant régulier , alias facteur

k

$k$

k

$k$

Manfred Weis

Partitionner un graphique en cycles nœud-disjoint

Réponses: