完全二分图

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

定义

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

例子

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

性质

• 平面图不能含有子图$K_{3,3}$；Template:Le不能含有子图$K_{3,2}$（这些是必要条件而不是充分条件）。
• 完全二分图$K_{m,n}$的顶点覆盖数为$\min \{m,n\}$，边覆盖数为$\max \{m,n\}$。
• 完全二分图$K_{m,n}$具有大小为$\max \{m,n\}$的Template:Le。
• 完全二分图$K_{m,n}$具有大小为$\min \{m,n\}$的Template:Le。
• 完全二分图$K_{n,n}$具有正则的Template:Le。
• 完全二分图$K_{m,n}$有m^n-1 n^m-1个不同的生成树。

参见

• Template:Le
• 道路 (图论)
• 完全图
• Template:Le
• 二分图
• 三間小屋問題