BipartiteGraphQ

BipartiteGraphQ[g]

如果图 g 是一个二分图，则产生 True；否则，产生 False.

更多信息

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

背景

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

范例

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

基本范例  (2)

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

不是所有图都是二部图：

范围  (6)

BipartiteGraphQ 可用于无向图：

有向图：

多重图：

混合图：

对于非图表达式，BipartiteGraphQ 给出 False：

BipartiteGraphQ 可用于大规模图：

属性和关系  (8)

一个二部图不含有自环：

任何树都是二部图：

含有不同的起始顶点和末端顶点的 PathGraph 是二部图：

每个面的边数都是偶数的任何平面图都是二部图：

一个顶点数为偶数的 CycleGraph 是二部图：

一个 CompleteGraph 是二部图：

一个 TuranGraph 是二部图：

当且仅当一个图不含有奇圈时，该图是二部图：

Wolfram Research (2010)，BipartiteGraphQ，Wolfram 语言函数，https://reference.wolfram.com/language/ref/BipartiteGraphQ.html.

文本

Wolfram Research (2010)，BipartiteGraphQ，Wolfram 语言函数，https://reference.wolfram.com/language/ref/BipartiteGraphQ.html.

CMS

Wolfram 语言. 2010. "BipartiteGraphQ." Wolfram 语言与系统参考资料中心. Wolfram Research. https://reference.wolfram.com/language/ref/BipartiteGraphQ.html.

APA

Wolfram 语言. (2010). BipartiteGraphQ. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/BipartiteGraphQ.html 年

BibTeX

@misc{reference.wolfram_2024_bipartitegraphq, author="Wolfram Research", title="{BipartiteGraphQ}", year="2010", howpublished="\url{https://reference.wolfram.com/language/ref/BipartiteGraphQ.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_bipartitegraphq, organization={Wolfram Research}, title={BipartiteGraphQ}, year={2010}, url={https://reference.wolfram.com/language/ref/BipartiteGraphQ.html}, note=[Accessed: 18-November-2024 ]}