algorithm - 图中与源无关的路径

Question

几年前，我读到了一种算法：它标记了图的边，因此从源节点 X 到目标节点 Y 的路径始终是相同的标签序列，与您选择作为源 X 的节点无关。它是如何调用的？

（我不记得图形应该满足哪种条件）

这是一个示例（由我创建）：

• 顶点 1：红/黑/红
• 顶点 2：红/红/黑
• 顶点 3：红/红/黑/绿
• 顶点 4：红/黑/红/绿

从作为源的任何顶点开始，您使用上面的路径总是会到达目标顶点。

Answer 1

有道路着色问题：

问题： 给定一个有向图 G，给边上色，使得对于每个顶点，都有一组从其他顶点指向该顶点的指令。

（链接）

最近证明（Trahtman 2009）如果图是非周期性的并且每个顶点具有相同的出度，则存在这样的着色：

定理：每一个 均匀出度的有限强连通非周期有向图都有一个同步着色。

Trahtman 还为该问题提供了 O(n^3) 算法。

您应该搜索“道路着色问题算法”及其变体（例如，可以将条件放宽为非周期性，但我认为到目前为止这是一个未解决的问题）。