二分图学习笔记()

一个 无向图 称为 二分图 \(\iff \exists s \subseteq \mathcal V, \forall (u,v) \in\mathcal E, (u \in s \leftrightarrow v \not \in s)\),其中 \(\mathcal V\) 是顶点的集合,\(\mathcal E\) 是边的集合
定理 1.1:至少有两个节点的树是二分图。
令任意节点为根,设根为 \(r\)。令 \(\text{dep}(x) = \left\{\begin{array}{cc}0 & x=r \\\text{dep}(\text{fa}(x))+1 &x\ne r\end{array}\right.\),则显然可以构造 \(s = \{x:\text{dep}(x)\}\)
定理 1.2:一个图是二分图 \(\iff\) 他所有回路的长度均为偶数或没有回路。
证明:反证,若存在一条长度为奇数的回路 \(a_1 \to a_2 \to a_3 \to \dots \to a_n\),则必有 \(\forall x \in [0, \dfrac n2) \cap \mathbb Z, a_{2x+1} \in s\),又因为图为无向图,\(a_n \leftrightarrow a_1\) 有一条边,所以 \(a_n \not\in s\),根据 \(n\) 为奇数得出 \(a_n \in s\),矛盾。
一个图 \(G\) 是二分图 \(\iff\) 使用 b/dfs 对图进行红蓝染色,若存在矛盾则不是二分图,反之亦然。
证明同回路长度为偶。

————————

一个 无向图 称为 二分图 \(\iff \exists s \subseteq \mathcal V, \forall (u,v) \in\mathcal E, (u \in s \leftrightarrow v \not \in s)\),其中 \(\mathcal V\) 是顶点的集合,\(\mathcal E\) 是边的集合
定理 1.1:至少有两个节点的树是二分图。
令任意节点为根,设根为 \(r\)。令 \(\text{dep}(x) = \left\{\begin{array}{cc}0 & x=r \\\text{dep}(\text{fa}(x))+1 &x\ne r\end{array}\right.\),则显然可以构造 \(s = \{x:\text{dep}(x)\}\)
定理 1.2:一个图是二分图 \(\iff\) 他所有回路的长度均为偶数或没有回路。
证明:反证,若存在一条长度为奇数的回路 \(a_1 \to a_2 \to a_3 \to \dots \to a_n\),则必有 \(\forall x \in [0, \dfrac n2) \cap \mathbb Z, a_{2x+1} \in s\),又因为图为无向图,\(a_n \leftrightarrow a_1\) 有一条边,所以 \(a_n \not\in s\),根据 \(n\) 为奇数得出 \(a_n \in s\),矛盾。
一个图 \(G\) 是二分图 \(\iff\) 使用 b/dfs 对图进行红蓝染色,若存在矛盾则不是二分图,反之亦然。
证明同回路长度为偶。