图论与组合 / 习题/考试 / 作业 / 4

• 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 条边的边割.

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

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

• 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$.

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

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

设二分图两部分为 $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)$.

考虑如下操作, 对任意点 $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$ 条路径.

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

对于有向图 $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$ 就构成一条增广路与割矛盾.

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

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

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