2008-11-08 18:11| 
22 Comments | 本文内容遵从把《三体II黑暗森林》看完后，又把上学期已经放下的Proofs from THE BOOK拿出来翻了几页。当结束了数论部分进入几何学时，一些离散性的东西让整本书陡然科学了起来。前面那篇日志里的牛B证明就是我从这本书的第9章中看到的，运用线性代数的基本定理我们居然可以证明一个无从下手的图论问题！今天我又看到牛B证明了：平面图Euler公式V+F=E+2的非数学归纳法证明。以前我见到过各种Euler公式的证明，证明方法千奇百怪，其中不乏很多独具匠心的精巧证明，但它们本质上都是运用数学归纳法不断拆边重组减低规模，将复杂的平面图一点一点变得简单。在Proofs from THE BOOK的第11章，我见到了一个用半页纸写下的巧妙证明，证明方法简单、美观而有趣，读后让人会心一笑。
在介绍这个证明之前，让我们先来回顾一下什么是Euler公式。Euler公式是说，在一个由若干顶点和它们之间的一些不相交的边所组成的图中，等式V+F=E+2总成立，其中V表示顶点个数，E表示总的边数，F表示这个图分割出来的区域个数（包括一个“外部区域”，例如一个圆把平面分割为两个区域）。如图1，这个图共有6个顶点、10条边和6个区域，可以看到6+6=10+2是成立的。为了证明这个结论，考虑这个图的任意一个生成树（图1中加粗了的边）。再考虑这个图的“对偶图”：新图的每个顶点代表原图的一个区域，原图的两个区域相邻则在新图上的两个对应顶点之间连一条边（图2中的虚线部分）。接下来，我们找出原图中那些不属于生成树的边界线，把它们在新图中所对应的边加粗（图2中的加粗虚线）。容易看出，加粗的虚线是连通的，因为原图的粗线条是一棵生成树，它没有隔离出任何一块区域；同时呢，加粗虚线是没有环的，否则它将把某个原图的顶点包起来，从而原图中的加粗线条就不可能是生成树了。只需要注意到一棵树的顶点数等于边数加一，我们的结论就直接出来了：原图的顶点数就是Euler公式中的V，它等于原图生成树的边数加一；新图的顶点数就是Euler公式中的F，它等于新生成树的边数加一；而两棵生成树的边数总和正好就是原图中的E。于是呢，我们就得到了V+F=E+2。
沙发耶～
嗯嗯，还有，我也想体验一下膜拜你的感觉～～咔咔～
严肃地膜拜一下M67大牛～～说实话昨天晚上你给我讲语概第一题的时候我真的被你震撼到了～～
我真的想知道楼上是不是M67大牛的“那什么什么”。
ls。。
别人的blog地址都留下了。。 自己去看看不就清楚了。。
发现煋了
一直很喜欢这本书，但是有些地方看不懂 = =
强啊 等有空了我也买本Proofs from THE BOOK看看
话说一直想知道你博客里的图都是用什么软件或者语言画的？
someone,楼上是托儿
您的有关分形的文章通俗易懂，我很感兴趣，能继续写一些有关三维分形的文章吗？我很想知道在三维空间中如何实现分形。谢谢。
两个问题：
1. M67牛你就是dd_engi吗？
2. M67牛你GIF格式的数学公式图是用什么画的？
容易看出，加粗的虚线是连通的，因为原图的粗线条是一棵生成树，它没有隔离出任何一块区域；同时呢，加粗虚线是没有环的，否则它将把某个原图的顶点包起来，从而原图中的加粗线条就不可能是生成树了。
这段话是否已经默认了Euler定理了呢？？
@LS 没有吧
真是很精辟的证明啊！
@10楼 问题1
{obviously} false
有个问题请教下……
最近在思考四维空间里的东西……于是发觉自己三维都没搞清楚……于是现在先反思三维的……
去看了下那个 从一到无穷大
那个双苹果是不是就是四维球？
这个证明是不是不够严格？
Matrix 有没有兴趣帮助 review 一下“雪山飞壶”这篇翻译文章的完成部分？原文到9999，才刚翻译到82，巨大的工程。
Any, that's very funny.
http://www.yeeyan.com/articles/view/xueshanfeihu/4502
好神奇!!!!
强烈赞美
DD和M67
的伟大友谊。
Orz......
哦，其实这种证法在我高中教材上面就有提示，我当时也是这么证的
[...] 证明：用F_i表示第i个面的边数。由Euler公式，面数f=e-v+2，而2e=Σ(F_i) ≥ l·r = l·(2+e-v)，可得e≤(v-2)l/(l-2) [...]
[...] http://www.matrix67.com/blog/archives/1006 Posted in Brain Storm Tags: 算法, 随记, 证明, 图论, 微积分Trackback: [...]