首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >检测二部图

问检测二部图
EN

Stack Overflow用户
提问于 2013-03-31 08:48:50
回答 1查看 445关注 0票数 1

我只是在创建一个检测二部图的算法,但我想到了一些我不确定是否属于二部图的图,尽管我的算法说它是二部图。

该图如下所示

代码语言:javascript
复制
(A)--(B)

(C)

因此,这里有3个节点,但只有A和B之间有1条边。这真的是二分的吗?

EN

回答 1

Stack Overflow用户

发布于 2013-04-06 03:44:33

是的,你的样例图确实是二分的。

例如,请看Wikipedia article,它在开场白中表示...

在图论的数学领域中,二部图(或二重图)是这样的图,其顶点可以被分成两个不相交的集合U和V,使得每条边都将U中的一个顶点连接到V中的一个顶点,即U和V都是独立的集合。等价地,二部图是不包含任何奇数长度圈的图。

有两种方法可以划分这个图("{A,C},{B}“或"{B,C},{A}"),它们将满足二部图所需的条件。

二部图不要求是连通图。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/15725189

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档