什么叫二部图(二部图的子图也是二部图)

点击量:5044 来源:解译网 发表时间:2022-05-23 16:18作者:黄仲峰

蔡书玮网友提问:

什么叫二部图

优质答案:

朋友们好,许台法来为大家解答以上问题。什么叫二部图很多人还不知道,现在让我们一起来看看吧

什么叫二部图(二部图的子图也是二部图)

二部图又叫二分图,是图论中的一种特殊模型,是指顶点集可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

判断二部图的常见方法是染色法:对任意一未染色的顶点染色,判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色, 若已经染色且颜色和相邻顶点的颜色相同,则说明不是二部图,若颜色不同则继续判断,直到全部染上色。

以上就是顶点,子集,颜色的相关内容了,希望能帮到您。

声明

删帖请联系zhiyihome@qq.com;