一个难看的证明和一个漂亮的证明

    正逢考试周，抱歉这几天更新很慢。最近6天天天都有考试，今天上午考完英语后，终于有机会喘一口气了。下一次考试是后天下午的古代文学史，打算从明天开始借别人的笔记来背。今天下午先稍微休息一下。
    前几天准备考离散数学时，烦躁得真想把课本撕了。北大出的那本《离散数学教程》是我所见过的最破的教材，里面频繁出现一些诸如假设m和n怎么怎么样结果推出了p和q怎么怎么样的印刷错误；在短短三页纸中，“Peano”被拼写错了四次，而且每次错的都不一样。
    离散数学本身是相当科学的。离散数学中的证明，特别是图论证明，都是相当有趣的。但是，课本上的证明写得太丑了，符号和语言晦涩难懂，思维缺乏直观性和启发性。于是呢，我深刻体会到了这个Blog存在的必要性。我非常反对缺乏直观思维方式的证明过程。一个合格的教科书需要在严格的形式证明之外附上一段证明思路的直观描述。大家或许注意到了，我在写Blog时很不愿意定义变量，能用自然语言描述的地方就尽可能用自然语言来说。在介绍种种精妙的趣题和证明时，我往往会改变证明步骤的顺序和语言表述的方式，以顺应人的直观思维方式；否则，证明的巧妙性和启发性很难被表现出来。


    有趣的是，证明的美观性很可能与实际采用的证明方法完全无关。本质相同的两种证明方法，用不同的思维去考察，用不同的文字去讲述，效果可能完全不一样。不妨让我们来看一看《离散数学教程》是如何证明完全图K_5和完全二分图K_3,3不是平面图的。

定理：设G是连通平面图，顶点数为v，边数为e，G的各面的边数至少是l，则e≤(v-2)l/(l-2)
证明：用F_i表示第i个面的边数。由Euler公式，面数f=e-v+2，而2e=Σ(F_i) ≥ l·f = l·(e-v+2)，可得e≤(v-2)l/(l-2)
 
推论：完全图K_5和完全二分图K_3,3都不是平面图
证明：(1)由于K_5是简单图，所以l=3，于是10=e≤(v-2)l/(l-2)=(5-2)·3/(3-2)=9，矛盾；
       (2)由于K_3,3没有奇数环，所以l=4，于是9=e≤(v-2)l/(l-2)=(6-2)·4/(4-2)=8，矛盾。

 
    再来看一看来自Proofs from THE BOOK第11章中的证明：

显然，所有面所拥有的平均边数为2e/f。
 
K_5中有5个顶点、10条边。若它是平面图，则它应该有10-5+2=7个面，于是每个面平均拥有20/7条边。这说明该图中至少存在一个边数小于3的面，但对于一个简单图来说这是不可能的。
 
类似地，K_3,3中有6个顶点、9条边。若它是平面图，则它应该有9-6+2=5个面，于是每个面平均拥有18/5条边。这说明该图中至少存在一个边数小于4的面，但对于一个二分图来说这是不可能的。

21 条评论

发表评论




Enter Captcha Here :