圖中的源獨立路徑

幾年前，我讀到一個算法：它標記圖的邊，所以從源節點X到目標節點Y的路徑始終是相同的標籤序列，與您選擇爲源X的哪個節點無關。它怎麼叫？圖中的源獨立路徑

（我不記得是哪一種情況應該由圖形滿足）

下面的例子（由我創建）：

Example graph

從任何頂點作爲源使用上面的路徑始終到達目標頂點。

從2到3的邊緣也可以染成黑色。並且頂點3規則變成：紅色/紅色/黑色/黑色 – user1365836 2012-07-31 14:17:32

是否有其他條件？你總是可以用紅色標註所有內容！ – Shahbaz 2012-07-31 14:30:06

我認爲你不能爲兩個邊緣分配相同的顏色*從相同的頂點退出*如果不是路徑是模棱兩可的！ – user1365836 2012-07-31 14:39:03

有道路着色問題：

問題：給定有向圖G中，顏色的邊緣，使得對於每一個頂點，存在導致該頂點，從每一個的一組指令其他頂點。

（link）

這是最近證明（Trahtman 2009），如果圖是非週期性和每個頂點具有相同的出度，這樣的着色存在：

定理：每有限強連接不定期有向圖均勻出度有同步着色。

Trahtman也給出了一個O（n^3）算法的問題。

您應該搜索「道路着色問題算法」及其變體（例如，可以將條件放鬆到非週期性，但我認爲這是迄今爲止的一個公開問題）。

2012-07-31 15:06:14 Haile

看起來是2007年，而不是2009年。 – user1365836 2012-07-31 15:20:24

它於2009年發佈：http://www.springerlink.com/content/842608t361mg2k12/?MUD=MP – Haile 2012-07-31 15:24:55

回答