欧拉的图论贡献：连通图 (connected graph) ，生成树 (spanning tree) 以及相关证明、归纳

引文：

"结合2棵生成树"原理:

"简单归纳"

"缩小面的归纳"

"电中性"

“ 用‘嵌入’ 法中和”

引文：

嵌入 (embedding)

将图G "嵌入" 一个平面後得到的它在该平面的一个 "嵌入" W， 则:W上的顶点一一对应G上边的端点, W中的边一一对应G上的简单弧, 并满足:

1.W中任意一条弧的端点对应G中一条边的顶点.

2.W中任意一条弧上的点和G中顶点不相关

3.W中任意两条弧的交点对应G中边的顶点.

简单弧 (simple arc)

平面内无环路连续曲线.

图的对偶(dual graph)

G*是图G的"对偶" , 则: 在平面内被图分隔开的每一个区域中取一个点, 并将这些相临区域中取得的点用边相连, 得到的图是G*.

( 对偶的性质是对称的, 用 "G*" 表示G的对偶,则G** = G)

如图: G' 与G　互相对偶.

连通图 (connected graph)

如果无向图所有顶点互相可达, 则它是连通的.

生成树 (spanning tree)

一棵遍历图所有顶点的树.

翻译的欧拉公式 V + F - E = 2 的19种证明方法

（原文： Nineteen Proofs of Euler's Formula ）

"我"的话:

1. 若论思想性、精简、严密， 原文远胜。 所以赘述， 乃体谅中文资料难求之苦。

2. 欢迎修改

注:

1> 带引号的词语, 我也不确定.

2> 斜体词语, 后面有解释,

3> 未完成

注2:

1> V + F - E = 2 是拓补学重要公式 (原型被推广到了凹多面体 V + F - E = C ): . 欧拉公式还有很多

2> 以下证明, 有三个重要的数学模型被使用, 证明中我给出了简述, 其实不严密. 有兴趣可以再查资料.

它们是: Jordan curve theorem, dual graph, graph embedding

"结合2棵生成树"原理:

对于任二维平面内 "嵌入" 的连通图G, 它的一个"对偶" 是G*.(取G中每个面的中点, 以及G外一点, 相临面各连一边成为G的 "对偶": 图G*)

我们假定: G*中由G相临面连成的边, 只被G中这两个面交线分隔. 那么:

1. G中的环,一定切断G*

2. G中的树,一定不会切断G*

(上面两个性质的证明用到拓补学的一个定理, Jordan curvetheorem: 这个定理对我们来说是没什么疑问, 简述其旨如下:

一条简单封闭曲线分平面为两部分.

但据说这个定理在数学史上的证明大费周折)

证明:

取G的生成树T, 则T不含环, 且T中边相对于G的补集 T'同样不含环 .

因为 T' 没有切断 G*, 所以 T' 的对偶仍是生成树. T的边数是 (V-1) , (T')* 的 边数与 T' 相同, 是 (F - 1)

可以证明: 这两棵生成树边数的和是G的边数: (V- 1) +(F - 1) = E

"简单归纳"

注: 作者声明自己不喜欢这样的证明.

"It is to my mind unnecessarilycomplicatedand inelegant;"

证明1:　(归纳面）

将一个图先 "嵌入" 二维平面得到图G.

当G只有一个面时 : E(1) = V(1) - 1 + F(1) - 1

当G有N个面时,

设: E(N) =V(N-1) - 1 +F(N-1) - 1

我们去除一条G中两个面的一条临边, 得到G有 N-1个面时

E(N-1) = E(N)- 1

V(N-1) = V(N)

F(N-1) = F(N)

故: E(N-1) =V(N-1) - 1 + F(N-1) - 1

丛而归纳出欧拉公式成立

证明2：（归纳顶点）

将一个图先 "嵌入" 二维平面得到图G.

当G只有一个顶点时 (一个简单环 )

F(1) + V(1) - E(1) = (E(1) + 1) + 1 - E(1) = 2

当G有N个顶点时, 假设结论成立

我们去除一条G中两个面的一条临边, 得到G有 N-1个面时 ,面和边各减少1. 故结论成立

证明3：　（归纳边）

和上面的方法一个思路

略.

"缩小面的归纳"

证明:

当凸多面体只有一个面时, V(1) + (F(1) - 1) - (E(1) - 1) = 0 显然成立.

假设当有N个面时这一性貭仍然成立. 这时我们,从凸多面体上取下一个面. 这时多面体成为了一个 "开口的容器".

我们这时在不影响面数的前提下缩小这个 "开口", 直到为一个点.于是得到一个新的凸多面体.

设这个凸多面体比原来少了 M 个顶点, 则这M个顶点在 "开口" 上,因此这个多面体比之原先, 又减少了M条边.

这样假设在N - 1 时成立

"电中性"

证明：

如图

用一种方法放置, 使图的边都不在水平面上, 这样就产生了最高点U, 最低点L. 在凸多面体的顶点放正单位电荷, 边中点放负单位电荷, 面中点放正单位电荷.

以下证明, 可以中和除了U, L所在位置外的电荷: 从上往下看, 我们让所有电荷在水平面 "逆时针" 运动一次到相临面, 那么:

1> U, L 不动 2> 不考虑U, L, 进入一个面的电荷是该面边数 e的一半减一. ( e / 2 - 1), 负电荷多一 , 其他电荷除了面中点的一个正电荷全部移出.

故除U,L 完全中和.

得证

“ 用‘嵌入’ 法中和”

和上一法不同， 我们首先得到凸多面体的在二维平面的一个 "嵌入"(embedding) ：如图： 首先, 我们旋转图使之没有一个是竖直的. 之后, 将在每个面和顶点中点上放一个正电荷， 在每条边中点上放一个负电荷。 (注意: 多面体的"嵌入", 将平面分成几个区域则原多面体有几个边, 因此图外的面上也放一个正电荷.) 下一步我们规定电荷移动的方向: (1) 移动边上的电荷到右方顶点. (2) 移动面上的电荷到面最右的顶点. (3) 图外面的正电荷不动. 这样, 除了最左边的顶点和图外的顶点上的两个电荷全部中和.