Chemin minimal - toutes les arêtes au moins une fois

Question

J'ai dirigé un graphe avec beaucoup de cycles, probablement fortement connectés, et j'ai besoin d'un cycle minimal. Je veux dire que j'ai besoin de cycle, qui est le cycle le plus court du graphique, et chaque bord est couvert au moins une fois.

J'ai recherché un algorithme ou un arrière-plan théorique, mais la seule chose que j'ai trouvée est l'algorithme du postier chinois. Mais cette solution n'est pas pour le graphe orienté.

Quelqu'un peut-il m'aider? Merci

Modifier >> Tous les bords de ce graphique ont le même coût - par exemple 1

Answer 1

Jetez un oeil à ce document - Directed Chinese Postman Problem. C'est la classification de problème correcte si (en supposant qu'il n'y a plus de restrictions).

Si vous êtes en train de lire la théorie, faites une bonne lecture au this page, qui est tiré du Algorithms Design Manual.

citation clé (la deuxième moitié de la version dirigée):

L'excursion optimale de facteur peut être construit en ajoutant les arêtes appropriées au graphe G de manière à la rendre Eulérienne. Plus précisément, nous trouvons le chemin le plus court entre chaque paire de sommets de degré impair dans G. Ajouter un chemin entre deux sommets de degré impair dans G les transforme tous deux en degré pair, nous rapprochant ainsi d'un graphe eulérien. Trouver le meilleur ensemble de chemins les plus courts à ajouter à G revient à identifier une correspondance parfaite de poids minimum dans un graphique sur les sommets de degré impair, où le poids de bord (i, j) est la longueur du chemin le plus court de i à j. Pour les graphes orientés, ceci peut être résolu en utilisant la correspondance bipartite, où les sommets sont partitionnés selon qu'ils ont plus d'arêtes entrantes ou sortantes. Une fois que le graphique est eulérien, le cycle réel peut être extrait en temps linéaire en utilisant la procédure décrite ci-dessus.

Answer 2

Je doute qu'il est optimal, mais vous pouvez faire une recherche basée sur la file d'attente en supposant que le graphique est assuré d'avoir un cycle. Chaque entrée de file d'attente contient une liste de noeuds représentant les chemins. Lorsque vous retirez un élément de la file d'attente, ajoutez toutes les étapes suivantes à la file d'attente, en vous assurant de ne pas visiter à nouveau les noeuds. Si le dernier nœud est le même que le premier nœud, vous avez trouvé le cycle minimum.

Answer 3

ce que vous cherchez est appelé "chemin eulérien". Vous pouvez le google pour trouver assez d'informations, les bases sont here Et à propos de l'algorithme, il est un algorithme appelé algorithme de Fleury, google pour elle ou regarder here

Answer 4

Le cas particulier dans lequel le réseau est entièrement constitué de bords dirigés peuvent être résolu en temps polynomial. Je pense que le document original est Matching, Euler tours and the Chinese postman (1973) - une description claire de l'algorithme pour le problème de graphe orienté commence à la page 115 (page 28 du pdf):

Lorsque toutes les arêtes d'un graphe connexe sont dirigées et graphique est symétrique, il existe un algorithme particulièrement simple et attrayante pour spécifiant une tournée Euler ...

L'algorithme pour trouver une tournée d'Euler dans une scène, symétrique, graphe connexe G est d'abord trouver un couvrant arborescences de G. Ensuite, à , n'importe quel nœud n, à l'exception de la racine r de l'arborescence, spécifie n'importe quel ordre pour les bords dirigés un chemin de n tant que le bord de l'arborescence est le dernier dans la commande.Pour la racine r, spécifiez n'importe quel ordre pour les bords dirigés à l'écart de r.

Cet algorithme a été utilisé par van Aardenne-Ehrenfest et de Bruin pour énumérer tous les tours d'Euler dans un certain graphe orienté [1].