不等式证明中的图论方法：团数、谱与路径结构的应用
整理了昨天比较多人想看的“不等式证明中的图论方法”，联赛之前会优先整理代数板块的专题（手上的资料和做过的题目都相对更多一些）．
本系列文章均由我提供完整思路、所有例题，并交给GPT整理排版而成．
pdf版下载链接：不等式证明中的图论方法.pdf
本文讨论一种常见的建模视角：当一个多元不等式中的项由“哪两个指标发生关系”决定时，可以把指标看成顶点，把相应关系看成边．由此，原来的代数问题往往可转化为团数、独立集、路径、哈密顿结构或矩阵谱的估计．图论在此提供了一种整理“哪些项出现、哪些项不能同时出现”等离散关系的有效语言．
除非另有说明，本文中的图均指有限简单图；表示图 的团数，即最大完全子图的顶点数；与 分别表示邻接矩阵和图拉普拉斯矩阵．下标按模 理解时，会在相应题目中另行说明．
从约束形式选择工具
不同归一化条件通常对应不同工具：
且 固定：优先考虑边权和、团数、着色和 Motzkin–Straus 定理；
固定：优先考虑邻接矩阵、图拉普拉斯与 Rayleigh 商；
出现局部比值且有明确的“向前候选”：优先考虑有向路径与乘积链；
条件涉及任意排列中的相邻项：优先考虑哈密顿路、哈密顿圈及其平均．
关键在于使图的定义准确反映原式：先确定“顶点对应什么、边表示什么”，再确定所需控制的是团、路径、谱还是平均出现次数．
一、团数与边权和：Motzkin–Straus 定理
“方法要点 若目标式为若干非负乘积 之和，且 固定，可将出现的指标对作为边．问题随即转为顶点加权图的边权和极值；团数、着色以及等权情形下的边数都可作为控制参数．
例 1.1｜Motzkin–Straus 定理（加权形式）[1]
设 的团数为 ．非负实数 满足．证明：
并说明等号可以达到．
分析 在一组使目标函数达到最大值的权重中，若有两个不相邻的正权顶点，可将其中一个顶点的全部权重合并到另一个顶点，并选择使目标函数不减的合并方向．反复进行这一操作后，正权顶点组成一个团，问题化为固定和条件下完全图的二次型估计．
证明 记
由于可行集闭且有界，而 为连续函数，故最大值存在．在所有达到最大值的权重中，取正权顶点数最少的一组．若正权顶点 不相邻，令 ．由于 ，把 全部并入 时不会额外产生 项．不妨设 ．将 改为 、将 改为 ，其余权重不变，则 ．由于 已是最大值，必有 ；但 的正权顶点数更少，矛盾．因此正权顶点组成一个 阶团，其中 ．于是
在一个最大团的 个顶点上取 ，其余顶点取 ，等号成立．
“注 当 无三角形时 ．若总权重 ，将各权重除以 后应用上式，再乘回 ；时结论成立．因此对任意非负权重都有
特别地，时圈 无三角形，若约定 ，则
下文将这一直接推论简称为 引理．
补充：Turán 定理与等权极值
Motzkin–Straus 定理给出非负顶点权的边权和上界．取所有顶点权相等时，可得到禁完全图条件下的边数估计．记 为将 个顶点尽量均匀地分成 部（允许空部）、同部内无边而异部间全连边所得的完全 部图，并记 ．若，，则 有 个大小为 的部和 个大小为 的部，从而
Turán 定理 [2]
若 个顶点的图 不含 ，则，且等号由 取得．
证明 对参数 作强归纳．当 时图中不能有边；当 时 ，结论显然成立．以下设 且 ．若 不含 ，则对参数 应用归纳假设，得到
将 视为一个第 部为空的完全 部图．一般地，完全 部图中若两部大小相差至少 ，将较大部的一个顶点移入较小部，边数增加；反复调整后得到平衡完全 部图．因此 ． 若 含有一个 阶团 ，则每个 外顶点至多与 中 个顶点相邻．因此，至少有一个端点在 中的边数至多为
图 仍不含 ，且顶点数减少了 ，故对参数 应用归纳假设，得到
又因 与 除以 的余数相同，直接由 的公式得到
将以上两部分边数相加，即得 ．
“注 在例 1.1 中令每个顶点权均为 ，若 ，则
该式与 Turán 定理具有相同的主项，Turán 定理还给出由整数分部产生的修正项．特别地，时得到 Mantel 定理 ；相应的加权结论即前述 引理．本文中，Turán 定理作为 Motzkin–Straus 定理在等权计数问题中的补充．
二、关系图：由整除链确定团数
“方法要点 整除、包含、可比等关系本身具有组合结构．若两两相邻对应一条链，可由链长估计团数；若能分成若干同组内无边的集合，则可利用着色或直接合并各组权重．
例 2.1｜2013 Korean Mathematical Olympiad Final Round, Problem 3
设整数 ，记
非负实数 满足 ．求
的最大值．
分析 以 为顶点，当两数中较小者整除较大者时连边．目标式即所得关系图的边权和．团中的整数按递增顺序排列后形成严格整除链，而严格整除链中后一项至少为前一项的 倍．因此可先确定该图的团数，再应用例 1.1．
证明 令
若 构成一个团，则
相邻两项不同，故 ，从而
由 得 ．另一方面，构成一个 阶团，故该图的团数为 ．由例 1.1，
在 上各取权重 ，其余权重取 ，等号成立．因此最大值为
另一种证明：分组法
将 分成 组：
以及
同一组中若 ，则 ；若又有 ，则因 为不同正整数必有 ，矛盾．因此同一组中任意两个不同整数均不存在整除关系．
记
每个 的两个端点分属不同的组，故
最后一个不等式由柯西不等式 得到．取 ，其余 ，等号成立．
“注 上述分组给出了整除图的一个显式 -着色；初等证明实际上只使用“同组内无边”这一性质，并不需要知道整张图的全部边．一般地，若一个图的顶点可分成 个独立集，且各组顶点权之和为 ，则
这一估计是完全 部图情形的直接加权形式．
三、局部选边：将 项化为边权和
“方法要点 局部 或 只在有限候选中取值时，可在变量取定后保留使极值取得的候选边．所得图虽依赖于变量，但选边规则固定，因此可统一控制所有可能选边图中的三角形、完全图等局部构型．
例 3.1｜数之谜原创代数 542
给定整数 ．非负实数 满足 ．下标按模 理解．求
的最大值．
分析 对每个 ，在 中选取使最大值取得的顶点，并将 与该顶点连边．时所得无向边互不重复，因而 可写成一张简单图的边权和．接下来不必精确描述所有可能的选边图，只需控制它们的最大团即可．时会出现重边或短周期现象，必须分别计算．
证明 当 时，，故最大值为 ．
当 时，不妨记三个数为 ．则
若 ，由 得 ；若 ，由 得 ．所以最大值为 ．
当 时，令 ，于是 ．由 ，
取 时等号成立．
以下设 ．对每个 选 ，使 ，并连无向边 ．若同一条无向边被两个起点重复选中，则只能由这条边的两个端点相向选取，因此两个前进步长之和等于 ；而步长都属于 ，故 时不可能．因此所得图 有 条不同的边，且 ．当 时，只有 条边，而 有 条边，故 不含 ，从而 ．记 为圈 的平方，即循环距离不超过 的两个不同顶点之间均连边．当 时，，而 的补图恰由三条互不相交的对径边组成，所以任一团至多从每对对径点中取一个顶点，故 ．于是由例 1.1，．取 ，其余为 ，直接代回可得等号．
若 ，考察三角形的任一顶点 ，另外两点均须位于 中；两点之间的循环距离还须不超过 ．因此 中的三角形只能由三个循环连续顶点 构成．对这样的三元组，边 与 都只能由起点 选出：从另一端反向选取所需的步长分别为 与 ，均不属于 ．因此若三边同时出现，顶点 就必须同时选择两个候选点，与“每个起点只选一条边”的构造矛盾．因此 无三角形．由 引理，．取 ，其余为 ，等号成立．综上，
四、谱方法：邻接矩阵、图拉普拉斯与 DFT
“方法要点 平方和约束下的二次型适合写成矩阵形式：相邻乘积对应邻接矩阵，差分平方对应图拉普拉斯；若系数具有循环平移不变性，则可用 DFT 分离各频率．
设图 的邻接矩阵为 ，顶点上的实数写成列向量 ．由于每条无向边在 中出现两次，
记 的最大特征值为 ．由实对称矩阵最大特征值的 Rayleigh 商表征，
以下主要使用最大特征值 ．若以邻接矩阵的谱半径 表述，则由 Perron--Frobenius 定理有 ；后文不再单独使用谱半径．若只需较弱而简便的估计，由 还可得
其中 和 分别表示顶点 的度数和图的最大度数．
例 4.1｜路图上的精确极值
设 ，实数 满足
求
的最大值．
分析 目标式是路图 的边权和，而约束是平方和．这正是 Rayleigh 商最适合的情形：只需求出 邻接矩阵的最大特征值，并找出相应特征向量，即可同时得到最优常数和等号情形．
证明 设 为 的邻接矩阵．若 是特征向量，并约定 ，则
取 ，由恒等式
得到 ．边界条件 给出
由此得到 个互异的特征值
故它们恰为 的全部特征值．因此
因此
取
利用
可知这组数满足平方和为 ，且对应最大特征值．故
图拉普拉斯与差分平方
设 为度数对角矩阵，图拉普拉斯矩阵定义为 ．直接展开有
若 连通，将 的特征值按从小到大排列为
对应常向量 ．当 时，，故 Rayleigh 商给出
常称为图的代数连通度．邻接矩阵用于估计相邻顶点乘积和，图拉普拉斯用于估计相邻顶点差分平方．
循环图与离散傅里叶变换
圈图 的邻接矩阵和图拉普拉斯矩阵都是循环矩阵，可用离散傅里叶变换（DFT）同时对角化．令 ，并设
当 均为实数时，（下标按模 理解）．帕塞瓦尔（Parseval）等式为
循环移位 在第 个频率上对应乘以 ．因此，约定 ，有
由 Parseval 等式计算循环移位的内积并取实部，还得到
因此 的特征值为
而 的特征值为
例 4.2｜Fan–Taussky–Todd 离散 Wirtinger 不等式（周期型）[3]
设 ，实数 满足 ，并约定 ．证明
并确定等号情形．
分析 零和条件等价于 ．在非零频率 中，的最小值为 ．
证明 由上面的 DFT 恒等式及 ，
等号成立当且仅当傅里叶系数只可能出现在 两个频率上．对实数序列，这等价于
其中 ；时对应零序列．
“注 例 4.2 是 Fan–Taussky–Todd 离散 Wirtinger 不等式的周期型．Ky Fan、Olga Taussky 与 John Todd 在 1955 年论文 Discrete analogs of inequalities of Wirtinger中证明了周期型以及若干边界型离散不等式．其两端为零的形式为
见习题 8.4．周期型的自然基底是 DFT 的复指数函数；两端为零时相应的基底为 ，即离散正弦变换（DST）的基底，也可由长度 的奇延拓与 DFT 得到．因而例 4.1、例 4.2 与习题 8.4 都可理解为相应对称矩阵在正弦基或傅里叶基下的对角化．
五、有向路径：由局部选择构造乘积链
“方法要点 比值具有明确先后次序，且每项只有有限个向前候选时，可用有向边记录选择．候选步长的上界控制路径长度，而路径上比值相乘时中间变量相消，便于随后应用均值不等式．
例 5.1｜2019 IZhO Day 1, Problem 2[5]
求最大的实数 ，使任意两两不同的正实数 都满足
分析 因为题设中的各数两两不同，所以对正数 且 有
因此每一项都可以严格压低为两个比值中的较小者．选择分母较大的候选项，并将这一选择记为一条向前的有向边，就得到步长为 或 的路径．将路径末端与起点连接后，所取比值的乘积为 ；再用 AM–GM 不等式把“路径项数”转成“比值和的下界”．
证明 设原式为 ．循环平移下标后可设 ．舍去第一项，对 用上述基本估计；又因 最小且各数两两不同，有 、．
于是
令 ．当 时，在 与 中选择使 较大的下标 ，并令 ．设经过 次跳跃后第一次到达 ，即
每次跳跃长度为 或 ．舍去 中未被这条路径使用的正项，可得
若 ，则总前进距离为 ，而每次至多前进 ，故
此时 中沿路径的 个比值，再加上 与 ，共 项，乘积恰为 ．由 AM–GM 不等式，
若 ，则总前进距离为 ，故
舍去正项 后，沿路径的 个比值与 共 项，乘积为 ，因而
因此 ．
下面说明常数不能增大．令 ，取
并另取 ．这些数两两不同．逐项代入原式可得
故原式在题设条件下的下确界为 ，从而题目所求最大常数为 ．
“注 当局部估计产生有限个候选比值时，可将所选候选项记录为有向边．若每一步的前进距离有统一上界，则可由总距离估计路径长度；在比值型问题中，再将路径首尾连接，常可得到乘积为 的比值链，并应用 AM–GM 不等式．
六、哈密顿平均：由排列条件估计全体边权
“方法要点 任意排列中的相邻乘积和可视为完全图上一条哈密顿路的权和；循环排列对应哈密顿圈．对全体此类结构取平均，可由完全图的对称性计算每条边的出现频率．
例 6.1｜2017 IMO Shortlist A5[4]
设整数 ．实数 满足：对它们的任意排列 ，都有
求最大的实数 ，使恒有
分析 在完全图 的边 上赋权 ．每个排列对应一条哈密顿路．第一步是把“路的下界”转成“圈的下界”：若圈上有一条非负边，删去它即可．只有当所有数非零且正、负数目相等时，才可能出现每条圈边都为负的正负交替圈，因此这一情形需要单独处理．第二步再对适当的哈密顿圈取平均，利用完全图的对称性计算每条边的出现概率．
证明 记 ．先设存在零项，或正项与负项的个数不同．任一哈密顿圈上必有一条权重非负的边：若圈上没有零点且所有相邻边都为负，则顶点符号必须严格正负交替，从而正、负点数相等．删去一条非负边后得到哈密顿路，故该圈总权至少为 ．
对所有无向哈密顿圈等概率平均．一个圈含 条边，而 有 条边；由对称性，每条固定边在随机哈密顿圈中出现的概率为 ．因此平均圈权为 ，从而 ．
余下情形中，，且全部 非零，其中恰有 个正数与 个负数．写成 ，并记 ．考虑正负交替的哈密顿圈．设某一圈全部负边权绝对值之和为 ，则圈权为 ．删去绝对值为 的一条边后，所得哈密顿路权为 ，故 ．对圈上 条边求和，得到
在所有正负交替的无向哈密顿圈中等概率平均．固定一对正、负顶点；由对称性，一个给定正顶点的两个邻点在 个负顶点中均匀分布，因此这对顶点相邻的概率为 ．于是
异号边权之和为 ，同号边权均为正，于是 （此时 ）．故所有情形都有 ．
最后说明常数不能增大．取 ．若负数位于哈密顿路内部，路权为 ；若负数位于端点，路权为 ．因此这组数满足题设，而
所以
七、方法归纳
把一道不等式作图论化处理时，可按以下四个步骤展开：
确定顶点．通常一个变量、一个指标或一个离散对象对应一个顶点．
确定边的含义．边可以表示“这一乘积出现”“两个对象可比较”“这一候选被选中”或“排列中彼此相邻”．
把原式改写成图上的量．常见形式包括边权和、矩阵二次型、路径上的比值和以及哈密顿路/圈的权和．
估计所需的图参数．通常无须完全刻画图的结构；若能够控制团数、独立集分组、路径长度、最大特征值或边的平均出现概率，即可满足证明需要．
常见结构与工具的对应关系
非负权重、固定、目标是 ：用 Motzkin–Straus；若已有独立集分组，也可直接合并组内权重．
各顶点权相等、问题退化为计边：用 Turán 型极值．
整除、包含、可比等固定关系：先找团所对应的链，或找独立集所对应的分层．
局部 ：先按变量大小“选边”，再研究所有可能选边图都满足的禁构型．
固定的二次式：用邻接矩阵或图拉普拉斯；循环对称时优先考虑 DFT，路径边界则常出现正弦基．
局部比值有有限个向前候选：构造有向路径，由步长控制项数，再利用乘积消去中间变量．
任意排列的相邻项：转成哈密顿路或哈密顿圈，并对全体结构取平均．
最后还需注意三点．第一，图上的量与原式是“相等”还是仅给出“上/下界”；第二，每次使用柯西、AM–GM、Rayleigh 商或平均法时，等号条件能否同时满足；第三，若证明中出现严格不等式，最终常数通常只是上确界或下确界，需要另给逼近构造．例 5.1 的 是下确界而不是实际最小值；例 4.1、4.2 则由相应特征向量直接给出等号．
八、精选习题
下面六题分别对应团数、关系图、局部选边、谱方法、有向路径与哈密顿平均．作答时可先判断原式中的“成对关系”来自固定关系、局部选择、二次型还是排列相邻，再据此确定顶点、边及相应的归一化条件，最后估计所需图参数或矩阵特征值．
习题 8.1｜带状邻接图
设整数 满足 ，非负实数 满足 ．求
的最大值．
习题 8.2｜子集包含关系
设 ．对 的每个子集 ，给定非负实数 ，且 ．求
的最大值．
习题 8.3｜局部选边：步长 或
设整数 ．非负实数 满足 ，下标按模 理解．求
的最大值．
习题 8.4｜Fan–Taussky–Todd 不等式（两端为零）
设 ，实数 满足 且．求
的最小值．
习题 8.5｜有向路径的 候选推广
设整数 ，记 ，并设 为正实数．证明
习题 8.6｜哈密顿圈平均
设 ，为实数，并且对它们的任意排列 都有
求 可能取得的最大值．
九、习题提示与答案
8.1
在顶点集 上，若 就连边．任一团的最大、最小下标之差不超过 ，故团数至多为 ；而任意 个连续顶点构成 ．由例 1.1，最大值为
在任意 个连续顶点上各取权重 ，其余权重取 ，等号成立．
8.2
将 的每个子集作为顶点，两个不同子集可比较时连边．团对应严格包含链．集合大小每次至少增加 ，故链长至多为 ；而 达到该长度．故最大值为
在上述任意一条长度为 的最大链上各取权重 ，其余权重取 ，即可达到等号．
8.3
对每个 ，在 与 中选出权重较大的顶点并连边．时同一无向边不可能由两个端点相向重复选中．若所得图有三角形，沿三边取带符号步长 ，则三者之和是 的倍数；但其绝对值至多为 ，故只能为 ；而三个奇数之和为奇数，不可能等于 ，矛盾．因此图无三角形，例 1.1 给出 ．取 、其余为 时等号成立，所以
8.4
左端是两端为零的路径差分平方和．对应的 对称矩阵主对角线为 ，两条副对角线为 ．取
可得特征值
因此最小值为
等号在 时取得，其中 由平方和为 确定．
8.5
从 出发；当 时，在 中选取使 最大的下标 ，并令 ．于是
设经过 次跳跃后第一次进入 ．由于每次至多前进 ，而
故 ，从而 ．随后沿相邻比值依次连接至 ，再加入 ．所得闭合比值链中各项都来自原式，且中间变量全部相消，乘积为 ；其中至少包含 个跳跃比值和末项 ，故项数至少为 ．对这些正数应用均值不等式，其和至少为 ；原式其余各项均为正，因此结论成立．
8.6
对所有无向哈密顿圈等概率平均．由对称性，每条边出现的次数相同；每个圈含 条边，而 共有 条边，因此固定边出现在随机哈密顿圈中的概率为
题设说明每个哈密顿圈的边权和至多为 ，故其平均值也至多为 ．于是
取 时，每个哈密顿圈含 条权为 的边，圈权恰为 ，故上界可以达到．
说明 以下仅列出本文直接使用的经典定理原始文献及两道国际竞赛题的官方题源，供进一步查阅．
参考文献
[1] T. S. Motzkin and E. G. Straus, Maxima for Graphs and a New Proof of a Theorem of Turán, Canadian Journal of Mathematics17 (1965), 533–540.
[2] P. Turán, On the Theory of Graphs, Colloquium Mathematicum3 (1954), 19–30.
[3] Ky Fan, Olga Taussky, and John Todd, Discrete analogs of inequalities of Wirtinger, Monatshefte für Mathematik59 (1955), 73–90.
[4] International Mathematical Olympiad, Shortlisted Problems with Solutions, 58th IMO, Rio de Janeiro, 2017, Problem A5.
[5] International Zhautykov Olympiad, Mathematics Problems, 2019, Day 1, Problem 2.
留言
解法、疑问、勘误都可以说。公式用 LaTeX：行内
$…$，整行$$…$$。留言区还没开。想聊这道题，可以点上面的「在公众号查看原文」，到公众号那边留言。