首页 > 代码库 > 算法7-6:图论中的难题
算法7-6:图论中的难题
二部图
难度:★★
二分图是图论中的一种特殊模型,指顶点可以分成两个不相交的集使得在同一个集内的顶点不相邻(没有共同边)的图。
下图是一个二分图的例子,红点之间不会相邻,白点之间不会相邻。
判断图中是否存在环
难度:★★
通过深搜就可以解决了。
欧拉环
难度:★★
从一个顶点出发,所有的边都只经过一次,最后回到起点。判断一张图中是否存在这样的路径。
哈密尔顿环
难度:★★★★
从一个顶点出发,所有的顶点都经过一次,最后回到起点。判断一张图中是否存在这样的路径。
这个是一个经典的NP完全问题,目前还没有发现高效的解决办法。
同构问题
难度:★★★★★
两张图是否同构。所谓同构,就是忽略顶点上的数字,判断两张图是否是等价的。
下面这两张图就是等价的。
平面图
难度:★★★
将一张图放在平面中,判断这张图能否摆放在一个平面中使得所有的边都互不相交。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。