完全二分图是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。
定义
完全二分图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}。
例子
File:Complete bipartite graph K3,1.svg|K1,3
File:Complete bipartite graph K3,2.svg|K2,3
File:Complete bipartite graph K3,3.svg|K3,3
性质
*平面图不能含有子图K_{3,3}；不能含有子图K_{3,2}（这些是必要条件而不是充分条件）。
*完全二分图K_{m,n}的顶点覆盖数为\min \lbrace m,n \rbrace，边覆盖数为\max\lbrace m,n\rbrace。
*完全二分图K_{m,n}具有大小为\max\lbrace m,n\rbrace的。
*完全二分图K_{m,n}具有大小为\min\lbrace m,n\rbrace的。
*完全二分图K_{n,n}具有正则的。
*完全二分图K_{m,n}有mn-1 nm-1个不同的生成树。
参见
*
- 道路 (图论)
- 完全图
*
- 二分图
- 三間小屋問題
评论 (0)