完全二分图

维基百科,自由的百科全书
跳转至: 导航搜索
完全二分图
Complete bipartite graph K3,2.svg
一个完全二分图m=3 n =2
顶点 n+m
mn
自同构群 2m!n!如果m=n,否则m!n!

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

定义[编辑]

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

例子[编辑]

性质[编辑]

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

参见[编辑]