Euler图

究　镪镰　

◎赵希武刘海波（内蒙古师范大学计算机与信息工程学院０１００２２）　【摘要】本文通过对凸多面体的Ｅｕｌｅｒ公式与平面连　通图中Ｅｕｌｅｒ公式的对照分析．给出平面图的Ｅｕｌｅｒ公式另　一证明方法和这一公式在不是连通平面图中的推广．　【关键词】Ｅｕｌｅｒ公式；连通平面图；连通分支　１．引言　我们在中学课本中已经见到过关于凸多面体的Ｅｕｌｅｒ　公式，这个公式是由瑞士数学家欧拉（Ｅｕｌｅｒ）在１７５０年写　信给他的好友哥德巴赫（Ｇｏｌｄｂａｃｈ）时提出来的．Ｅｕｌｅｒ指出　任何一个凸多面体的顶点数　、棱数Ｅ和面数Ｆ之间存在　着以下关系式：　＋，一Ｅ：２．　事实上．欧拉公式不仅限于凸多面体，在平面连通图　中也有欧拉公式，即任何一个连通平面图Ｇ的顶点数　，　边数Ｅ和面数Ｆ之间也存在着关系式：　＋Ｆ—Ｅ＝２．　本文主要给出这个公式的另一证明方法和这一公式　在不是连通平面图中的推广．　２．Ｅｕｌｅｒ公式的另一证明方法　为了证明方便。我们给出如下引理．　引理若Ｇ是树，则Ｅ＝Ｖ一１（Ｅ，　分别表示树Ｇ的　边数和顶点数）．　证明对　用归纳法．当Ｖ＝１时，Ｇ　Ｋ。，且ｓ＝０：　—１．假设对少于　个顶点的所有树都成立，并设Ｇ是有　Ｔ，≥２个顶点的树．设　是Ｇ的一条边，因为　是Ｇ中　唯一的　，　）路，所以Ｇ一　不包含　，　）路．从而Ｇ一　不连通且ｇｏ（Ｇ一　）＝２．Ｇ一　的分支Ｇｌ和Ｇ２是无圈且　连通的，因此是树，并且　（Ｇ　），　（Ｇ。）＜Ｖ．所以，Ｅ（Ｇ　）＝　（Ｇ　）一１，对ｉ＝１，２成立．　从而Ｅ（Ｇ）＝Ｅ（Ｇ１）．４－Ｅ（Ｇ２）＋１＝Ｖ（Ｇ１）＋Ｖ（Ｇ２）一ｌ＝　Ｖ（Ｇ）一１，即Ｅ＝Ｖ一１．　定理１（Ｅｕｌｅｒ公式）若Ｇ是连通平面图，则平面图Ｇ　的顶点数　、边数Ｅ和面数Ｆ有如下关系：　＋，一Ｅ＝２．　下面给出Ｅｕｌｅｒ公式的一个新的证明方法．　证明设　＋，一Ｅ＝　．这里我们只要证明　恒不变，　且　＝２就可以了．若Ｆ＝１，则Ｇ是一棵树，这时有Ｅ＝　—　１．故　＋Ｆ—Ｅ＝２．　若Ｆ≥２，则Ｇ必然含有圈，那么我们打掉其中一个圈　上的一条边，则面数减少一个，边的条数也减少一条，这样　便有　＋（Ｆ一１）一（Ｅ一１）＝Ｖ＋Ｆ—Ｅ：　．　如此继续下去，每次图中的顶点数、面数和边数总是　保持如下关系：　顶点数＋面数一边数：　．　这样经过有限步之后，就得到了图Ｇ的一棵生成树，　这时，顶点数＝Ｖ，面数＝１，而边数＝Ｖ一１．于是得　＝２．　证毕．　３．Ｅｕｌｅｒ公式的推广　利用定理ｌ，我们便很容易推得下面结论：　定理２（Ｅｕｌｅｒ公式的推广）设平面图Ｇ的连通分支　数为ｇｏ，则有　＋Ｆ—Ｅ一　：１．　证明设平面图Ｇ的连通分支分别为Ｇ。，Ｇ：，…，Ｇ　由于Ｇ　，Ｇ：，…，Ｇ　都是连通的平面图，则根据定理１，若　设Ｇ　（　１，２，…，ｃｃ，）的顶点数为　边数Ｅ　，面数为　，就有　１＋　—Ｅ　＝２；Ｑ　２＋　—Ｅ２＝２；　②　＋　一　＝２．　⑧　而Ｖ＝Ｖ１十　２＋・－・＋　，Ｅ＝Ｅ１＋Ｅ２＋…十Ｅ　．　又Ｇ　，Ｇ　，…，Ｇ　公共的外界面，　故Ｆ＝　＋（Ｆ２—１）＋（Ｆ３—１）＋…＋（　一１）＝　＋　＋…＋　一（　一１）．　即　＋　＋…＋　＝Ｆ＋（ｏ３—１），　所以把①，②，…，　③个等式两边分别对应相加应有　ｌ十　２＋・・・＋　十　＋　＋・－・＋　一（Ｅｌ＋Ｅ２＋…＋　）＝２ｘｏ．　即得　＋Ｆ＋（　＋１）一Ｅ＝２ｗ，亦即　＋Ｆ—Ｅ一　＝１．　【参考文献】　［１］Ｊ．Ａ．帮迪，Ｕ．Ｓ＿Ａ．默蒂著．图论及其应用．吴望名，李　组念等译．北京：科学出版社，１９８７．　［２］胡美琛，邱伟德编著．组合与图．北京：人民邮电出　版社。１９８６．　

Euler积分

2009-08-20 09:58

一. Gamma函数

考虑无穷限含参积分

, 时积分收敛 . 称该积分为Euler第二型积分. Euler第二型积分定义了内的一个函数, 称该函数为Gamma函数, 记为, 即

= , .

函数是一个很有用的特殊函数 .作类似地讨论, 可得积分也在区间内闭一致收敛. 于是

可得如下结论:

的连续性: 在区间内连续 .

的可导性: 在区间内可导, 且

.

同理可得: 在区间内任意阶可导, 且

.

的递推公式 函数表: 的递推公式 : .

证

.

.

于是, 利用递推公式得:

,

,

, …………, ,

一般地有 .

可见 , 在上, 正是正整数阶乘的表达式 . 倘定义 ,

易见对,该定义是有意义的. 因此, 可视为内实数的阶乘. 这样一来, 我们很自然地把正整数的阶乘延拓到了内的所有实数上, 于是, 自然就有

, 可见在初等数学中规定 是很合理的.函数表:

很多繁杂的积分计算问题可化为函数来处理. 人们仿三角函数表、对数表等函数表, 制订了函数表供查. 由函数的递推公式可见, 有了函数在内的值, 即可对, 求得的值. 通常把内函数的某些近似值制成表, 称这样的表为函数表 . 5. 函数的延拓:

时, 该式右端在时也有

意义 . 用其作为时的定义, 即把延拓到了内.

时, 依式 , 利用延拓后的, 又可把延拓到

内 .

依此 , 可把延拓到内除去的所有点.

经过如此延拓后的的图象如[1] P347图表

常见变形有:ⅰ> 令, 有 =,

禁止复制 北京石油化工学院

Onlyunited

Euler法解常微分方程

Euler法解常微分方程算法：

Step 1 分别取积分上限、积分下限、步长

Step 2计算hnn判断bn是否成立，成立转到Step 3，否则继续进行Step 4

Step 3 计算),(1nnnnyxhfyy

Step 4 ),(1nnnnyxhfyy

Euler法解常微分方程算程序：

function euler2(fun,y0,A,h)

%fun--y'

%y0---初值

%A----x取值范围

%a----x左区间端点值

%b----x右区间端点值

%h----给定步长

x=min(A);

b=max(A);

y=y0;

while x

b=y;

y=y+h*feval(fun,x,b)

x=x+h;

end

例：用Euler法计算下列初值问题（取步长h=0.2）)6.00(1)0('2xyxyyy

输入：fun=inline('-y-x*y^2')

euler2(fun,1,[0 0.6],0.2)

得到：

y =

0.8000

y =

0.6144

y =

禁止复制 北京石油化工学院

Onlyunited

0.4613

指导教师： 年 月 日

改进Euelr法解常微分方程

改进Euler法解常微分方程算法：

Step 1 分别取积分上限、积分下限、步长

Step 2 取一个以h为步长，a，b分别为左右端点的矩阵

Step 3 （1）做显性Euler预测),(1nniiyxhfyy

（2）将1iy带入)],(),([2h111iiiiiiyxfyxfyy

Step 4计算hnn判断bn是否成立，成立返回Step 3，否则继续进行Step 5

第四章 Euler图与Hamilton图

概念、性质、定理及应用重要，需要掌握；定理证明不要求。

p71页4.2节，不要求学。

P84页，4.5节内容不要求学。

P94页，4.8、4.9节及本章之后内容不要求。

P89页，4.7只要求概念。

难点学习指导：

1. 欧拉图、欧拉闭迹概念，注意定义

定理证明不要求，注意定理1的（2），欧拉图每个顶点的度是偶数。

注意：推论里的图根据定义不是欧拉图，但是如果将两个奇点用一条线连接起来就成了欧拉图。那么欧拉迹从一个奇点到另一个奇点，这个迹不是闭迹。

2. 第4.2节不要求看。

3. 第4.3中国邮递员问题，(1)如果是欧拉图，邮递员问题就是求欧拉闭迹；(2) 如果不是欧拉图，邮递员问题就比较复杂，有些边邮递员需要重复走，但有一个原则，每个边最多重复走一次。这个时候就用到了下面定理3；

对于边带权图，P75页下面的边交换算法，可以求出最优环游。

4．若G是欧拉图，任何欧拉环游都是最优环游。如何在欧拉图中求最优环游，这就是Flerry算法：

Flerry算法的基本原理：（1）先在欧拉图中找到一点v0，找和改点连接权值最小的边，其端点为v1；（2）以此类推，尽可能不用割边，除非没有其他边可选。

5.对于边带权值的非欧拉图，那么G的任何环游通过某些边不止一次，这时就用到了p77的算法。（1）首先添加重复边使G成为一个欧拉图，这个图称为G的Euler赋权母图G*，（2）再求G*的欧拉环游。

求G*的最小权值欧拉环游如下：

在（a）图中有两个奇点，因此图（a）不是欧拉图。

要求最小权环游：(1)在图（a）中，先求从u到v权值最小的路，；（2）在该最短路上，重复每条边一次生成母图G*；（3）再求图G* 的最小权欧拉环游，

6.hamilton图（圈）定义，只考虑在一次行程中将所有点走到，再回到起点。可能一部分边没有走到。

注意，S是改图的一个点集，是改点集中点的数量，是删除改点集中的点及其相关联的边以后，图G被分成的独立图的数量。