检查图是否单连通
我把《算法导论》第3版第22行22.3-13中单连通图的定义引用为有向图G=(V,E）是单连通的,如果G对所有顶点u至多包含一条从u到V的简单路,V属于V。我注意到图中的圈并不一定意味着图不是单连通的，因为包含圈的路径不被认为是简单路径。有向图中的一个简单圈可以由相应的边集唯一地表示。让我们考虑一个满足以下两个性质的有向图:
(1)它的DFS林中只有树边和后边，(2)图中表示每个简单圈的集合都是不相交的（即它们不共享任何边）。现在我的问题是：满足以上两个条件的有向图一定是单连通图吗？或者仅仅条件1就足以证明图是单连通的？我找不到任何反例
共有1个答案
我发现了一个反例。假设这个有向图G具有5个节点（0,1,2,3,4）和6条边（0,1）,（1,2）,（2,0）,（2,3）,（3,4）,（4,0）。如果我们从集合（3,4）中的任何节点开始DFS，我们将只有树和后边。显然，它满足条件1，但不满足2，并且它不是单连通图，因为从节点1到0有两条简单的路(1->2->3->4->0和1->2->0)。令人惊讶的是，如果我们从任何其他节点（即从0、1、2)开始DFS，其DFS森林将至少包含一个前沿。观察到该图中表示简单圈的边集是{（0,1）,（1,2）,（2,0）}和共享边（0,1）和（1,2）的{（0,1）,（1,2）,（2,3）,（3,4）,（4,0）}。通过从两个集合之间公共边内的任一节点中选择初始节点（即从0、1、2)获得的DFS林中得到至少一个前向边，而通过从剩余节点中的任一节点中选择初始节点（即从3、4)获得的DFS林中只得到树边和后向边。证明了条件1不是有向图单连通的充分条件。
-
问题内容： 我正在使用JAI并使用以下文件创建文件： 我在该行之前检查文件是否存在。但是，如何检查文件是.bmp还是.tiff还是图像文件？ 有人知道吗？ 问题答案： Image Magick项目具有识别图像的功能，并且有一个用于Image Magick的Java包装器，称为JMagick，我认为您可能需要考虑而不是重新发明轮子： http://www.jmagick.org 我一直在使用Imag
-
问题内容： 我正在通过jQuery $ .ajax加载图像路径，并在显示图像之前先检查它是否确实存在。我可以使用图像加载/就绪事件或类似的方法来确定文件路径有效吗？ 将.myimage设置为显示：无，我希望这样做 这样有可能吗？ 问题答案： 好吧，你可以绑定处理程序… 像这样， 好吧，您已经可以使用load-event 问题是如果禁用Javascript，图像将永远不会显示…
-
问题内容： 如何检查连接是否已在事务中？我正在使用Microsoft SQL Server数据库文件。 问题答案： 经过一番搜索，我发现了另一个“堆栈溢出”问题。事实证明，您不能在ADO.NET中嵌套事务。尝试时，您可能最终会启动两个不相关的事务，这会导致并行事务错误。 要查看连接当前是否在事务中，可以执行以下操作： 这将返回嵌套事务的数量。 请注意，您可以手动嵌套事务，而无需使用SqlTrans
-
问题内容： 如何使用Javascript检查互联网连接？这样，我可以有一些条件说“在生产过程中使用Google缓存的JQuery版本，在开发过程中使用该版本或本地版本，具体取决于Internet连接”。 问题答案： 针对您的特定情况的最佳选择可能是： 在您的结束标记之前： 鉴于您的问题集中在jQuery上，这可能是最简单的方法。 如果您想要一个更强大的解决方案，可以尝试： 阅读有关W3C在脱机We
-
我在网上搜索了很长一段时间，但我找不到我要找的东西。 如果我的设备已经连接到蓝牙设备（/在我启动应用程序之前），我如何通过我的应用程序发现。 我希望有类似bool BluetoothAdapter的东西。isPaired（）