完全２部グラフ

ウィキペディア

完全2部グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/06 05:36 UTC 版)

完全2部グラフ
m=3 n =2の完全2部グラフ
頂点	n+m
辺	mn
自己同型	2m!n! if m=n, その他 m!n!
テンプレートを表示

完全2部グラフ（かんぜんにぶグラフ、英: complete bipartite graph）は、グラフ理論において、2部グラフのうち特に第1の集合に属するそれぞれの頂点から第2の集合に属する全ての頂点に辺が伸びているものをいう。bicliqueとも。

定義

完全2部グラフ ${\displaystyle G:=(V_{1}+V_{2},E)}$

星グラフ S₃, S₄, S₅, S₆

• 
  K_1,1
• 
  K_2,1
• 
  K_2,2
• 
  K_3,1
• 
  K_3,2
• 
  K_3,3
• 
  K_7,1

特性

• 2部グラフから、辺数 ${\displaystyle m\cdot n}$