完全二分图

维基百科,自由的百科全书
跳转至: 导航搜索
完全二分图
Complete bipartite graph K3,2.svg
一个完全二分图m=3 n =2
顶点 n+m
mn
自同构群 2m!n!如果m=n,否则m!n!

完全二分图是一种特殊的二分图,可以把图中的顶点分成两个集合,使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。

定义[编辑]

完全二分图G:=(V_1 + V_2, E)是一个二分图,使得对于任何两个顶点v_1 \in V_1v_2 \in V_2v_1 v_2都是G中的一条边。\left|V_1\right|=m\left|V_2\right|=n的完全二分图记为K_{m,n}

例子[编辑]

性质[编辑]

参见[编辑]