algorithm - グラフ内のソースに依存しないパス

Question

数年前、あるアルゴリズムについて読みました。グラフのエッジにラベルを付けるため、ソースノード X から宛先ノード Y へのパスは、ソース X として選択したノードとは関係なく、常に同じ一連のラベルになります。どのように呼ばれますか?

(グラフがどのような条件を満たせばよいか思い出せません)

ここに例があります（私が作成しました）：

グラフの例

ソースとして任意の頂点から開始し、上記のパスを使用すると、常に目的の頂点に到達します。

score 3 · Accepted Answer

道路の着色問題があります。

問題: 有向グラフ G が与えられた場合、すべての頂点に対して、他のすべての頂点からその頂点に至る一連の命令が存在するように、エッジに色を付けます。

最近証明された ( Trahtman 2009 ) グラフが非周期的で、すべての頂点が同じ出次数を持つ場合、そのような色付けが存在します。

定理:出次数が 一様なすべての有限強連結非周期有向グラフには、同期色があります。

Trahtman は、この問題に対する O(n^3) アルゴリズムも提供しています。

「道路色付け問題アルゴリズム」とその変形を検索する必要があります (たとえば、条件を非周期性に緩和することはできますが、これはまだ未解決の問題だと思います)。

1 に答える 1