组合优化与组合构造讲义 林 常 §1
组合数学题型 1
主要方法 1
I 型归纳法
定跨度:起点个数等于跨度
不定跨度:起点个数等于 1
递推关系的阶数与初始条件
II 型归纳法(最小数原理)
设 P(n)是关于正整数的命题
若由 P(n)不成立可推出存在正整数 n′1 可推出 P(n－1)成立
则 P(n)对一切正整数成立
若 P(n)对全体素数成立,且由 P(m)及 P(n)成立可推出 P(mn)成立
则 P(n)对一切大于 1 的正整数成立
若 P(n)对全体素数幂成立,且由 P(m),P(n)成立及(m,n)=1 可推出 P(mn)成立
则 P(n)对一切大于 1 的正整数成立
调整法(向较优目标逼近)
设φ : S→R 有最大(小)值(例如,当φ(S)为有限集或φ 在紧集S 上连续时)
若S的子集A 满足:对任一x∈S\A,都有x′∈S 使得 φ(x′)>(x2>… >x10,将它们沿圆周顺时针排成 a1,… ,a10 使 S=1011i iia a+=∑(a11=a1)
不妨设 a1=x1,a2
