完全二分图

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

完全二分图
一个完全二分图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）
• 道路 (图论)
• 完全图
• 零图
• 二分图
• 三間小屋問題