Bóna · 枚举与解析组合学导论 · 第 6 章 极值组合学

6.6　习题Exercises

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（题目目标 / 分步思路 / 例）与配图为面向高中生的解题方法提示，逐步推演、举例、画图，不用比喻。本节只给思路与方法，完整最终解答见对应“习题解答”一节。

本节用到的记号与名词

提示：除非另有说明，所提到的所有图都是简单图。

  1. 三角形的存在性。 设 \(G\) 是一个有 \(2n\) 个顶点、且边数多于 \(n^2\) 的图。用数学归纳法证明 \(G\) 必含一个三角形（三个两两相邻的顶点）。

    思路这是 Turán 型极值结果（\(K_3\) 的情形）。要证“边足够多 ⟹ 出现三角形”。
    1. 对 \(n\) 做归纳。基础情形 \(n=1\)：\(2\) 个顶点最多 \(1\) 条边，而题设要求 \(>1\) 条，前提矛盾（或取 \(n=2\) 起验证），命题平凡成立。
    2. 归纳步：若 \(G\) 无三角形，取一条边 \(uv\)。\(u,v\) 不能有公共邻居（否则成三角形）。把 \(u,v\) 连同与它们相连的边一并删去，得到一个 \(2(n-1)\) 顶点的子图 \(G'\)。
    3. 统计被删掉的边数：含 \(u\) 或含 \(v\) 的边总数 \(=d(u)+d(v)-1\)。关键不等式是 \(d(u)+d(v)\le 2n\)（否则 \(u,v\) 必有公共邻居）。
    4. 于是 \(e(G')\ge e(G)-(2n-1)>n^2-(2n-1)=(n-1)^2\)，对 \(G'\) 用归纳假设得三角形，矛盾。

  2. 二部子图。 用 \(\delta(A)\)、\(e(A)\) 分别表示图 \(A\) 的最小度与边数，用 \(d_A(x)\) 表示顶点 \(x\) 在 \(A\) 中的度数。

    1. 证明：任何图 \(G\) 都含一个二部子图（bipartite subgraph）\(B\)，使得 \(e(B)\ge e(G)/2\)。
    2. 证明：任何图 \(G\) 都含一个二部子图 \(B\)，使 \(B\) 与 \(G\) 的顶点集相同，且 \(\delta(B)\ge \delta(G)/2\)。
    3. 证明：任何图 \(G\) 都含一个二部子图 \(B\)，使 \(B\) 与 \(G\) 顶点集相同，且对所有顶点 \(x\)，都有 \(d_B(x)\ge d_G(x)/2\)。
    思路（极值/局部调整法）核心方法：取一个让“跨越两部的边数最多”的二部划分，再说明任何顶点若违反条件就可把它换到另一边、使边数增加，与“最多”矛盾。
    1. (a) 在所有把顶点分成两堆 \((X,Y)\) 的方式中，选使跨边数 \(e(B)\) 最大的那个 \(B\)。对任一顶点 \(x\)：它指向自己这堆的边数 \(\le\) 指向对面那堆的边数（否则把 \(x\) 挪到对面跨边会更多）。把这条对所有顶点求和：每条非跨边被自己两端各算一次，故跨边 \(\ge\) 非跨边，于是 \(e(B)\ge e(G)/2\)。
    2. (c) 是逐点加强版：上一步对“每个顶点”都成立，恰好就是 \(d_B(x)\ge d_G(x)/2\)。
    3. (b) 由 (c) 立即得到：每个顶点在 \(B\) 中度数至少是它在 \(G\) 中度数的一半，再取下界即 \(\delta(B)\ge\delta(G)/2\)。

  3. 凸性。 证明：对所有非负整数 \(r\)，函数 \(f(x)=\dbinom{x}{r}\) 在区间 \([r-1,\infty)\) 上是凸函数（convex）。

    思路把组合数当成关于 \(x\) 的多项式 \(\binom{x}{r}=\dfrac{x(x-1)\cdots(x-r+1)}{r!}\)，用二阶导数判别凸性，或用差分。
    1. 方法一（二阶导）：求 \(f''(x)\)，证明它在 \([r-1,\infty)\) 上 \(\ge 0\)。注意此区间内各因子的符号控制。
    2. 方法二（凸性的实用判据）：在整数点上验证 \(f(x-1)+f(x+1)\ge 2f(x)\)，即 \(\binom{x-1}{r}+\binom{x+1}{r}\ge 2\binom{x}{r}\)，用帕斯卡公式 \(\binom{x+1}{r}=\binom{x}{r}+\binom{x}{r-1}\) 展开化简。
    3. 凸性是本章很多“度数集中 ⟹ 边/三角形多”的不等式（如 Turán 证明里的 Jensen 不等式）背后的工具。

  4. “双层棱柱”的色数。 设 \(G\) 是一个图，\(G_1\) 由如下方式得到：取 \(G\) 的两份拷贝，再把 \(G\) 的每个顶点 \(x\) 与它在另一拷贝中对应的顶点 \(x'\) 连边（见图 6.13）。用 \(\chi(G)\) 表示 \(\chi(G_1)\)。

    G G₁（两份 G + 对应点连边）
    虚线为“对应点 \(x\!-\!x'\)”的连边。问题：\(\chi(G_1)\) 与 \(\chi(G)\) 的关系。
    思路先猜结论 \(\chi(G_1)=\chi(G)\)（当 \(\chi(G)\ge 2\) 时），再分别证 \(\le\) 与 \(\ge\)。
    1. 下界：\(G\) 是 \(G_1\) 的子图，故 \(\chi(G_1)\ge\chi(G)\)。
    2. 上界：设 \(G\) 有一个用 \(\chi(G)=c\) 种颜色的正常染色。第一拷贝照用这个染色；第二拷贝把每个 \(x'\) 染成与 \(x\) 不同的颜色——只要 \(c\ge 2\)，可把第二拷贝的颜色做一个“轮换/置换”使每个 \(x'\) 的颜色异于 \(x\) 且内部仍正常。
    3. 验证：拷贝内部因平移染色仍合法，跨拷贝的 \(x\!-\!x'\) 边因两端异色也合法，故 \(c\) 种颜色够用。

  5. 弱直积。 设 \(G,H\) 为两个简单图，定义它们的弱直积（weak direct product）\(G\times H\)：顶点集为所有有序对 \((g,h)\)，其中 \(g\) 是 \(G\) 的顶点、\(h\) 是 \(H\) 的顶点；\((g,h)\) 与 \((g',h')\) 之间有边当且仅当 \(g\) 与 \(g'\) 在 \(G\) 中相邻且 \(h\) 与 \(h'\) 在 \(H\) 中相邻。图 6.14 给出 \(K_2\times K_3\)。

    1. 证明 \(\chi(G\times H)\le \min(\chi(G),\chi(H))\)。
    2. 是否总有 \(\chi(G\times G)=\chi(G)\)？
    (x,1) (x,2) (x,3) (y,1) (y,2) (y,3)
    图 6.14：\(K_2\)（顶点 \(x,y\)）与 \(K_3\)（顶点 \(1,2,3\)）的弱直积。\((x,i)\) 与 \((y,j)\) 相邻当且仅当 \(x\sim y\)（恒成立）且 \(i\ne j\)；同一侧顶点间无边（因 \(K_2\) 中无自环边）。结果是一个 6-圈。
    思路(a) 直接构造染色；(b) 是著名的 Hedetniemi 猜想方向的小问，重在举例/思考。
    1. (a) 设 \(c\) 是 \(G\) 的一个 \(\chi(G)\) 染色。给 \((g,h)\) 染 \(c(g)\)。若 \((g,h)\sim(g',h')\)，则 \(g\sim g'\)，故 \(c(g)\ne c(g')\)，合法。于是 \(\chi(G\times H)\le\chi(G)\)；对 \(H\) 同理，取较小者。
    2. (b) 不必死证，先用小例子试：取完全图 \(K_3\)，算 \(\chi(K_3\times K_3)\)，看是否仍为 \(3\)。这能帮助你理解“积的色数”何时取到上界。

  6. 给定度序列的色数上界。 一个 \(10\) 个顶点的图 \(G\) 的度数为 \(9,3,3,3\) 以及六个度数等于 \(2\)。证明 \(\chi(G)\le 4\)。

    思路用“低度顶点可贪心染色”的思想（与第 9 题的 \(\chi\le \Delta+1\) 同源），但要利用大多数顶点度数很小这一事实。
    1. 那个度数 \(9\) 的顶点 \(v\) 与所有其他点相邻，单独占一种颜色。
    2. 去掉 \(v\) 后，剩下 \(9\) 个顶点，它们在原图中度数为 \(3,3,3,2,2,2,2,2,2\)，去掉与 \(v\) 的连边后每个度数再减 \(1\)，得到一个最大度很小的图，用 \(\le 3\) 种颜色按度数从小到大依次（或反向）贪心染色即可。
    3. 合计 \(1+3=4\) 种颜色，得 \(\chi(G)\le 4\)。

  7. 色数的精确取值。 证明：若 \(G\) 如第 6 题所述，则 \(\chi(G)\) 可以是 \(3\) 或 \(4\)，但不能是 \(2\)。

    思路分两件事：排除 \(2\)（找奇圈），并各给一个达到 \(3\)、\(4\) 的具体例子。
    1. \(\chi(G)\ne 2\)：色数为 \(2\) 等价于图是二部图、等价于无奇圈。说明这种度序列必然含奇圈（例如度数 \(9\) 的点与若干度数 \(2\) 的点能构成奇长闭路），从而 \(\chi\ge 3\)。
    2. \(\chi=4\) 可达：构造含 \(K_4\) 或奇轮的具体图。\(\chi=3\) 可达：另造一个无 \(K_4\) 但有奇圈的图。两例都要满足给定度序列。

  8. 非 2-连通图的最多边数。 称一个连通图是 \(k\)-连通（\(k\)-vertex-connected）的，若删去其任意 \((k-1)\) 个顶点及相邻边后仍连通。问：\(n\) 个顶点的简单图若不是 2-连通的，最多能有多少条边？

    思路“非 2-连通”意味着存在一个割点（或图本身不连通）。要在此约束下把边塞到最多，构造极值图。
    1. 极值构造：取一个 \(K_{n-1}\)，再添一个顶点只与 \(K_{n-1}\) 中一个顶点相连。这个公共顶点就是割点，故不是 2-连通。
    2. 数边：\(\binom{n-1}{2}+1\) 条。再论证不可能更多——任何非 2-连通图都可经一个割点分块，跨块边受限。

  9. 最大度与色数。 设 \(G\) 的最大度为 \(k\)。

    1. 证明 \(\chi(G)\le k+1\)。
    2. 找出两个无穷类图，使得 (a) 的界是紧的，即 \(\chi(G)=k+1\)。
    思路（贪心染色）把顶点排成一列依次染色：每染一个点，它至多有 \(k\) 个已染邻居，故 \(k+1\) 种颜色里总有一种可用。
    1. (a) 取颜色 \(\{1,\dots,k+1\}\)。逐个顶点染：当前点的邻居最多 \(k\) 个，至多用掉 \(k\) 种颜色，必有第 \(k+1\) 种可选。
    2. (b) 两个达到等号的无穷类：完全图 \(K_{k+1}\)（最大度 \(k\)，色数 \(k+1\)）；以及奇圈 \(C_{2m+1}\)（最大度 \(2\)，色数 \(3=2+1\)）。

  10. (进阶 +) Brooks 定理的情形。 设 \(G\) 的最大度为 \(k\)。

    1. 找出所有 3-连通且满足 \(\chi(G)=k+1\) 的图 \(G\)。
    2. 找出所有满足 \(\chi(G)=k+1\) 的图 \(G\)。
    思路（Brooks 定理）这正是Brooks 定理的内容：连通图取到上界 \(\chi=\Delta+1\) 当且仅当它是完全图或奇圈。
    1. (b) 结论：恰当 \(G\)（按连通分量看）含完全图 \(K_{k+1}\) 或奇圈（当 \(k=2\)）作为达到上界的分量。叙述并验证 Brooks 定理。
    2. (a) 在 3-连通这一更强条件下，奇圈（仅 2-连通）被排除，只剩完全图 \(K_{k+1}\) 一类。

  11. 两班排班。 某工厂的工人总共掌握 \(500\) 种不同技能，且每种技能恰有 \(10\) 名工人掌握。证明：可以把工人排成两个班次，使得每种技能在两个班次中都有人。

    思路（概率法/局部调整）随机把每个工人独立分到两班之一，再用调整法消除“某技能全挤在一班”的坏情形。
    1. 把“每种技能在每班都有”视为约束。先随机分班，计算“某种技能两班分布不均、甚至全在一班”的概率。
    2. 用调整论证：若某技能两班都无人不可能（每技能 10 人），唯一坏情况是 10 人全在同一班；把其中一人调到另一班，逐步修复，论证存在一种合法排班。

  12. 超图大小上界（并集受限）。 设 \(\mathcal F\) 是 \([n]\) 上的超图，满足：对 \(\mathcal F\) 中任意两条边 \(A,B\)，都有 \(A\cup B\ne[n]\)。问 \(\mathcal F\) 最多能有多大？

    思路（取补集，转化为反链/相交族）“\(A\cup B\ne[n]\)”等价于“补集 \(\bar A\cap\bar B\ne\varnothing\)”，即补集族两两相交。
    1. 令 \(\bar A=[n]\setminus A\)。条件变成补集族任意两个有公共元素，即一个相交族（intersecting family）。
    2. 相交族最大为 \(2^{n-1}\)（固定一个元素必属于每个集合即可达到）。故 \(|\mathcal F|\le 2^{n-1}\)。

  13. 替代证明。 我们对定理 6.30 给出的证明中，例子里的 \(\mathcal F\) 含有 \([n]\) 中从大小 \(1\) 到 \(n\) 的所有尺寸的边。请给出一个只用较少种不同尺寸的边的替代证明。

    思路回看定理 6.30 的极值族要达到什么数量，再换一个用尽量集中尺寸（比如只用大小约 \(n/2\)）的构造来达到同样的界。
    1. 明确定理 6.30 想证的等号能达到的最大值。
    2. 构造只用一两种尺寸的边的族（如全部 \(\lfloor n/2\rfloor\) 元子集），验证它满足所需条件且达到同样规模。

  14. Helly 型相交问题。 设 \(\mathcal F\) 是 \([n]\) 上的超图，其中最小的边大小为 \(k\)。假设：无论怎样取 \(\mathcal F\) 中的 \(k+1\) 条边，它们的交集都非空。问：\(\mathcal F\) 中所有边的交集是否可能为空？

    思路（鸽巢/反证）假设全体交为空，则每个元素至少被某条边“漏掉”。最小边只有 \(k\) 个元素，配合 \(k+1\) 条边推矛盾。
    1. 取最小边 \(A\)（\(|A|=k\)）。若全交为空，则 \(A\) 的每个元素 \(a\) 都存在某边 \(B_a\) 不含 \(a\)。
    2. 这样得到至多 \(k\) 条边 \(B_a\)，再加上 \(A\) 本身共 \(k+1\) 条；它们的交集不含 \(A\) 的任何元素，又被含于 \(A\)，故为空——与“任意 \(k+1\) 条边交非空”矛盾。结论：全交不可能为空。

  15. (进阶 +) 避免等差数列的染色。 给出 \([2141]\) 的一个 2-染色（2-coloring）的例子，使其不含长度为 \(18\) 的单色等差数列（monochromatic arithmetic progression）。

    思路（van der Waerden 数的下界构造）这说明 \(W(18;2)>2141\)。需要明确地造出一个分块/周期染色，并逐一验证没有长 18 的单色等差数列。
    1. 常用手法：把 \(\{1,\dots,2141\}\) 按某种周期或递归（如基于较小 van der Waerden 构造的拼接）分两色。
    2. 对任意可能的等差数列，按公差所在区间分类讨论，逐类证明无法在同色内凑满 18 项。

  16. \(R(3,3)\le 6\)。 把 \(K_6\) 的每条边染成红色或蓝色。证明所得图必含一个三条边同色（monochromatic）的三角形。

    5 条边两色 → 至少 3 条同色（红）
    从一个顶点出发的 5 条边，按鸽巢原理至少 3 条同色，这 3 条是证明的起点。
    思路（鸽巢 + 分类）固定一点，看它的 5 条边；用鸽巢原理找出 3 条同色边，再考察这 3 条边对应端点之间的边。
    1. 取顶点 \(v\)，它有 5 条边，两色 → 至少 \(\lceil 5/2\rceil=3\) 条同色，设为红，连向 \(a,b,c\)。
    2. 看 \(a,b,c\) 三点间的三条边：若有一条红，则它与 \(v\) 的两条红边构成红三角形；若全不红，则 \(a,b,c\) 自身构成蓝三角形。两种情形都得单色三角形。

  17. (进阶 +) Ramsey 数存在性。 设 \(k,\ell\) 为正整数。证明存在一个最小的正整数 \(R(k,\ell)\)，使得：若把 \(K_{R(k,\ell)}\) 的边染红或蓝，则必出现红色的 \(K_k\) 或蓝色的 \(K_\ell\)。\(R(k,\ell)\) 称为Ramsey 数。

    思路（对 \(k+\ell\) 双重归纳）用经典递推 \(R(k,\ell)\le R(k-1,\ell)+R(k,\ell-1)\) 证明有限上界，从而最小值存在。
    1. 边界：\(R(1,\ell)=R(k,1)=1\)，\(R(2,\ell)=\ell\) 等。
    2. 归纳：在 \(N=R(k-1,\ell)+R(k,\ell-1)\) 个顶点的图中取一点 \(v\)，按它的红/蓝邻居数用鸽巢分两种情形，分别套用较小 Ramsey 数得到所需单色完全图。

  18. 三色版三角形。 把 \(K_{17}\) 的每条边染成红、蓝、绿三色之一。证明所得图必含一个单色三角形。

    思路（与第 16 题同法，鸽巢升级）这对应 \(R(3,3,3)\le 17\)。
    1. 取一点 \(v\)，它有 \(16\) 条边，三色 → 至少 \(\lceil 16/3\rceil=6\) 条同色，设为红，连向 6 个点。
    2. 这 6 个点之间若有任意一条红边，即与 \(v\) 成红三角形；否则这 6 个点之间只用蓝、绿两色，于是它们构成的 \(K_6\) 是两色染色，由第 16 题（\(R(3,3)\le 6\)）必含单色三角形。

  19. 瞬时码与前缀码。 证明：有限字母表上的一个码（code）是瞬时的（instantaneous）当且仅当它是前缀码（prefix-free，即无任何码字是另一码字的前缀）。

    思路（双向定义展开）“瞬时可译”指读完一个码字就能立即判定它结束，无需向后看。把两个定义并排，逐向推。
    1. 前缀码 ⟹ 瞬时：若无码字是别人的前缀，则一旦匹配到一个完整码字就不可能是更长码字的开头，可立刻断码。
    2. 瞬时 ⟹ 前缀码（逆否）：若某码字 \(u\) 是码字 \(v\) 的前缀，则读到 \(u\) 时无法判断是 \(u\) 结束还是 \(v\) 才开头，违反瞬时性。

  20. 禁子矩阵（avoidance）。 在为图与排列定义了“避免”概念后，对元素为 \(0/1\) 的矩阵定义避免如下：称 \(n\times n\) 矩阵 \(A\) 避免 \(k\times l\) 矩阵 \(B\)，若在 \(A\) 中找不到 \(k\) 行与 \(l\) 列，使其交出的子矩阵在每个位置都不小于 \(B\)（即 \(A\) 没有一个 \(k\times l\) 子矩阵，在 \(B\) 为 \(1\) 的每个位置上也都是 \(1\)）。设 \(f(n,B)\) 为避免 \(B\) 的 \(0/1\) 矩阵中 \(1\) 的最多个数。

    1. 求 \(f(n,B)\)，其中 \(B=(1,\ 1)\)。
    2. (进阶 +) 求 \(f(n,B)\)，其中 \(B=\begin{pmatrix}1&0\\0&1\end{pmatrix}\)。
    思路（每行/每列计数）这是 Zarankiewicz / 禁矩阵型极值问题。把约束翻译成“某种局部结构不能出现”，再逐行或逐列限制 1 的个数。
    1. (a) \(B=(1,1)\) 出现意味着某一行有两个 1。避免它就是每行至多一个 1，故 \(f=n\)。
    2. (b) \(\begin{pmatrix}1&0\\0&1\end{pmatrix}\) 是 \(2\times2\) 置换矩阵；避免它限制了 1 的“错位成对”出现。逐行分析每行 1 的列位置关系，导出线性上界 \(f(n,B)=O(n)\) 的精确常数。

  21. 非线性的反例。 上一题可能让读者猜测对所有 \(B\) 都有 \(f(n,B)=O(n)\)。但这不对。设 \[B=\begin{pmatrix}1&1&0\\1&0&0\\0&0&1\end{pmatrix}.\] 定义矩阵序列 \(A_i\)：\(A_0=1\)，\(A_1=\begin{pmatrix}1&1\\1&0\end{pmatrix}\)，且 \(A_{n+1}=\begin{pmatrix}I_{2^n}&A_n\\A_n&0\end{pmatrix}\)，其中 \(I_{2^n}\) 是 \(2^n\times2^n\) 的单位矩阵。于是 \(A_n\) 的尺寸为 \(2^{n+1}\times2^{n+1}\)。

    1. 证明 \(A_n\) 避免 \(B\)。
    2. 确定 \(A_n\) 含多少个 \(1\)，并由此推出 \(f(n,B)\ne O(n)\)。
    思路（递归结构归纳）对递归定义的矩阵，用归纳法证“避免”，并写出 1 个数的递推求解。
    1. (a) 归纳：假设 \(A_n\) 避免 \(B\)，分析 \(A_{n+1}\) 的四个分块（\(I,\ A_n,\ A_n,\ 0\)）中任意 \(B\) 形状的 1 如何分布，证明不可能拼出 \(B\)。
    2. (b) 设 \(a_n\) 为 \(A_n\) 中 1 的个数，由分块得 \(a_{n+1}=2^n+2a_n\)，解出 \(a_n\sim c\cdot 2^n\cdot n\)（含一个 \(n\) 因子），即关于尺寸 \(N=2^{n+1}\) 是 \(N\log N\) 量级，超过线性，故非 \(O(N)\)。

  22. 分块计数（上界铺垫之一）。 设 \(B\) 是 \(k\times k\) 的置换矩阵（permutation matrix），并设 \(n\) 被 \(k^2\) 整除。设 \(A\) 是一个避免 \(B\) 的 \(n\times n\) 的 \(0/1\) 矩阵，且 \(A\) 恰有 \(f(n,B)\) 个 1。把 \(A\) 切成 \(k^2\times k^2\) 的小块。证明：这些小块中至多有 \(f\!\left(\dfrac{n}{k^2},B\right)\) 个含有非零元素。

    思路（块缩成单点）把每个 \(k^2\times k^2\) 块压成“有无 1”的一个格子，得到一个 \(\frac{n}{k^2}\times\frac{n}{k^2}\) 的 0/1 矩阵 \(A'\)。
    1. 若 \(A'\) 出现了 \(B\)（即有 \(k\) 行块、\(k\) 列块的非零格子按 \(B\) 模式排列），则在原矩阵中能在每个对应块里挑出一个 1，拼出 \(B\)，与 \(A\) 避免 \(B\) 矛盾。
    2. 因此 \(A'\) 也避免 \(B\)，其 1 的个数（即非零块数）\(\le f(n/k^2,B)\)。

  23. (进阶 +) 高块与宽块。 接上题，称 \(A\) 的一个 \(k^2\times k^2\) 块为高块（tall），若它在至少 \(k\) 行中含非零元；类似地称为宽块（wide），若它在至少 \(k\) 列中含非零元。设 \(A,B\) 如上题。任取 \(A\) 的一行块，证明这 \(n/k^2\) 个块中至多有 \(\binom{k^2}{k}(k-1)\) 个是高块。再对宽块叙述并证明对应命题。

    思路（鸽巢 + 避免性）若同一行的高块太多，就能在它们里挑出 \(B\) 的某种行/列模式，违反避免性。
    1. 每个高块在它的 \(k^2\) 行中选出 \(k\) 个“有内容”的行，共 \(\binom{k^2}{k}\) 种可能的行模式。
    2. 若同一行块里出现了 \(k\) 个高块共享同一种 \(k\)-行模式，配合置换矩阵 \(B\) 的列结构即可拼出 \(B\)。故每种行模式至多出现 \(k-1\) 个高块，总数 \(\le\binom{k^2}{k}(k-1)\)。宽块对称论证（行列互换）。

  24. 置换矩阵的线性上界（Marcus–Tardos）。 利用前两题的结果证明：若 \(B\) 是置换矩阵，则 \[f(n,B)\le 2k^4\binom{k^2}{k}\,n.\] 特别地，这说明若 \(B\) 是置换矩阵，则 \(f(n,B)=O(n)\)。

    思路（合并三类块的贡献）把所有非零块分成“高块”“宽块”“既不高也不宽的小块”三类，分别估其 1 的总数，相加。
    1. 非高非宽块：每块 1 的个数 \(
    2. 高块/宽块：由第 23 题，每行（每列）块中高（宽）块数 \(\le\binom{k^2}{k}(k-1)\)，乘以行块数与每块最多 \(k^4\) 个 1。
    3. 把递推求解（主定理式展开），归纳得到题给的线性界。

  25. (进阶 +) Stanley–Wilf 猜想。 回忆 \(S_n(q)\) 表示避免模式 \(q\) 的 \(n\)-排列个数（此概念见第 4 章习题 32）。利用上一题结果证明：对所有模式 \(q\)，存在常数 \(c_q\)，使对所有 \(n\) 有 \(S_n(q)

    思路（排列↔置换矩阵）把排列写成置换矩阵，把“避免模式 \(q\)”翻译成“矩阵避免置换矩阵 \(B_q\)”，再用第 24 题的线性界换算。
    1. 避免 \(q\) 的 \(n\)-排列对应避免 \(B_q\) 的 \(n\times n\) 置换矩阵，其 1 的个数恰为 \(n\)，且由第 24 题，任何避免 \(B_q\) 的 0/1 矩阵 1 数 \(\le c\cdot n\)。
    2. 用这一稀疏性配合 Füredi–Hajnal 到 Stanley–Wilf 的标准约化（按矩阵分块计数），得到 \(S_n(q)\) 的指数上界 \(c_q^{\,n}\)。

  26. 模式拷贝数的下界（平均法）。 设 \(n\) 为正整数，\(q\) 为 \(k\)-排列，\(k\le n\)。证明存在一个 \(n\)-排列，它含有多于 \(\dfrac{\binom{n}{k}}{k!}\) 个 \(q\) 的拷贝。

    思路（平均值原理）计算所有 \(n!\) 个排列中 \(q\)-拷贝的平均个数，必有某个排列不低于平均。
    1. 固定任一 \(k\) 个位置，它们形成的模式在随机排列下等可能取 \(k!\) 种模式之一，故等于 \(q\) 的概率是 \(1/k!\)。
    2. 位置组合共 \(\binom{n}{k}\) 种，于是 \(q\)-拷贝数的期望为 \(\binom{n}{k}/k!\)。由平均值原理，存在排列其拷贝数 \(\ge\) 期望；再说明可取到严格大于。

  27. 招聘与贪心匹配。 某公司有 \(n\) 个职位待补、\(n\) 名应聘者。每位应聘者有自己的资格与要求：他可能只胜任某些职位，且对每个他感兴趣的职位有一个最低薪资期望（低于此薪资就不接受）。这些数值因人、因岗而异。无人能身兼多职。人事经理想填满全部 \(n\) 个职位，使公司总薪资成本尽可能低。

    1. 用图论语言表述经理的任务。
    2. 设经理用贪心方式补缺：先补“能以最低薪资找到合格人选”的那个职位，然后在剩下 \(n-1\) 个职位里再补这样的一个，依此类推。假设他成功补满所有职位，这种策略是否总能达到最低成本？
    思路（带权二部匹配）(a) 这是带权二部图的完美匹配最小化问题；(b) 用反例检验贪心。
    1. (a) 顶点两边分别是职位与应聘者，边表示“胜任”，边权为对应最低薪资；目标是找一个总权最小的完美匹配。
    2. (b) 贪心通常不最优。构造一个小例子（如 \(2\times2\)）：贪心先锁定一个看似便宜的边，却逼得另一边只能选很贵的边，总和反而高于另一种配法。给出这样的具体数字反例即可。

  28. (进阶 +) 拟阵交换性质。 设 \(A,B\) 是同一个图 \(K\) 的两个无圈（cycle-free，即森林）子图，且 \(A\) 的边数多于 \(B\)。证明：\(A\) 中存在一条边，可加到 \(B\) 上而使 \(B\) 仍保持无圈。

    思路（连通分量计数 / 拟阵交换公理）这是图拟阵（graphic matroid）的交换性质。用“森林的边数 = 顶点数 − 连通分量数”来推。
    1. 森林 \(F\) 上 \(e(F)=|V|-c(F)\)（\(c\) 为连通分量数）。\(A\) 边多于 \(B\) 意味着 \(A\) 的连通分量比 \(B\) 少。
    2. 于是 \(B\) 的某个连通分量被 \(A\) 的某条边“跨越”到不同的 \(B\)-分量两端；把这条 \(A\)-边加入 \(B\) 连接两个不同分量，不会产生圈。

  29. (进阶 +) 修路与最小生成树。 某县要为它的 \(n\) 个城镇修建一个连通的道路系统。调研给出了每对城镇间修直达路的造价。县长知道最便宜的连通网络应是一棵树，于是计划这样贪心地建图 \(G\)：先选可能的最便宜的一条路；再选第二便宜的一条；之后每步选还没选过、且加入后不会在已选道路图中形成圈的最便宜的路；当再也无法在不形成圈的前提下加路时停止——此时 \(G\) 已是一棵树。问：这种贪心策略是否总能给出最优结果？

    思路（Kruskal 算法的最优性）这正是Kruskal 最小生成树算法。答案是肯定的，证明的关键是上一题的“交换性质”。
    1. 设贪心得到的树为 \(T\)，任取一棵最优树 \(T^*\)。若两者不同，取它们边权排序后第一个不同处。
    2. 用第 28 题的交换性质：把 \(T\) 的那条边换入 \(T^*\)（或反之）能在不增加总造价的前提下让 \(T^*\) 更像 \(T\)。反复交换，证明 \(T\) 的造价不超过 \(T^*\)，故贪心最优。

返回 全书目录