二分图

顶点可分成两侧、所有边都跨两侧的无向图;等价于无奇环,可用二染色判定。

标签 图论 / 二分图 / 染色 / 奇环

定义

设 𝐺=(𝑉,𝐸) 是无向图。若存在划分

𝑉=𝐿∪𝑅,𝐿∩𝑅=∅,

使每条边的一个端点在 𝐿、另一个在 𝑅,则称 𝐺 是二分图,𝐿,𝑅 称为它的两部。

等价地,二分图可以二染色:相邻顶点颜色不同,同色顶点之间没有边。二分图不要求 |𝐿|=|𝑅|,也不要求连通;不同连通分量可以分别染色。

所有跨两部的边都出现的二分图称为完全二分图 𝐾𝑚,𝑛,其中 |𝐿|=𝑚、|𝑅|=𝑛。

判定方法见 二分图判定。

源码位置