二分图(英文: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] 定义
二分图:设和是图的顶点子集,使,且的每一条边的一个端点在中,另一个端点在中,则称为二分图,记作。[13]