完全二分图

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

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

定义

完全二分图 是一个二分图,使得对于任何两个顶点   都是 中的一条边。  的完全二分图记为 

例子

性质

  • 平面图不能含有子图 外平面图英语Outerplanar graph不能含有子图 (这些是必要条件而不是充分条件)。
  • 完全二分图 顶点覆盖数 ,边覆盖数为 
  • 完全二分图 具有大小为 最大独立集英语Maximum independent set
  • 完全二分图 具有大小为 最大匹配英语Maximum cardinality matching
  • 完全二分图 具有正则的n-边染色英语Edge coloring
  • 完全二分图 有mn-1 nm-1个不同的生成树

参见