二分图
顶点可分成两侧、所有边都跨两侧的无向图;等价于无奇环,可用二染色判定。标签 图论 / 二分图 / 染色 / 奇环
定义
设 是无向图。若存在划分
使每条边的一个端点在 、另一个在 ,则称 是二分图, 称为它的两部。
等价地,二分图可以二染色:相邻顶点颜色不同,同色顶点之间没有边。二分图不要求 ,也不要求连通;不同连通分量可以分别染色。
所有跨两部的边都出现的二分图称为完全二分图 ,其中 、。
判定方法见 二分图判定。
标签 图论 / 二分图 / 染色 / 奇环
设 是无向图。若存在划分
使每条边的一个端点在 、另一个在 ,则称 是二分图, 称为它的两部。
等价地,二分图可以二染色:相邻顶点颜色不同,同色顶点之间没有边。二分图不要求 ,也不要求连通;不同连通分量可以分别染色。
所有跨两部的边都出现的二分图称为完全二分图 ,其中 、。
判定方法见 二分图判定。