附录五名词小词典
按在书中出现的大致顺序排列。
- 概率分布：列出所有可能的结果，给每个结果一个不小于零的机会，加起来等于 。（第四章）
- 签盒：某一种保留情况下，助手抽签用的那一盒签，也就是这种情况下各个去处被抽中的机会。两条记录都在时的那一盒叫标准签盒：十张签里电影院 张、公园 张、图书馆 张、游乐场 张。（第四章）
- 耦合：把几个给定的分布放进同一次抽签，安排它们怎样一起出现，同时保持各自的分布不变。（第五章）
- 联合分布：每张签上同时写着各栏的结果，所有签和它们的机会合在一起。（第五章）
- 边际分布：遮住别的栏，只看某一栏得到的分布。（第五章）
- 最大耦合：两个分布之间，让“两栏相同”的机会最大的耦合。（第六章）
- 全变差距离（TV）：两张表每种结果上差的绝对值之和的一半，等于单独协调两张表时变化机会的最低值。（第六章）
- 保留情况、相邻：助手的记忆清单此刻还剩哪几条记录；只差一条记录的两种情况叫相邻。（第七章）
- 答案单：为每一种保留情况各写好一个回答的一张签。删到哪种情况，就读哪一栏，不重新抽。（第七章）
- 顺序无关：最后读到的回答，只取决于最后还剩哪些记录，和删除的先后无关。（第七章）
- 图、顶点、边：一些点和点之间的连线。（第七章）
- 逐一缺失：每个顶点只排除一种回答、其余平分的一组表。（第八章）
- 出题游戏：出题人在每种情况上放一个签盒，安排人看过全部签盒以后写答案单；每种删除算一个倍数，最吃亏的那个倍数是这一局的分数。（第九章）
- 最优因子 （读作“柔”）：给定一组表时，最好的共同安排下，最吃亏那条边的倍数，也就是一局里安排人能做到的最低分。（第九章）
- 耦合常数 ：固定一张图，在所有可能的输入中最坏的最优因子，也就是出题人在这张图上能逼出的最高分。（第九章）
- 圈 ： 个顶点依次相连、首尾闭合的图。（第九章）
- 树、森林：没有圈的连通图叫树，几棵树合起来叫森林。（第十章）
- 条件概率：已知某件事发生时，在这个范围内另一件事所占的比例。（第十章）
- 并集上界：几件事至少一件发生的机会，不超过各自机会之和。（第十一章）
- 三角不等式：绕道经过第三张表，需要挪动的机会不会比直接改更少。（第十一章）
- 锐界：上界和下界相等，不能再改进。（第十二章）
- 割点、桥、块：拿掉会让图断开的顶点和边；从割点处拆出的“结实的片段”。（第十三章）
- 仙人掌图：每条边最多属于一个圈的图。（第十三章）
- 图子式单调性：删顶点、删边或合并一条边的两端，耦合常数都不会变大。（第十三章）
- 完全图 ： 个顶点两两相连的图。（第十五章）
- 层、权重 ：把概率柱横着切开，每一层由“够得着它的顶点集合”标记，同一集合的层合起来的厚度就是权重。（第十六章）
- 保持全变差的提升、共享随机映回：论文里的叫法。前者指距离不变、变回去也不会更差的切层；后者指变回去时，抽到同一个集合的顶点共用一次抽签。（第十六章）
- 分数精确覆盖、多面体 （ 读作“兰布达”）：所有合法权重组成的容器。（第十七章）
- 极点（角）：不能写成两个不同合法点混合的点。（第十七章）
- 有限极值归约：图的耦合常数等于有限张清单上各个角的最优因子中最大的那个。（第十八章）
- 行列式：解方程组时公共分母那个整数。（第十九章）
- 线性规划：在一些“一次式”条件下，让一个一次式尽量小或尽量大的问题。（第二十章）
- 原始—对偶证书：一份“做得到”的签表，加一份“做不到更好”的证明，两边数值精确相等。（第二十章）
- 超立方体 ： 条记录的全部保留情况，相差一条记录的连边。（第二十二章）
- 边连通度 （读作“卡帕”）：最少剪断几条边能让图断开。（第二十二章）
- 集中式、只看自己的表：设计安排时能看到所有顶点的表，叫集中式；每个顶点只能看到自己那张表，再加共用的随机源，叫只看自己的表。（第二十三章）
- 计时器赛跑：每种回答配一个计时器，所有顶点共用这一组，各自按自己的表调快，输出最先响的那个。（第二十三章）
- 共同门槛：只有两种回答时，所有顶点共用绳子上的同一个点，各自在自己的机会处画门槛。（第二十三章）