查看“︁完全二分图”︁的源代码

{{unreferenced|time=2015-11-23T19:24:13+00:00}}
{{NoteTA
|1 = zh-cn:二分图; zh-tw:二部圖; zh-hk:二分圖;
}}

{{infobox graph
 | name = 完全二分图
 | image = [[File:Complete bipartite graph K3,2.svg|160px]]
 | image_caption = 一个完全二分图''m''=3 ''n'' =2
 | automorphisms    = 2''m''!''n''!如果''m''=''n''，否则''m''!''n''!
 | vertices = ''n''+''m''
 | edges = ''mn''
}}
'''完全二分图'''是一种特殊的[[二分图]]，可以把图中的[[顶点 (图论)|顶点]]分成两个[[集合_(数学)|集合]]，使得第一个集合中的所有[[顶点 (图论)|顶点]]都与第二个集合中的所有顶点相连。

== 定义 ==
完全二分图<math>G:=(V_1 + V_2, E)</math>是一个二分图，使得对于任何两个[[顶点 (图论)|顶点]]<math>v_1 \in V_1</math>和<math>v_2 \in V_2</math>，<math>v_1 v_2</math>都是<math>G</math>中的一条边。<math>\left|V_1\right|=m</math>且<math>\left|V_2\right|=n</math>的完全二分图记为<math>K_{m,n}</math>。

== 例子 ==

<gallery>
File:Complete bipartite graph K3,1.svg|''K''<sub>1,3</sub>
File:Complete bipartite graph K3,2.svg|''K''<sub>2,3</sub>
File:Complete bipartite graph K3,3.svg|''K''<sub>3,3</sub>
</gallery>

== 性质 ==

*[[平面图 (图论)|平面图]]不能含有[[子图]]<math>K_{3,3}</math>；{{le|外平面图|Outerplanar graph}}不能含有子图<math>K_{3,2}</math>（这些是[[必要条件]]而不是[[充分条件]]）。
*完全二分图<math>K_{m,n}</math>的[[覆盖 (图论)|顶点覆盖数]]为<math>\min \lbrace m,n \rbrace</math>，边覆盖数为<math>\max\lbrace m,n\rbrace</math>。
*完全二分图<math>K_{m,n}</math>具有大小为<math>\max\lbrace m,n\rbrace</math>的{{le|最大独立集|Maximum independent set}}。
*完全二分图<math>K_{m,n}</math>具有大小为<math>\min\lbrace m,n\rbrace</math>的{{le|最大匹配|Maximum cardinality matching}}。
*完全二分图<math>K_{n,n}</math>具有正则的{{le|边染色|Edge coloring|''n''-边染色}}。
*完全二分图<math>K_{m,n}</math>有m<sup>n-1</sup> n<sup>m-1</sup>个不同的[[生成树]]。

== 参见 ==
* {{le|圈图|Circle graph}}
* [[道路 (图论)]]
* [[完全图]]
* {{le|零图|Null graph}}
* [[二分图]]
* [[三間小屋問題]]
[[Category:图]]