1 第 10 章教材习题：题意释义与通用解题方法

本节不是逐题完整解答。 它为每个教材编号习题提供经页面核验的题意释义（Problem）、主题标签（Topic），以及本章层面的通用解题方法导引。本公开仓库不分发教材原图、转移表、边权与长表达式，因此具体数值、状态名与表达式需结合教材对应原页数据自行推导。同一类题的“方法导引”会重复出现，它说明的是解题思路，而不是该题的具体答案。

本章共收录 18 个教材编号习题。

1.1 习题 10.1.1

Source: textbook PDF p.309

Problem（教材题意释义）

修改图 10-1 的边权，重新求可能的最小生成树。

Topic

最小

方法导引（通用，非本题具体答案）

把教材页中的状态、边、权值或产生式先完整抄成一个有限表，然后严格按本章算法逐步计算；不要凭图形直觉跳步。 本题的可复现做法是：①列出源对象；②执行相应算法（状态消除/可区分表/PDA 的 ID 推演/CFG 推导/PCP 搜索等）；③每一步记录新状态、集合或配置；④用接受条件或不变量核对最终结果。 由于公开版不直接复制教材图表，精确的状态名、边权和表项以所标 PDF 页为准；算法步骤在这里完整给出，学习时可逐行对照源页复算。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.2 习题 10.1.2

Source: textbook PDF p.309

Problem（教材题意释义）

在图 10-1 增加一条权 19 的边，重新求最短哈密顿回路。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

把教材页中的状态、边、权值或产生式先完整抄成一个有限表，然后严格按本章算法逐步计算；不要凭图形直觉跳步。 本题的可复现做法是：①列出源对象；②执行相应算法（状态消除/可区分表/PDA 的 ID 推演/CFG 推导/PCP 搜索等）；③每一步记录新状态、集合或配置；④用接受条件或不变量核对最终结果。 由于公开版不直接复制教材图表，精确的状态名、边权和表项以所标 PDF 页为准；算法步骤在这里完整给出，学习时可逐行对照源页复算。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.3 习题 10.1.3

Source: textbook PDF p.309

Problem（教材题意释义）

假设某 NP 完全问题有 O(n^{log n}) 的确定算法，推导对 NP 中任意问题复杂度意味着什么。

Topic

NP

方法导引（通用，非本题具体答案）

先确定每个变量的语义，再写产生式并用双向正确性证明。构造型题通常把计数相等、嵌套或分段选择交给不同变量；推导题严格区分最左推导与最右推导。 正确性证明分两部分：由产生式归纳证明每个生成串都满足目标性质（soundness）；再对任意满足性质的串按长度或结构归纳，展示如何选择第一条产生式并递归生成剩余部分（completeness）。 若要求无歧义，还要说明每个串的第一条产生式/主运算符由字符串结构唯一决定。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.4 习题 10.1.4

Source: textbook PDF p.310

Problem（教材题意释义）

研究 n 维 m 网格图的哈密顿回路存在条件并证明教材给出的实例结论。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.5 习题 10.1.5

Source: textbook PDF p.310

Problem（教材题意释义）

对两个 CFG 编码语言 L1,L2 构造双向多项式归约，并由此判断其 NP 完全性关系。

Topic

CFG；NP

方法导引（通用，非本题具体答案）

先确定每个变量的语义，再写产生式并用双向正确性证明。构造型题通常把计数相等、嵌套或分段选择交给不同变量；推导题严格区分最左推导与最右推导。 正确性证明分两部分：由产生式归纳证明每个生成串都满足目标性质（soundness）；再对任意满足性质的串按长度或结构归纳，展示如何选择第一条产生式并递归生成剩余部分（completeness）。 若要求无歧义，还要说明每个串的第一条产生式/主运算符由字符串结构唯一决定。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.6 习题 10.1.6

Source: textbook PDF p.310

Problem（教材题意释义）

证明 P 对反转、并、连接、星、逆同态、补等操作封闭。

Topic

封闭

方法导引（通用，非本题具体答案）

从已有自动机/文法构造新的识别器。对商与导数，保留原 DFA 的转移图并改变接受条件或起始集合；对 init，把能到达原接受态的状态设为接受态；对 cycle 可猜测切分点并用有限状态记录两个阶段。 对 half/alt 等操作，关键是同时模拟原自动机并在有限控制中记录位置奇偶或同步关系。 若题目要求反例，则选一个已知非正则/非 CFL 的目标语言，并构造简单语言使该运算结果恰好等于目标语言，从封闭性矛盾得证。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.7 习题 10.1.7

Source: textbook PDF p.310

Problem（教材题意释义）

证明 NP 对 10.1.6 中除补以外的运算封闭，并解释补为何等价于 NP=coNP 的开放问题。

Topic

封闭；NP

方法导引（通用，非本题具体答案）

从已有自动机/文法构造新的识别器。对商与导数，保留原 DFA 的转移图并改变接受条件或起始集合；对 init，把能到达原接受态的状态设为接受态；对 cycle 可猜测切分点并用有限状态记录两个阶段。 对 half/alt 等操作，关键是同时模拟原自动机并在有限控制中记录位置奇偶或同步关系。 若题目要求反例，则选一个已知非正则/非 CFL 的目标语言，并构造简单语言使该运算结果恰好等于目标语言，从封闭性矛盾得证。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.8 习题 10.2.1

Source: textbook PDF p.317

Problem（教材题意释义）

对两个具体布尔表达式计算可满足赋值数量，并判断是否属于 SAT。

Topic

SAT

方法导引（通用，非本题具体答案）

证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.9 习题 10.2.2

Source: textbook PDF p.317

Problem（教材题意释义）

用变量 x_ij 编码四顶点图，写布尔公式表达哈密顿回路、连通、含三角形、含孤立点等性质。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.10 习题 10.3.1

Source: textbook PDF p.325

Problem（教材题意释义）

把三个布尔表达式转换为等可满足的 3-CNF。

Topic

CNF

方法导引（通用，非本题具体答案）

按固定顺序转换以避免重新引入已消除结构：先删除无用符号，再处理 ε 产生式（必要时保留新起始符），再消单位产生式，最后把长右部二叉化并把终结符替换成专用变量。 CNF 最终只允许 A→BC 或 A→a（以及必要时 S→ε）。GNF 则继续消除左递归并按变量顺序替换，使每条产生式以终结符开头。 每一步都说明语言保持关系；如果原语言含 ε，要单独处理 ε。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.11 习题 10.3.2

Source: textbook PDF p.325

Problem（教材题意释义）

定义 4TA-SAT：至少四个可满足赋值；证明它 NP 完全。

Topic

NP；SAT

方法导引（通用，非本题具体答案）

证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.12 习题 10.3.3

Source: textbook PDF p.325

Problem（教材题意释义）

分析特殊 3-CNF E_n（对每组三个变量含两个互补子句）在 n=4、5 时是否可满足。

Topic

CNF

方法导引（通用，非本题具体答案）

按固定顺序转换以避免重新引入已消除结构：先删除无用符号，再处理 ε 产生式（必要时保留新起始符），再消单位产生式，最后把长右部二叉化并把终结符替换成专用变量。 CNF 最终只允许 A→BC 或 A→a（以及必要时 S→ε）。GNF 则继续消除左递归并按变量顺序替换，使每条产生式以终结符开头。 每一步都说明语言保持关系；如果原语言含 ε，要单独处理 ε。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.13 习题 10.3.4

Source: textbook PDF p.325

Problem（教材题意释义）

给 2SAT 的多项式时间算法，并证明正确性。

Topic

SAT

方法导引（通用，非本题具体答案）

证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.14 习题 10.4.1

Source: textbook PDF p.336

Problem（教材题意释义）

研究 CLIQUE：读图求最大 k、k 团边数，并由顶点覆盖归约证明 NP 完全。

Topic

NP

方法导引（通用，非本题具体答案）

证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.15 习题 10.4.2

Source: textbook PDF p.336

Problem（教材题意释义）

补全从 3SAT 到图着色的归约，证明 k-着色 NP 完全。

Topic

NP；SAT

方法导引（通用，非本题具体答案）

证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.16 习题 10.4.3

Source: textbook PDF p.338

Problem（教材题意释义）

对图 10-14 手工求哈密顿回路、最大独立集、最小顶点覆盖、最小边覆盖、2-着色性。

Topic

最小

方法导引（通用，非本题具体答案）

把教材页中的状态、边、权值或产生式先完整抄成一个有限表，然后严格按本章算法逐步计算；不要凭图形直觉跳步。 本题的可复现做法是：①列出源对象；②执行相应算法（状态消除/可区分表/PDA 的 ID 推演/CFG 推导/PCP 搜索等）；③每一步记录新状态、集合或配置；④用接受条件或不变量核对最终结果。 由于公开版不直接复制教材图表，精确的状态名、边权和表项以所标 PDF 页为准；算法步骤在这里完整给出，学习时可逐行对照源页复算。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.17 习题 10.4.4

Source: textbook PDF p.338

Problem（教材题意释义）

证明一批问题 NP 完全：子图同构、反馈边、整数线性规划、支配集、消防站、半团、单位时间调度、恰当覆盖、背包。

Topic

NP

方法导引（通用，非本题具体答案）

证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。

1.18 习题 10.4.5

Source: textbook PDF p.338

Problem（教材题意释义）

证明有向/无向哈密顿通路以及受叶数/度数限制的生成树问题 NP 完全。

Topic

NP

方法导引（通用，非本题具体答案）

证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。

Common mistakes

• 跳过量词、边界条件或接受方式；
• 把“存在一种构造”误写成“任意构造都成立”；
• 图表题未先准确抄录源数据就直接计算。