如何檢查給定的無向圖是否存在傳遞方向？

如果一個無向圖的邊可以以這樣一種方式定向，即如果（x，y）和（y，z）是所得有向圖中的兩條邊，那麼存在一條邊（x，z ）在結果有向圖中。如何檢查給定的無向圖是否存在傳遞方向？

我正在使用真正的食物網絡，我需要檢查一個密集的無向圖（模擬食物網中的競爭）是否具有傳遞方向。無向圖被表示爲Java中的鄰接矩陣。

編輯：

我們可以在this way定向邊緣。所以，這個圖有一個傳遞的方向。

我回答了，但後來我發現你在討論中使用「無向圖」和「有向圖」。這是一個錯字，還是什麼？ – nbro

在定向無向圖的邊之後，得到的圖是有向圖。 –

也許我錯過了一些東西。正如你所定義的「有一個TO」，我相信原始無向圖中的任何路徑都必須位於一個完整的子圖中。因此，每個連接的組件必須是原始圖形的完整圖形才能具有TO。這很容易檢查。如果我有這個錯誤，那麼帶有TO的不完整圖的例子會很有幫助。 – Gene

你在看什麼是comparability graph。這類圖也被稱爲「可傳遞定向圖」，但這不是最常見的名稱。對於這一類的認可，請看graphclasses website。

2016-07-03 17:45:54

是的，我已閱讀可比性圖表。你知道這個簡單的實現，這將有幫助嗎？ –

你可以看看Golumbic的書「算法圖論和完美圖」第5章，它致力於比較圖。 –

謝謝，我會研究它。 –

回答