如果圖形具有交叉邊緣，是否單獨連接

當我看「算法3簡介」時，遇到下面的這個問題。如果圖形具有交叉邊緣，是否單獨連接

22.3-13 * 有向圖G是單連通的，如果u→v意味着G對於所有頂點V至多包含一個從u到v的簡單路徑。給出一個有效的算法來確定有向圖是否單獨連接。

一些這樣的答案「從每個頂點運行DFS一次。該圖是單獨連接的，當且僅當沒有前邊緣，也沒有交叉的邊緣」

但我懷疑這種情況。例如，如果圖（A-> D，D-> E，E-> A，B-> C，C-> A）的所有邊從D開始，因此C-> A是交叉邊，但是I認爲這張圖是單獨連接的。對不起，我無法上傳圖片，因爲stackoverflow的權限。

來源

2013-05-20 Zinan

你的示例圖有一個圓圈，它沒有辦法單獨連接。 – kutschkem

你可以包含一個鏈接到img上傳網站 –

@BartlomiejLewandowski我設計了這個圖表，所以它不在網站上。 – Zinan

圖中可能存在交叉邊，也可能有周期，圖將單連接（SC）。如果我們有前沿，很明顯我們有2條路徑到達目的地V. 但在這種情況下如果我們有交叉邊緣圖不是SC :: 假設ab或zb是我們在圖中的交叉邊，如果有是a和z圖之間的路徑不是SC，如果我們沒有相同的路徑，那絕對是SC。如果ab（或zb）是我們的交叉邊，那麼不應該有a和z之間的路徑。

來源

2014-02-21 14:55:23 David

如果圖形具有交叉邊緣，是否單獨連接

回答

相關問題