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

完全二部圖
一個完全二部圖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個不同的生成樹

參見

編輯