二分图
有两个顶点集且同一集合的顶点都不邻接的图
条目
历史版本
二分图（英文：bipartite graph[1]）又称二部图，是一类特殊的图。[12]其定义为：如果一个图的顶点能分成两个集合V1和V2，并使得同一集合中的任何两个顶点都不邻接，则称此图为二分图。[13]
图论发展至今已有200多年的历史，它最早起源于哥尼斯堡七桥问题。1736年，瑞士数学家欧拉（Euler）在《关于位置几何问题的解法》的论文中，对哥尼斯堡七桥问题进行了论述，并将其形象地转化为一笔画问题，[14][15]标志着图论的正式诞生。[4]1878年，英国数学家西尔维斯特（Sylvester）在《自然》杂志上发表的著作《化学与代数》中首次使用了“图”的数学术语。[5][16]1914年，匈牙利数学家柯尼希（Koenig）在著作《关于集合的一般理论和图论中的一个问题》中引入了二分图的概念，并称它为“偶回路图”，后改称为二部图。1935年，英国数学家霍尔（Hall）在其论文《论子集的代表元》 中提出了著名的霍尔定理，[3]给出了二分图存在完美匹配的充要条件。[17]1957年，法国数学家贝尔热（C.Berge）提出了图存在最大匹配的充要条件，[6]它可用于解决二分图中的最大匹配问题。[18]
二分图有一些基本性质，如所有回路长度均为偶数。[19]二分图可根据节点基数的大小进行分类，[20]它与子图[21]、完全图[22]等概念密切相关。二分图的运算有匹配[23]、覆盖[24]、检验二分性[1]等，其中匹配可以通过匈牙利算法来求解。[25]图的每边最多只有两个顶点，如果推广至任意个，可得到超图的概念，二分图与超图之间可相互确定。[26][27]此外，二分图在现实世界中具有广泛的应用价值，如生物学中，融合多生物数据的二分图聚类集成方法，能有效地处理蛋白质功能重叠问题。[7]