弱平衡連接有向

我如何證明，如果一個平衡有向圖是弱連接，那麼它也強烈連接？（平衡有向圖意味着對於每個節點，它是不完整的，並且outdegree是相同的，並且弱連接意味着該圖的非定向版本被連接）。弱平衡連接有向

我能想到的，到目前爲止是：如果該圖是平衡的，這意味着它是向圈的聯合。所以如果我刪除任何週期，它將保持平衡。循環中的每個頂點都有一個邊緣進入它，一個邊緣引出它。

然後，我想我需要使用一些矛盾或歸納來證明圖形是強烈連接..這就是我困惑的地方。

2011-12-01 user1074557

您可能必須在http://cstheory.stackexchange.com更多的運氣 – Gian

作業中的問題是題外話在cstheory。你不想刪除週期，你想[合約]（http://en.wikipedia.org/wiki/Edge_contraction）它。 – Per

從http://cstheory.stackexchange.com/faq：「理論計算機科學 - 堆疊交換是在相關領域的理論計算機科學家和研究人員，我們歡迎在理論計算機科學（TCS）的研究層次的問題。」確定「研究水平」很難，但在任何特定領域，如果你不知道什麼是研究水平，什麼不是，那麼你有希望解決的任何問題都不是。或者你是個天才。 –

如果其中兩個週期相交，則它們形成一個強連通分量（因爲我們可以從週期中的任何頂點行進到它們的交點，然後繞過另一個週期，然後再回來完成數字-8 ）

由於圖形是弱連接的，我們知道所有循環相交，以便因此圖形是強烈地連接。

我想你可以充實我離開了手續。

來源

2011-12-01 01:47:57 hugomg

弱平衡連接有向

回答

相關問題