算法引论 笔记3
20 Jul 2013 by LelouchHe
说明
本篇还是将算法引论的第二章(第二章介绍的有趣而深刻的题目好多啊~~)
有趣的问题续
独立集路径
独立集是有向图G(V,E)的节点集合,这些节点两两不相邻(节点间存在一条边即可认为相邻)
问题
有向图G(V,E)存在一个独立集S(G),使得G中每一个节点都可以从S(G)中的某一个节点通过长度不超过2的路径达到
解决
很显然,n(节点数)很小的时候命题成立,即归纳基础成立,接下来,使用归纳法来证明
首先,假设其成立,即对于$k < n$的有向图,存在这样的S(G)
然后,考虑节点数为n的情况.现在思考如何归回到归纳假设上,自然的思路是删掉1个点,假设我们删掉点v以及同v相连的边,得到图H.H的节点数为n-1,满足归纳假设,设满足条件的独立集为S(H),再来考虑被删掉的v(我们总得思考n个节点啊)
- 若$S(H) \bigcup \lbrace v \rbrace $独立,那么,归纳假设直接就成立了.S(H)到原来的n-1个点都有不超过2的路径(自然,里面没有v),而$v \in S(H) \bigcup \lbrace v \rbrace $,自然亦有此路径,所以得到$S(G) = S(H) \bigcup \lbrace v \rbrace $
- 若$S(H) \bigcup \lbrace v \rbrace $不独立,那么此时的S(G)是多少?显然,$S(H) \bigcup \lbrace v \rbrace $是不可能的了,除了v之外,其余点都满足了,v有谁来负责呢?如果这个不独立,那么必有$w \in S(H)$,且w,v相邻.有两种可能,$(w,v) \in G$即(w,v)是图的一条边,那么此时v可由w直达,距离为1,满足命题,此时$S(G) = S(H)$;但如果是相反情况,$(v,w) \in G$,就无法判断了.这里并不能指望说肯定有一条(w,v)的边的.
| 那么如何处理呢?既然(v,w)很难处理,那么干脆直接全部删除好了,设$N(v) = \lbrace v \rbrace \bigcup \lbrace w | (v,w) \in E \rbrace $,删除点时将N(v)全部删除,此时节点数仍小于n,满足假设,而之后的添加v处理,就没有了烦人的(v,w)边了,那么就可以直接推出命题了. |
最后,问题得证
加强归纳
这里用到的技术可以说是加强归纳法,即利用之前的所有case,而不仅仅是n-1这个单一的临近假设.
书上没有这么详细的说明为什么要删除N(v),我这里写的是我自己的想法,如果有错,还请包涵(不过我觉得大致如此的),同时,也可以看到,从$k = n - 1$到$k < n$的转变并不很难,只要我们瞄准一个方向,是可以一步一步的得到正确的结果.
无重边路径
如果连通无向图中的两条路径不包含相同的边,那么这两条路径就是”无重边”的
问题
G(V,E)是连通的无向图,O是V中度数为奇数的节点集合,将O中的节点分为节点对,证明对每一对节点都能找到连接它们的与其他路径无重边的路径
解决
由于问题是围绕边展开的,自然的想法是使用边进行归纳(设边数为n).当n=1时,命题显然成立(只有一条边,显然无重边).这是归纳基础,接着使用归纳法进行证明
首先,假设其成立,即命题对于所有$k < n$的连通无向图成立
然后,考虑边数为n的时候.此时如果O是空集,那么就无需证明了.反之,自然的想法是减少1条边即可回到原来的归纳假设.在O中任取两点,因为G是连通的,所以必然存在连接两点的路径,去掉这些路径,边数至少减少1,这样就回到了归纳假设.
不过,这里有一个问题,归纳假设的前提是连通无向图,但这样随意的去掉路径,很有可能导致不连通(如果这是两点间唯一路径的话),这样不满足前提了(虽然很像,但还是不满足了).这样的情况我们之前有遇到过.在独立集路径问题中,我们在归纳过程中进行了修正(还记得从删除v到N(v)的过程么?),此处也遵循类似的过程.既然连通是一个障碍,那就暂时不要连通属性
归纳假设的转化
现在的归纳假设为
- 对于边数为n的无向图,能找到度数为奇数的点集O,其中节点对见路径与其他路径无重边
去掉的连通属性,再回到原先卡壳的地方,由于没有连通性要求,分别考虑不同的独立的连通集即可.这些连通集的边数小于n,满足归纳假设.这样得证
思考
此处使用的技术是”加强归纳假设”,通过证明一个更强的归纳假设,来证明原先较弱的假设.这就是书上说的发明者悖论.
在通常的归纳法证明中,我们可以进行类似的转化,不一定变强,也可以对假设做些额外的修改.不过加强归纳假设是一个常见的转化,因为强的结论可以直接推导弱的结论,而弱的结论只能给我们推导提示,虽然还要进一步的证明才行
还是那句话,莫慌,慢慢来.
平均数定理
问题
如果$x _ i$是正整数,则下式成立:
\[(x _ 1 x _ 2 x _ 3 \cdots x _ n) ^ {\frac{1}{n}} \le \frac {x _ 1 + x _ 2 + \cdots x _ n}{n}\]分析
通常这是数学课上的朴素证明,不过这里有很多的限制,导致可以通过归纳法来证明.限制是必要的,即$x _ i$为整数,有了这个限制,就可以从归纳基础开始,推导归纳假设,直至证明结论
这里将引入一个新的归纳法变种–逆向归纳法:
- 如果命题P对某个自然数的无限子集成立,且P对n成立能推出其对n-1成立,那么P对任意自然数都成立
这个归纳十分自然,既然可以从1开始进行归纳,那么自然也可以从”最后”开始向前归纳(最后自然指的是无限远/大处)
所以,悲剧的,虽然我还没有搞清为什么这里需要”逆向归纳法”,暂时以开拓思路的初衷开始命题的证明吧
解决
一般来说,逆向归纳法倾向于首先使用普通归纳法将命题扩展到某个无限自然数子集,然后再逆向回来证明全部命题.
之所以推出去再倒回来,是因为命题对于普通归纳不直接,相反,它对于某个特定性质的子集是直接的,这样,先证明了这个子集(恩,我们的问题前进了一大步了),然后试图回退,来寻找一个好的思路
由于本题涉及到开方操作,一个自然合理的想法是利用2的幂次方来处理,因为这样会带来一系列的平方,而平方是喜闻乐见的
2幂次方归纳
现在的假设是命题对于所有的$n = 2 ^ m$都成立
显然,归纳基础是成立的,n=2时,就是简单的平方和公式.我们还使用归纳法来证明
首先,假设其成立,即对于$n = 2 ^ k$时,命题成立
然后,考虑下一个情况,即$2 n = 2 ^ {k + 1}$时,我们有
\[(x _ 1 x _ 2 x _ 3 \cdots x _ {2n}) ^ {\frac{1}{2n}} = \sqrt{(x _ 1 x _ 2 \cdots x _ n) ^ {\frac{1}{n}} (x _ {n + 1} x _ {n + 2} \cdots x _ {2 n}) ^ {\frac{1}{n}}}\]可以看到,根号里的两项满足归纳假设,这两项本身也满足归纳假设,由归纳假设就可以到处命题成立了(太长了,实在懒得再打出来了)
最后得证
这样,就证明了对于所有的2幂次方命题是成立的,这样逆向归纳的第一步无限子集已经有了,下面就是逆向过程了
逆向归纳
第一步已经给了我们归纳基础了
首先,假设其成立,即定理对于任意大的n都是成立的
然后,考虑n-1的情况.先看下试图证明的式子
\[(x _ 1 x _ 2 \cdots x _ {n - 1}) ^ \frac{1}{n - 1} \le \frac{x _ 1 + x _ 2 + \cdots x _ {n - 1}}{n - 1}\]这样的形式比较复杂,转换成合适的幂次方表达
\[x _ 1 x _ 2 \cdots x _ {n - 1} \le (\frac{x _ 1 + x _ 2 + \cdots + x _ {n - 1} }{n - 1}) ^ {n - 1}\]不等式右边同n的情况很像,只要乘以右边的一项即可
\[x _ 1 x _ 2 \cdots x _ {n - 1} \frac{x _ 1 + x _ 2 + \cdots + x _ {n - 1} }{n - 1} \le (\frac{x _ 1 + x _ 2 + \cdots + x _ {n - 1} }{n - 1}) ^ {n}\]这下不等式左边有了n项,自然我们可以使用归纳假设了,看看能否到处结论.结果很好(那是自然的),假设得证
最后命题成立
思考
这就是奇怪的逆向归纳法,性质良好的无限子集能够提供给我们证明的思路,这是一个不错的开始,尤其对于这类问题,即可以明显的看到,如果归纳变量满足一个特定性质时,可以简单的证明,那么我们就要尝试能否先证明这个特定子集的正确性,再翻过来归纳全部结果
这提示了我们,在解决问题时,如果不能全局搞定,就可以按照部分性质来一步一步的吃掉,明白了么?
常见错误
总结下这些有趣的题目,有几个容易错误的点需要指出
- 归纳基础的成立是必须证明的,而这往往和归纳假设是联系在一起的.比如我们考察了1/2/3的情况,然后草率的得出归纳基础成立是不合理的.归纳基础必须是归纳假设可以成立的前提,加入n=4的时候完全不能有3推出,而n>4时都是建立在n=4的基础上,那么这个归纳基础就是错误的.see?这就说明,不止从问题角度来看归纳基础,同时要和归纳假设的定义域情况联系到一起,防止被割裂
- 保证归纳假设在单一步骤证明中不变.归纳的很多时候,我们会自以为是的加入一些”隐性”的”事实”,比如在无重边路径问题,第一次尝试归纳时忽略了连通性要求,结果差点错误的得出结论.从后面的证明也看到,这个性质可以从归纳假设中去掉,但是此处去掉,和在证明中”不经意去掉”有本质区别.所以归纳假设可以变,但一旦决定了,就要保持下去
- 归纳步骤时,从n-1归纳n,必须是任意情况的n,即不能挑选出某一特定的情况n,来说明在普遍意义上的命题成立.在看平均数问题中时,可以看到,即使我们考虑了所有的2幂次方问题(这个选择很特殊了已经),但是还是必须经过逆向归纳才能得到整个问题.当然,换个思路,选择特定的n,可以给我们证明的思路,或者便于逆向归纳