完全二分圖

完全二分圖
一個完全二分圖m=3 n =2
頂點	n+m
邊	mn
自同構群	2m!n!如果m=n，否則m!n!

完全二分圖是一種特殊的二分圖，可以把圖中的頂點分成兩個集合，使得第一個集合中的所有頂點都與第二個集合中的所有頂點相連。

定義

完全二分圖$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}$；外平面圖不能含有子圖$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}$具有正則的n-邊染色。
• 完全二分圖$K_{m,n}$有m^n-1 n^m-1個不同的生成樹。

參見

• 圈圖
• 道路 (圖論)
• 完全圖
• 零圖
• 二分圖
• 三間小屋問題