Algorithme pour les nœuds graphiques match

Question

Étant donné un graphe orienté, ce qui est un algorithme je peux utiliser pour trouver un sous-ensemble aléatoire de ses bords de sorte que chaque noeud a exactement un entrant et sortant exactement un bord?

Par exemple, cela pourrait être le graphique que je me donne:

Et ce serait un graphique de sortie valide:

Ceci est valable parce que:

• Il contient tous les noeuds sur le graphique d'entrée
• Tous ses bords sont également sur le graphique d'entrée
• Chaque noeud a exactement un bord et laissant un bord à venir (et qui ne peut être le même bord, pas de boucles sont autorisés, chaque nœud doit se connecter à au moins un autre noeud).

S'il n'y a pas de solution possible qui doit être détectée.

Y at-il un algorithme efficace pour résoudre ce problème?

Merci!

Answer 1

Il est un problème cycles nœud de couverture. Il peut être résolu que maximum dans appariements bipartites graphiques .

En bref:

1. Séparer chaque nœud en deux, chacun dans une partition d'un graphe, de sorte que tous bords vont de la partition P1 à P2 partition. Dans l'échantillon, les noeuds A et D se transforme en noeuds A1, D1 partition P1 et A2, D2 dans P2. Bord A-D va se transformer en A1-D2 et D-A -. D1-A2
2. Ensuite, trouver une correspondance maximale, il existe des algorithmes.
3. Puis fusionner les nœuds en arrière, et vous avez une couverture de cycle.

Answer 2

Vous essayez de décomposer un graphique en un ensemble de cycles.

des points Ce lien vous à l'algorithme de Tarjan pour trouver des cycles dans un graphique.

Après cela, vous aurez besoin d'une stratégie de recherche (certains choix de cycles ne peuvent pas conduire à une solution compte tenu de vos contraintes).