二分图erfentu

设G= 是无向图. 若G的点集V=T∪S,T∩S=φ，并且，T的点只与S的点邻接，S的点只与T的点邻接，则G称为二分图(二部图、偶图、双图). 记做G: . 例如，G₁,G₂都是二分图，G₁＝ < {v ₁,v ₄ ,v₅,v₆},{v₂,v₃,v₇,v₈}; R>，而G₂ < {u₁,u₂ },{u₃,u₄,u₅}; E>.

K₁

K₂

若二分图G= 中，T的每个点与S的每个点邻接，S的每个点也与T的每个点邻接，则称G是完全二分图. |T|=m,|S|=n的完全二分图记作K_m,n. 显然，K_m,n＝K_n,m.
m个人n件工作的单位的分工，可用二分图T={v₁,v ₂，…，v_m},S= {v₁,v₂，…，v_n} 分别表示人员与工作的集合，地i做工作，，则v _i ,u_j有边相连.这样得到的工作分配图就是个二分图.
K₃₃，可解释成三所房子均需安装煤气、自来水与电缆的管线布置图.