BipartiteGraphQ

BipartiteGraphQ[g]
如果图 g 是一个二分图,则产生 True;否则,产生 False.

更多信息更多信息

  • 如果一个图的顶点可以被分为两组,并且所有边都用来将这两组顶点两两连接的话,称之为二分图.

背景
背景

  • BipartiteGraphQ 检验指定的图是否为二分图. 如果一个图的顶点能够被分成两个不相交的独立集合(称作"分裂集合"),其中独立集合内的任意两个顶点均没有共同边,则该图为二分图. 也就是说,二分图的所有边在 内各有一个端点. 如果图为二分图,BipartiteGraphQ 返回 True,否则返回 False. 图为二分图的等价条件包括缺少奇数长度的环和色数最多为两个. 树(和森林)不含有环,因此自然是二分的. 二分图的家族包括顶点数为偶数的环图、网格图、超立方体图、骑士图和星形图(由于是树图自然为二分图).
  • 二分图是在模拟某些任务分配问题时自然产生的. 例如,已知工人的集合为,全时工作的集合为,构造一个由分裂集合 组成的二分图,如果一个工人能胜任某项工作,则用边将工人和工作连接. 求使得工人利用最大化的任务分配方式等价于求最大的独立边集合.
  • 图论中的许多基础性结果涉及二分图. 根据 König 线染色定理,二分图的边色数等于它们的最大度数. KönigEgerváry 定理表明,对于二分图,独立边集合的最大尺寸等于顶点覆盖的最小尺寸. Ore 缺陷公式指出,如果一个图有分裂集合 ,则该公共值等于 的大小减去 的所有子集 ,和 的大小减去 中与 中顶点相邻的顶点数的最大值. 在特殊情况下, 的子集的顶点数全部小于 中它的近邻数,Ore 缺陷公式则成为 Hall 结婚定理,后者指出,这个条件等价于入射到 的各顶点的一组独立的边集合的存在性.
  • CompleteGraph[{m,n}] 返回在分裂集合 上尺寸分别为 mn 的完全二分图,它在 中的每个顶点都与 中的每个顶点相连.

范例范例打开所有单元关闭所有单元

基本范例  (2)基本范例  (2)

检查一个图是否是二部图:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=

不是所有图都是二部图:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=
2010年引入
(8.0)
Translate this page: