3

3.1.2

在环 $C_n$ 中, 确定极大匹配边数的最小值.

答案

首先连续的三条边至少有一条在极大匹配中, 不然一定可以将中间那条边加入到匹配中构成更大的一个匹配.

所以至少为 $\lceil \frac{n}{3}\rceil$, 另一方面, 我们只需按顺序每隔两条边选一条边 (第一条边也选) 那么就能取到这个下界.

所以最小值为 $\lceil\frac{n}{3}\rceil$

3.1.8

证明或否定: 每棵树至多有一个完美匹配.

证明

考虑数学归纳法, 对节点数量归纳.

首先奇数个节点显然没有完美匹配, 故成立.

下面对偶数个节点归纳, $n=2$ 时显然成立.

当 $n=2k$ 时, 任意找到一个叶子 $u$, 设其和 $v$ 相连, 那么 $uv$ 必定属于任意完美匹配, 否则 $u$ 不被覆盖.

那么 $G-u-v$ 被分为若干子树, 如果有奇子树, 证明整个树没有完美匹配. 否则根据归纳假设, 所有子树的完美匹配都是唯一的, 从而整个树的完美匹配就是子树的匹配再加上 $uv$. 所以唯一.

3.1.9

证明: 图 $G$ 中每个极大匹配至少有 $\alpha'(G)/2$ 条边.

证明

取一个最大匹配 $M$, 将点集分为不相邻的两个集合 $X,Y$, 则有 $|X|=|Y|=\alpha'(G)$.

先考虑任意极大匹配 $M'$, 设 $X_1=V(M')\cap X, X_2=X-V(M'), Y_1=V(M')\cap Y, Y_2=Y-V(M')$.

那么一定有 $|X_2|\leqslant |Y_1|$ 和 $|Y_2|\leqslant |X_1|$, 否则就能在 $M$ 中再挑选一条边加入匹配与极大矛盾.

而此时匹配的边数已经不低于 $\frac{|X_1|+|Y_1|}{2}$, 而 $|X_1|+|Y_1|\geqslant |X_2|+|Y_2|$ 所以 $\frac{|X_1|+|Y_1|}{2}\geqslant \frac{\alpha'(G)}{2}$.

3.1.19

令 $\mathcal{A} = \{A_1, \cdots, A_m\}$ 是集合 $Y$ 的子集族. $\mathcal{A}$ 的一个相异代表系 (SDR) 是 $Y$ 中一些满足 $a_i \in A_i$ 的不同元素 $a_1, \cdots, a_m$ 构成的一个集合. 证明: $\mathcal{A}$ 有一个 SDR 当且仅当 $\left| \bigcup\limits_{i \in S} A_i \right| \geq |S|$ 对任意 $S \subseteq \{1, \cdots, m\}$ 成立. (提示: 将该问题转化为图论问题.)

证明

考虑建二分图. $i\leftrightarrow y, \forall y\in A_i$. 那么根据 Hall 定理, 该二分图含有一个浸润 $\{1,2,\cdots, m\}$ 的匹配当且仅当 $|N(S)|\geqslant |S|,\forall S\subseteq \{1,2,\cdots,m\}$, 而在该题目情形下 $|N(S)|=|\bigcup\limits_{i\in S} A_i|$. 所以有一个 SDR 等价于有一个浸润 $\{1,2,\cdots,m\}$ 的匹配等价于 $|\bigcup\limits_{i\in S}A_i|\geqslant |S|,\forall S\subseteq \{1,2,\cdots,m\}$.

3.1.42

一个贪心算法用迭代过程构造一个较大的独立集 $S$, 它每次迭代从剩下的图中选择度最小的一个顶点添加到 $S$ 中, 并把该顶点及其相邻顶点从图中删除. 证明: 在简单图 $G$ 中, 该算法产生的独立集的大小至少为 $\sum_{v \in V(G)} \frac{1}{d_G(v) + 1}$. (Caro[1979], Wei[1981])

证明

考虑按该算法一共取了 $k$ 次, 每次删除的中心点为 $v_i$, 总点集为 $V_i$.

那么我们有 $V(G)=\bigcup\limits_{i=1}^k V_i$, 且 $\forall v\in V_i, d_{G'}(v)\geqslant d_{G'}(v_i)$, 并有 $|V_i|\leqslant d_{G'}(v_i)+1\leqslant d_{G}(v_i)+1$, 所以 $\sum\limits_{v\in V_i}\frac1{d_G(v)+1}\leqslant \sum\limits_{v\in V_i}\frac{1}{d_{G'}(v)+1}\leqslant 1$.

综上 $k\geqslant \sum\limits_{v\in V(G)}\frac 1 {d_G(v)+1}$.

3.3.3

对于下面的图, 对 $\{0,1,2,3,4\}$ 中的每个 $k$ 值给出一个 $k$-因子.

答案

3.3.4

令 $G$ 是一个 $k$-正则二部图. 证明: $G$ 可以分解为若干个 $r$-因子当且仅当 $r$ 整除 $k$.

证明

"$\Rightarrow$": 设分解为 $a$ 个 $r$-因子, 那么考虑其中一个点, 在整个图中, 度数 $d_G(v)=k$, 在每个因子中度数为 $r$, 总度数为 $ar$ 所以有 $k=ar$ 即整除.

"$\Leftarrow$": 根据 Hall 定理推论, 正则的二部图具有 1-因子, 而删去一个 1-因子后变为 k-1 正则二部图仍有 1-因子. 于是一共可以取出 k 个 1-因子. 而两个 1-因子的并就得到一个 2-因子. 所以我们将这 k 个 1-因子每 r 个分为一组就得到 $\frac{k}{r}$ 个 r-因子.

3.3.6

证明: 树 $T$ 有一个完美匹配当且仅当 $o(T-v)=1,\forall v\in V(T)$.

证明

"$\Rightarrow$": $T$ 有完美匹配, 所以是偶数个节点. 那么任意去除一个点后剩余点个数是奇数个. 所以必定存在奇数个奇分支. 另一方面由于树是二部图, 根据 Tutte 定理, 有 $o(T-v)\leqslant 1$, 所以 $o(T-v)=1$.

"$\Leftarrow$": 考虑数学归纳法, 对节点个数归纳. 两个点显然成立.

任取叶子 $u$, 及其唯一邻居 $v$, 考虑 $T-\{u,v\}$ 被分为 $T_1,T_2,\ldots,T_k$ 这些子树, 由于 $o(T-v)=1$, $\{u\}$ 是 $T-v$ 的一个奇分支, 所以 $|T_i|$ 为偶数. 而对于 $T_i$ 中的点 $T-w= T_i-w\cup (T_1\cup T_2\cup\cdots T_{i-1}\cup T_{i+1}\cup\cdots\cup T_k\cup\{u,v\})$ 并且后面一部分是同一个连通分支, 由于 $|T_i|$ 是偶数, 所以这一部分也是偶数, 即 $o(T_i-w)=1$, 即 $T_i$ 也满足题设条件, 故根据归纳假设其存在完美匹配. 于是将所有子树的完美匹配和 $uv$ 并起来就得到一个原图的完美匹配.

3.3.7

对任意 $k>1$, 构造一个没有 1-因子的 k-正则图.

答案

当 $k$ 为偶数时, 取 $K_{k+1}$ 即为没有 1-因子的 k-正则图.

当 $k$ 为奇数时,