完全二分圖

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

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