完全二分图

完全二分图是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。

完全二分图
一个完全二分图m=3 n =2
顶点	n+m
边	mn
自同构群	2m!n!如果m=n，否则m!n!

定义

完全二分图${\displaystyle G:=(V_{1}+V_{2},E)}$是一个二分图，使得对于任何两个顶点${\displaystyle v_{1}\in V_{1}}$和${\displaystyle v_{2}\in V_{2}}$，${\displaystyle v_{1}v_{2}}$都是${\displaystyle G}$中的一条边。${\displaystyle \left|V_{1}\right|=m}$且${\displaystyle \left|V_{2}\right|=n}$的完全二分图记为${\displaystyle K_{m,n}}$。

例子

• K_1,3
• K_2,3
• K_3,3

性质

• 平面图不能含有子图${\displaystyle K_{3,3}}$；外平面图（英语：Outerplanar graph）不能含有子图${\displaystyle K_{3,2}}$（这些是必要条件而不是充分条件）。
• 完全二分图${\displaystyle K_{m,n}}$的顶点覆盖数为${\displaystyle \min \lbrace m,n\rbrace }$，边覆盖数为${\displaystyle \max \lbrace m,n\rbrace }$。
• 完全二分图${\displaystyle K_{m,n}}$具有大小为${\displaystyle \max \lbrace m,n\rbrace }$的最大独立集（英语：Maximum independent set）。
• 完全二分图${\displaystyle K_{m,n}}$具有大小为${\displaystyle \min \lbrace m,n\rbrace }$的最大匹配（英语：Maximum cardinality matching）。
• 完全二分图${\displaystyle K_{n,n}}$具有正则的n-边染色（英语：Edge coloring）。
• 完全二分图${\displaystyle K_{m,n}}$有m^n-1 n^m-1个不同的生成树。

参见

• 圈图（英语：Circle graph）
• 道路 (图论)
• 完全图
• 零图
• 二分图
• 三間小屋問題