複数の開始ノードと複数の終了ノードを持つ有向グラフが与えられた場合、到達可能なすべてのエッジにアクセスするパスを形成する必要がありますが、1 回のパスでエッジ (または頂点) に複数回アクセスすることはできません。[これは、開始ノードから終了ノードに信号を送信することにより、ネットワーク内のすべての接続を電気的にテストすることですが、パスを一緒にショートさせることはできません。]
1 回のパスでエッジに再度アクセスすることはできないため、次のようにします。
- グラフのサイクルは無視しても問題ありません。
- 私が形成する各パスが他のパスをブロックすることを知っています。
- したがって、到達可能なすべてのエッジを 1 回のパスで訪問することはできないため、複数回のパスが必要です。
コンテキストから、パスの最小数は、任意の頂点に入るエッジの最大数になることがわかっています。特定のパスを終了すると、以前のパスでアクセスしたエッジに自由に再アクセスできますが、一度もアクセスしたことがないエッジは、最もアクセスしたいエッジです。
パスごとに「多くの」エッジにアクセスして、パスの合計数を減らすことができますが、厳密にパスの数を最小限に抑える必要はありません。
これを達成するためのアルゴリズムに関する提案はありますか? 私のグラフが方向付けられていることを除いて、ルート検査の問題に少し似ているように聞こえます。