图论与组合：第 4 次作业

4 #

4.1.13 #

在 $K_{m,n}$ 中, 设 $S$ 由一个部集的 $a$ 个顶点和另一个部集的 $b$ 个顶点构成.

• a) 通过计算将 $|[S,\overline{S}]|$ 用 $a,b,m,n$ 表示出来.
• b) 通过 $(a)$ 从数字上证明 $\kappa'(K_{m,n})=\min\{m,n\}$.
• c) 证明: $K_{3,3}$ 中任意由 $7$ 条边构成的集合均是不连通集, 但任意由 $7$ 条边构成的集合均不是边割.

答案

• a) $|[S,\overline{S}]|=a(n-b)+b(m-a)=an+bm-2ab$.
• b) 分析上述表达式, 当 $a=b=0$, 或 $a=m,b=n$ 时最小, 但由于 $S$ 是非空真子集, 所以只能取 $a=1,b=0$ 等情况, 那么 $|[S,\overline{S}]|\geqslant \min\{n,m\}$. 另一方面, 不妨设 $m\leqslant n$, 那么只需要取 $S$ 为 $n$ 对应部集中的一个点就有 $|[S,\overline{S}]|=m$. 从而 $\kappa'(K_{m,n})=\min\{n,m\}$.
• c) $K_{3,3}$ 一共只有 9 条边, 删除 7 条后只剩两条边, 所以一定不连通. 但根据 a) 的公式计算可得边割大小只有 $3,4,5,6$ 所以没有 7 条边的边割.

4.1.14 #

设 $G$ 是一个连通图, 且对于其中的每条边 $e$ 均存在两个包含 $e$ 的环 $C_1$ 和 $C_2$ 使得二者的唯一公共边是 $e$. 证明: $G$ 是 3-边连通的. 并以此说明 Petersen 图是 3-边连通的.

证明

根据题意, 删除任何一条边后, 对于剩下的任一条边都仍处于一个环中, 所以剩下的图是 2-边连通的.

故任意两条边均不是割边所以原图是 3-边连通的.

4.1.24 #

设 $G$ 是简单 n-顶点图. 利用推论 4.1.13 证明下述命题.

• a) 如果 $\delta(G)\geqslant \lfloor n/2\rfloor$, 则 $\kappa'(G)=\delta(G)$. 对任意 $n\geqslant 3$ 构造一个满足 $\delta(G)=\lfloor n/2\rfloor -1$ 且 $\kappa'(G)<\delta (G)$ 的简单 n-顶点图 G.
• b) 如果 $d(x)+d(y)\geqslant n-1$ 对任意 $x\nleftrightarrow y$ 成立, 则 $\kappa'(G)=\delta(G)$. 对任意 $n\geqslant 4$ 且 $\delta(G)=m\leqslant n/2-1$ 构造满足 $\kappa'(G)<\delta(G)=m$ 且 $d(x)+d(y)\geqslant n-2$ 对任意 $x\nleftrightarrow y$ 成立的图 $G$.

证明

• a) 令 $k=\lfloor n/2\rfloor$, 取两个不相交的完全图 $K_k$ 和 $K_{n-k}$, 并用一条边连接这两个完全图, 那么 $\delta (G)=k-1, \kappa'(G)=1$.
• b) 考虑 $K_{m+1}$ 和 $K_{n-m-1}$, 中间有一条边相连, 那么 $\kappa'(G)=1,\delta(G)=m$.

4.2.1 #

对于下面的图, 确定其 $\kappa(u,v)$ 和 $\kappa'(u,v)$.

答案

$\kappa(u,v)=3$, 因为上中下存在三条没有公共点的路径, 从而 $\kappa(u,v)\geq 3$, 另一方面, 中间三个点是点割集.

$\kappa'(u,v)=5$, 存在五条没有公共边的路径, 从而 $\kappa'(u,v)\geqslant 5$, 另一方面, 存在大小为 5 的边割.

4.2.4 #

证明: 如果 $P$ 是 2-连通图 $G$ 中的一条 $u,v$-路径, 则存在一条 $u,v$-路径 $Q$ 内部不相交于 $P$.

证明

反设如果不存在这样的路径, 那么一定存在点使得所有 $u,v$-路径都经过, 那么删除这个点就会使得 $u,v$ 不连通. 矛盾.

4.2.23 #

利用 Menger 定理证明 Konig-Egervary 定理.

证明

设二分图两部分为 $X,Y$, 取点 $s,t$, $s$ 与 $X$ 中所有点连边, $Y$ 中所有点与 $t$ 连边.

从而对于 $\lambda(s,t)$ 中的每条内部不相交路径, 都可以选取至少一条边拼接成一个匹配. 所以一定有 $\lambda(s,t)\leqslant \alpha'(G)$.

而对于 $\kappa(s,t)$ 对应的点割集一定也是二分图的点覆盖, 因为如果存在边 $xy$ 没有被覆盖, 那么一定存在路径 $sxyt$, 从而与点割矛盾. 故最小点覆盖一定不超过点割集大小 $\beta(G)\leqslant\kappa(s,t)$.

又 $s,t$ 在新图中不直接连接, 所以 $\lambda(s,t)=\kappa(s,t)$ 进而得到 $\alpha'(G)=\beta(G)$.

4.2.28 #

设 $X,Y$ 是 k-连通图 G 的顶点构成的不相交集合. 对 $x\in X,\ y\in Y$, 设 $u(x)$ 和 $w(y)$ 都是非负整数并使得 $\sum\limits_{x\in X}u(x)=\sum\limits_{y\in Y}w(y)=k$. 证明: $G$ 有 $k$ 条两两内部不相交的 X,Y-路径使得其中 $u(x)$ 条起始于 $x$ 而其中 $w(y)$ 条终止于 $y$ 对 $x\in X,\ y\in Y$ 成立.

证明

考虑如下操作, 对任意点 $x$, 我们添加点 $x'$, 并对任意边 $xy$, 添加边 $x'y$. 我们断言这样的操作不会使图的连通性变差. 因为对于原图的任意大小为 $k-1$ 的点集 $S$, 如果 $x\notin S$, 则 $x$ 与剩余点连通, 那么 $x'$ 就可以通过同样的边与剩余点连通. (因为 $x'$ 复制了 $x$ 的所有边) 而如果 $x\in S$, 那么原图中剩余点是联通的, 由于 $d(x')=d(x)\geqslant k$. 所以 $x'$ 必定和原图中剩余点有边. 从而连通.

那么对于 $u(x)>0$, 我们就可以用上述方式复制 $u(x)$ 个 $x$ (包括原来的点). 同样的我们也可以复制到 $w(y)$ 个 $y$. 而此时得到的新图 $G'$ 仍是 k-连通的.

下面我们再考虑添加两个点 $s,t$, 令 $s$ 与所有 $\sum u(x)=k$ 个点连边, $t$ 与所有 $\sum w(y)=k$ 个点连边. 由于 $d(s)=d(t)=k$ 所以添加这两个点后也是 k-连通的.

那么就有 $\lambda(s,t)=\kappa(s,t)\geqslant k$. 也就是存在 $k$ 条内部不相交的路径从 $s$ 到 $t$. 又 $d(s)=d(t)=k$, 所以我们之前复制出的每个点都位于一条路径上, 并且这些路径再除去 $X,Y$ 后是两两不重复的.

那么我们就找到了这样的 $k$ 条路径.

4.3.2 #

在下面的网络中, 找出从 $s$ 到 $t$ 的一个最大流. 利用对偶问题证明所给出的结果是最优的, 并解释为什么这样可以证明最优性.

证明

存在下图所示流量为 17 的流, 并且边 3,4,5,2,3 构成一个大小为 17 的割. 根据最大流等于最小割定理该流就是最大流.

4.3.10 #

用网络流证明 Konig-Egvervary 定理.

证明

对于有向图 $s\to X$, $X\to Y$, $Y\to t$. 每条边的流量都设为 1.

考虑 $s,t$ 之间的最大流. 由于流量都是 1, 所以匹配和流是一一对应的. 即最大流对应最大匹配.

类似的, 割和点覆盖也是对应的, 但对于 $xy\in S$ 的割, 我们考虑将 $xy$ 替换为 $yt$ 形成一个新割大小不增. 不难验证替换后也是割. 所以我们只考虑不包含 $xy$ 边的割, 这些个和点覆盖可以构造双射, 考虑对于割中 $sx, yt$ 两类边, 取所有 $x,y$ 作为点覆盖, 因为如果存在边 $x'y'$ 未被覆盖, 那么 $sx'y't$ 就构成一条增广路与割矛盾.

所以最小点覆盖对应了最小割.

所以根据最大流等于最小割可以得到最大匹配等于最小点覆盖.

4.3.13 #

几个公司派代表开会; 第 $i$ 个公司派 $m_i$ 名代表. 会议的组织者负责安排同时进行的各组会议; 第 $j$ 组会议可以容纳 $n_j$ 为与会者. 组织者要把与会者全部安排到各组会议中, 但是从同一个公司来的代表必须位于不同的会议组中. 各组会议无需满员.

• a) 阐明如何用网络流来测试上述要求能否被满足.
• b) 设 $p$ 是公司的个数, 而 $q$ 是会议组的个数. 适当编号使得 $m_1\geqslant \cdots\geqslant m_p$ 并且 $n_1\leqslant\cdots\leqslant n_q$. 证明: 存在一个满足所有约束的代表安排方案当且仅当 $k(q-l)+\sum\limits_{j=1}^l n_j\geqslant\sum\limits_{i=1}^k m_i$ 对所有满足 $0\leqslant k\leqslant p,\ 0\leqslant l\leqslant q$ 的 k,l 成立.

答案

• a) 考虑这样一个有向图, 起点 $s$ 向每个公司连边, 容量为 $m_i$, 每个公司向每个会议连边, 容量为 $1$, 每个会议向汇点 $t$ 连边, 容量为 $n_j$. 考察 $s,t$ 间的最大流, 当最大流等于 $\sum m_i$ 时即存在这样的分配.
• b) 必要性: 如果存在可行方案, 那么对于最大的 $k$ 个公司, 和最小的 $l$ 个会议. 如果不满足该不等式, 那么说明这 $k$ 个公司的人永远不可能全部参与会议. 因为已经将 $1,\ldots,l$ 会议坐满, 剩余会议每个会议最多有 $k$ 个这些公司的人参与. 所以等式左边是这 $k$ 个人参与会议人数的上界.