algorithme pour circuit de facteur chinois dans un graphe bidirected

Question

Je recherche un algorithme qui trouve un circuit de facteur chinois dans un graphe bidirected. Le graphique bidirected ici n'est pas le graphique orienté symétrique, mais le graphique introduit par Edmonds & Johnson en 1970.

J'ai trouvé peu de papiers qui ont résolu le même problème basé sur un papier publié par Harold N Gabow en 1983, mais il n'y avait pas formalisé algorithme; ils ont juste mentionné que le problème peut être réduit/lié au b-matching parfait, au flux de réseau bidirected ... et ainsi de suite, que je ne peux pas comprendre jusqu'ici. Si quelqu'un connaît le concept et l'algorithme pour cela, s'il vous plaît donnez-moi quelques conseils.

Answer 1

La plupart des algorithmes permettant de trouver un circuit de facteur chinois transfèrent le problème à la recherche d'un circuit de Hamilton. Si cela n'est pas possible, le graphique est étendu de sorte qu'il est possible de trouver un circuit de Hamilton.

Dans un graphe non orienté, un circuit de Hamilton est possible lorsque tous les noeuds ont un degré pair. Si ce n'est pas le cas, les nœuds avec degré impair doivent être étendus avec un bord supplémentaire. Cela entraîne un problème d'appariement. J'espère que cela aidera votre problème de graphes bidirected. Peut-être que je peux vous aider plus loin si vous précisez votre question

Answer 2

Vous pouvez consulter ce document pour trouver une solution au chinese postman problem.