私は多くのサイクルでグラフを指示しましたが、おそらく強く接続されており、そこから最小のサイクルを取得する必要があります。つまり、グラフで最も短いサイクルであるサイクルを取得する必要があり、すべてのエッジが少なくとも1回はカバーされます。
私はいくつかのアルゴリズムまたはいくつかの理論的背景を探していましたが、私が見つけたのは中国の郵便配達アルゴリズムだけです。ただし、このソリューションは有向グラフ用ではありません。
誰か助けてもらえますか？ありがとう
編集>>そのグラフのすべてのエッジのコストは同じです-たとえば1
この論文を見てください-中国人郵便配達問題を指示しました。ただし、これは正しい問題分類です（これ以上の制限がないと仮定します）。
理論を読んでいるだけの場合は、アルゴリズム設計マニュアルのこのページをよく読んでください。
キークォート（ダイレクトバージョンの後半）：
グラフGに適切なエッジを追加してオイラーにすることにより、最適な郵便配達ツアーを構築できます。具体的には、Gの奇数次数の頂点の各ペア間の最短経路を見つけます。Gの2つの奇数次数の頂点間に経路を追加すると、両方が偶数次数になり、オイラーグラフに近づきます。Gに追加する最短経路の最適なセットを見つけることは、奇数次数の頂点のグラフで最小重みの完全一致を特定することになります。ここで、エッジの重み（i、j）は、iからj。有向グラフの場合、これは2部マッチングを使用して解決できます。この場合、頂点は、より多くの入力エッジまたは出力エッジがあるかどうかに応じて分割されます。グラフがオイラーになると、上記の手順を使用して実際のサイクルを線形時間で抽出できます。
最適かどうかはわかりませんが、グラフにサイクルがあることが保証されていると仮定して、キューベースの検索を実行できます。各キューエントリには、パスを表すノードのリストが含まれます。要素をキューから削除するときは、可能なすべての次のステップをキューに追加して、ノードに再度アクセスしないようにします。最後のノードが最初のノードと同じである場合、最小サイクルが見つかりました。
ネットワークが完全に有向エッジで構成されている特殊なケースは、多項式時間で解くことができます。元の論文は、マッチング、オイラーツアー、中国の郵便配達員（1973）だと思います。有向グラフ問題のアルゴリズムの明確な説明は115ページ（PDFの28ページ）から始まります。
接続されたグラフのすべてのエッジが方向付けられ、グラフが対称である場合、オイラーツアーを指定するための特に単純で魅力的なアルゴリズムがあります...
有向対称連結グラフGでオイラーツアーを見つけるアルゴリズムは、最初にGのスパンアーボレッセンスを見つけることです。次に、アーボレッセンスのルートrを除く任意のノードnで、から離れる方向に向けられたエッジの順序を指定します。 nアーボレッセンスのエッジが順序付けの最後である限り。ルートrには、rから離れる方向に向けられたエッジの順序を指定します。
このアルゴリズムは、vanAardenne-EhrenfestとdeBruinによって、すべてのオイラーツアーを特定の有向グラフに列挙するために使用されました[1]。