首页 > 代码库 > 算法7-6:图论中的难题

算法7-6:图论中的难题

二部图


难度:


二分图是图论中的一种特殊模型,指顶点可以分成两个不相交的集使得在同一个集内的顶点不相邻(没有共同边)的图。


下图是一个二分图的例子,红点之间不会相邻,白点之间不会相邻。



判断图中是否存在环


难度:


通过深搜就可以解决了。


欧拉环


难度:


从一个顶点出发,所有的边都只经过一次,最后回到起点。判断一张图中是否存在这样的路径。


哈密尔顿环


难度:


从一个顶点出发,所有的顶点都经过一次,最后回到起点。判断一张图中是否存在这样的路径。


这个是一个经典的NP完全问题,目前还没有发现高效的解决办法。


同构问题


难度:


两张图是否同构。所谓同构,就是忽略顶点上的数字,判断两张图是否是等价的。


下面这两张图就是等价的。



平面图


难度:★★★


将一张图放在平面中,判断这张图能否摆放在一个平面中使得所有的边都互不相交。