弱平衡连接有向

我如何证明，如果一个平衡有向图是弱连接，那么它也强烈连接？（平衡有向图意味着对于每个节点，它是不完整的，并且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

弱平衡连接有向

回答

相关问题