第三章欧拉图与哈密顿图
（七桥问题与一笔画，欧拉图与哈密顿图）
教学安排的说明
章节题目：§3.1环路；§3.2 欧拉图；§3.3 哈密顿图
学时分配：共2课时
本章教学目的与要求：认识七桥问题的实质，理解一笔画问题的解决方法，会正确理解关于欧拉图和哈密顿图的判断定理，并进行识别．
其它：由于欧拉图与一笔画问题密切相关，因此本章首先从一笔画问题讲起，章节内容与教材有所不同。
课堂教学方案
课程名称：§3.1环路；§3.2欧拉图；§3.3哈密顿图
授课时数：2学时
授课类型：理论课
教学方法与手段：讲授法
教学目的与要求：认识七桥问题的实质，理解一笔画问题的解决方法，会正确理解关于欧拉图和哈密顿图的判断定理，并进行识别．
教学重点、难点：
（1）理解环路的概念；
（2）掌握欧拉图存在的充分必要条件；
（3）理解哈密顿图的一些充分和必要条件；
教学内容：
看图1，有点像“回”字，能不能从某一点出发，不重复地一笔把它画出来？这就是中国民间古老的一笔画游戏，而这个图形实际上也是来源于生活。中国古代量米用的“斗”?上下都是四方的，底小口大，从上往下看就是这样的图形。
这类“一笔画”问题中最著名的当属“哥尼斯堡七桥问题”了。
一、问题的提出图1
哥尼斯堡七桥问题。18世纪，哥尼斯堡为东普鲁士的首府，有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥联结起来，见图2（1），当时那里的居民热衷于一个难题：游人怎样不重复地走遍七桥，最后回到出发点。1735年，一群执着好奇的大学生写信请教当时正在圣彼得堡科学院担任教授的著名数学家欧拉。欧拉通过数学抽象成功地解决了这一问题。欧拉发现欧几里得几何并不适用于这个问题，因为桥不涉及“大小”，也不能用“量化计算”来解决。相反地，这问题属于提出的“位置几何”。欧拉想到，岛与河岸陆地仅是桥梁的连接地点和通往地点，桥仅是从一地通往另一地的路径，一次能否不重复走遍七桥与河岸陆地大小是没有
本质联系的，与桥的宽窄也是没有关系的。所以，相对问题而言，可舍弃之，而仅考虑与问题有密切联系的本质特征：岛和岸地可以是仅有位置而没有大小的“点”，桥梁可以是仅有连接作用而没有宽窄的连接两点的线，那么可以把这四处地点用A,B,C,D四个点来表示，同时将七座桥表示成连结其中两点的七条线，就得到这样一张图．于是，欧拉建立了一个数学模型，一个人不重复地走遍所有的七座桥，就相当于从图中某一点出发，不重复地一笔画出图来．这样，“七桥问题”就转化为“一笔画”问题了。
欧拉注意到，如果一个图能一笔画成，那么一定有一个起点开始画，也有一个终点。图上其它的点是“过路点”——画的时候要经过它。
这些点有什么特征呢？先来看看“过路点”，它应该是“有进有出”的点，有一条边进这点，那么就要有一条边出这点，不可能是有进无出，如果有进无出，它就是终点，也不可能有出无进，如果有出无进，它就是起点。因此，在“过路点”进出的边总数应该是偶数。
如果起点和终点是同一点，那么它也是属于“有进有出”的点，因此必须连着偶数条边，这样图上所有点都连偶数条边。
如果起点和终点不是同一点，那么这两点连有奇数条边，这也是图中仅有的连着奇数条边的点。
现在对照七桥问题的图，B点连有3条边，A点连有5条边，C点D点各连3条边，哥尼斯堡七桥问题就变成了图2(2)中，是否存在经过每条边一次且仅一次，经过所有的顶点的闭链问题了。所以欧拉得出的结论是这个图肯定不能一笔画成，也就是说要想不重复的走遍这七座桥是不可能的。1736年瑞士数学家欧拉（Euler）发表了图论的第一篇论文“哥尼斯堡七桥问题”。欧拉在论文中指出，这样的闭链是不存在的。
图2
欧拉解决问题的关键是两步，先从实际问题中抽象出形式结构，再对形式结构进一步分析，抽象出其本质数量特征，由此得出判别准则，问题获得答案。哥尼斯堡七桥问题的解决远远超出了它的娱乐价值，欧拉用了最简单的图形——点和线，把一个实际问题抽象成数学问题，巧妙地彻底解决了“七桥问题”。这充分显示了数学抽象的形式化和量化特征。由此提出的新思想开辟了数学的一个新的领域——图论，同时也为拓扑学的研究提供了一个初等的例子。此后许多著名的数学游戏成为图论和拓扑学发展的催化剂和导引，如哈密顿问题（绕行世界问题）、四色猜想等。直到20世纪中期，这两门学科才逐步完善并迅速发展。
二、欧拉图
定义1给定图G=
欧拉图另一定义：如果图G的所有点均为偶数，则称图G为欧拉图。
实际上，在图中，如果所有的边可以排起来而不重复，则该图为一链，或者是开链，或者是闭链，当是开链时，链中的点为偶数度，起点和终点皆为奇数度。当是闭链时，链中的点皆为偶数度。
定理1：无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。
证明：设G为一欧拉图，那么G显然是连通的。另一方面，由于G本身为一闭路径，它每经过一个顶点一次，便给这一顶点增加度数2，因而各顶点的度均为该路径经历此顶点的次数的两倍，从而均为偶数。反之，设G连通，且每个顶点的度均为偶数，欲证G为一欧拉图。为此，对G的边数归纳。当m = 1时，G必定为顶点的环，如图3（a）所示，显然这时G为欧拉图。设边数少于m的连通图，在顶点度均为偶数时必为欧拉图，现考虑有m条边的图G。设想从G的任一点出发，沿着边构画，使笔不离开图且不在构画过的边上重新构画。由于每个顶点都是偶数度，笔在进入一个顶点后总能离开那个顶点，除非笔回到了起点。在笔回到起点时，它构画出一条闭路径，记为H。从图G中删去H的所有边，所得图记为G’，G’未必连通，但其各顶点的度数仍均为偶数（为什么？）。考虑G的各连通分支，由于它们都连通，顶点度数均为偶数，而边数均小于m，因此据归纳假设，它们都是欧拉图。此外，由于G连通，它们都与H共有一个或若干个公共顶点（如图3（b）所示），因此，它们与H一起构成一个闭路径。这就是说，G是一个欧拉图。
(a)
图3
三、一笔画问题。
要求笔不离纸，而且每条线只画一次，不准重复。显然哥尼斯堡七桥问题是一笔画问题。对于图来说，如果全部边（或有向边）可以排成一条链，则称这个图为一个一笔画。
下列图形能否一笔画成?
图4
定理2设G 是无向连通图，则G 是一笔画?G 中只有0或2个奇数度顶点（他们分别是起点和终点）。即：
一笔画0???
奇数顶点的个数为即全为偶数度，闭链，欧拉图奇数顶点的个数为2开链 证明：设G 的链是点边序列011221k k k v e v e v v e v -，其中顶点可能重复，但边不重复。 对于任一非端点顶点i v ，在欧拉路中每当i v 出现一次，必关联两条边，故i v 虽可重复出现，但是()deg i v 必是偶数。对于端点,若0k v v =，则()0d e g v 必是偶数，即G 中无奇数度顶点 。若 0k v v ≠，则()0deg v 必是奇数，()deg k v 必是奇数,即G 中有两个奇数度顶点 。上述定理的逆定理也成立，即：
定理3：设G 是无向连通图， G 中只有0或2个奇数度顶点?G 是一笔画。此定理分两步证：奇数度顶点是0，奇数度顶点是2。
证明思路：只证明奇数度顶点是0 的情形，(证明过程给出了一种构造方法)
（1）首先证明任取G 中点0v ，必存在包含0v 的圈。由于G 中点为偶数度,则从其中一个顶点开始构造一条圈,即从0v 出发经关联边1e 进入1v ,则必可由1v 再经关联
边2e 进入2v ,如此下去,每边仅取一次,必存在到达0v 的圈,01122
10k k v e v e v v e v -（否则便与G 中点为偶数度矛盾）
（2）若P: 01122
10k k v e v e v v e v -通过了G 的所有边, P: 0112210k k v e v e v v e v -就是一条闭链。
（3）否则，若G 中去掉P: 0112210k k v e v e v v e v -后得到子图G ',则G '中每个顶点
度数都为偶数,因为原来的图G 是连通的,故P: 01122
10k k v e v e v v e v -与G '至少有一个顶点i v 重合,在G '中由i v 出发重复(1)的方法,得到闭链L 。
(4)当P 与L 组合,若恰是G ,得欧拉路,否则重复(3),可得闭链M,依此类推可得一条欧拉路。
奇数度顶点是2的情形可类似证明。
因此，定理2与3可总结为
设G 是无向连通图， G 中只有0或2个奇数度顶点?G 是一笔画。
例1：下列图5中各图是否可以一笔画出？
图5
解：(1)有 个奇度顶点，无欧拉闭链或通路，不能一笔画成。
(2)与(3)都是
个奇度顶点，其余均为偶度顶点，具有欧拉通路，可一笔画成。 (4)均为偶度顶点，具有欧拉通路，可一笔画成。
例2、“两只蚂蚁比赛问题”。两只蚂蚁甲、乙分别处在图 6左图
中的顶点 处，并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点
处。如果它们速度相同，问谁最先到达目的地？
解：图 中，有两个奇度顶点 ，因此存在从 到 的开链，蚂蚁乙走到只
要走一条欧拉通路，边数为
，而蚂蚁甲要想走完图中所有边到达 ，至少要先
一条边到达 ，再走一条欧拉通路，故它至少要走 条边到达 ，所以乙必胜。
例3:甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？
图中A，C为奇点，其余都是偶点。甲从A点出发，可以不重复到达C点。乙从B出发一定会走重复的路，所以甲先回到邮局。
例4图6右图是一个公园的平面图，能不能使游人走遍
每一条路不重复？入口和出口又应
设在哪儿？
H点和B点是奇点，其余都是
偶点，所以入后和出口应设在H点
和B点。
图6
四、中国邮递员问题
一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．
用图论的述语，在一个连通的赋权图G（V，E）中，要寻找一条闭链，使该闭链包含G中的每条边至少一次，且该闭链的权数最小．也就是说要从包含G的每条边的闭链中找一条权数最小的闭链．
如果G是欧拉图，则很容易由弗罗莱算法求出一个欧拉闭链，但是若G不是欧拉图，即存在奇度数的顶点，则中国由递员问题的解决要困难得多．本节的主要目标是给出在有奇度数顶点的连通图中寻找最小权数的闭链的方法．首先注意到，若图G有奇数度顶点，则G的奇数度顶点必是偶数个．把奇数度顶点分为若干对，每对顶点之间在G中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E ．令G/=G+E/，即把附加边子集E/叠加在原图G上形成一个多重图G/，这时G/中连接两个顶点之间的边不止一条．显然G/是一个欧
拉图，因而可以求出G /的欧拉闭链．该欧拉闭链不仅通过原图G 中每条边，同时还通过E / 中的每条边，且均仅一次．邮递员问题的难点在于当G 的奇数度顶点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集E / 的权数ω(E / )为最小？为此有下列定理．
定理 4 设G （V ，E ）为一个连通的赋权图，则使附加边子集E / 的权数ω(E / )为最小的充分必要条件是G+E / 中任意边至多重复一次，且G+E / 中的任意闭链中重复边的权数之和不大于该闭链总权数的一半．
证明： 必要性．用反证法．设存在一种奇顶点集的配对，使其附加边子集E / 权数 ω(E / )为最小．若 G+E / 中有一条边重复n n () 2次，由于G+E /为欧拉图，所以删去相应的二次重复边后仍为欧拉图．这样，相应的附加边子集的权数将减小，这与 ω(E /)为最小的假设矛盾．这说明E /中的边均互不相同．
其次，若G+E / 中存在一个闭链，使它的重复边的权数之和大于该闭链总权数的一半，则在E / 中删去这些重复边（注意：这些边均在E /中），而代之以该闭链的其余部分的边再重复一次．经过这种替代后所得到的边子集E //仍为附加子集，且ω(E //)<ω(E /)，又产生矛盾．
充分性．设有两个附加边子集E /和E //，均使G+E /和G+E //中每条边至多重复一次，且每个闭链中的重复边的权数和不大该闭链权数的一半，我们来证明ω(E /)=ω(E //)．首先注意到，由E /和E //不相同的部分组成的图（记为]\[//////）（E E E E G ）是由一个或若干个欧拉子图所组成的．这是因为E /＋E //中每个顶点的度数均为偶数，而E /和E //的公共边数也是偶数，故
]\[//////）（E E E E G 中每个顶点的度数仍为偶数，
所以它若为连通图时是一个欧拉图；若为非连通图时则由若干个欧拉子图组成．
]\[//////）（E E E E G 的任何闭链都由E /和E //中的边组成，而E /和E //在闭链中的权数分别不大于该闭链权数的一半，因而任何闭链中属于E /中的权数之和与属于E //中的边数之和必定相等，所以ω(E /)=ω(E //)．它就是最优附加边子集的权数，即E /和E //均为使附加边子集的权数达到最小的最优附加边子集．
由定理4可得一个寻找邮递员问题最优解的方法．现举例如下：
例5已知邮递员要投递的街道如图7左图所示，试求最优邮路．
图7
解 先找出奇顶点：A 1，A 2，A 3，A 4，B 1，B 2，B 3，B 4．奇顶点进行配对，不妨把A 1与B 1，A 2与B 2，A 3与B 3，A 4与B 4配对，求其最短路．显然它不是最优解．下面我们根据定理4来进行调解．
第一次调整：删去多于一条的重复边，即A 3与B 3，A 4与B 4中的（A 4，B 3）．调整后，实际上成为A 1与B 1，A 2与B 2，A 3与A 4，B 3与B 4的配对，它们的最短路如图7右图所示．
第二次调整：发现在闭链{A 1，A 2，B 2，A 4，B 3，B 4，B 1，A 1}中重复边的权数和为11，大于该闭链权数20的一半．因而调整时，把该闭链的重复边删去，代之以重复其余部分，得图8左图．可以看出，实际上是调整为A 1与A 2，B 1与B 4，A 3与A 4，B 2与B 3配对
图8． 第三次调整：在图8左图中发现闭链{ A 3，A 4，B 2，A 3}中重复边的权数和为7，大于该闭链权数10的一半，因而删去原重复边（A 3，V 2，A 4）和（A 4，B 2），而添加（B 2，A 3），得到图8右图．进行检查发现，既没有多于一条的重复边，也没有任何闭链使其重复边的权数之和大于该闭链的一半，因此图8右图就是最优的附加边子集E /，而G+E /为欧拉图，可由弗罗莱算法找出最优邮路．
在现实生活中，很多问题都可以转化为中国邮递员问题，例如道路清扫时如何使开空车的总时间最少的问题等等．上面例1题所用的求最优邮路的方法叫“奇偶点图上作业法”．因为此方法要验证每个闭链，很不方便，Edmods和Johnson在1973年提出一种比较有效的方法，有兴趣的读者可参考有关资料．
例11.24中国邮路问题
中国邮路问题是我国数学家管梅谷先生在20世纪60年代提出来的。该问题描述如下：一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短？
下面用图论的语言来描述：用图论的语言来描述，即在一个带权图G中，能否找到一条回路C，使C包含G的每条边最少一次且C的长度最短？
该问题求解思路大体包括三个方面：
1) 若G没有奇数度结点，则G是欧拉图，于是欧拉回路C是唯一的最小长度的投递路线。
2) 若G恰有两个奇数度结点vi和vj，则G具有欧拉迹，且邮局位于结点vi，则邮递员走遍所有的街道一次到达结点vj；从vj返回vi可选择其间的一条最短路径。这样，最短邮路问题转化为求vi到vj的欧拉迹和vj到vi的最短通路问题。
3) 若G中奇数度结点数多于2，则回路中必须增加更多的重复边(路径）。这时，怎样使重复边的总长度最小？已有定理给出了判定条件，读者若有兴趣则请查阅相关文献。
五、哈密顿图
哈密顿图的理论是著名的货郎担问题的源头。哈密顿图起源于一种游戏，它是由英
国数学家哈密顿于1859年提出的“周游世界游戏”，它用一个正十二面体的20个顶点代替20个城市(图9（1）)，这个正十二面体同构于一个平面图(图9(2))，要求沿着正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点，这个游戏曾风靡一时，它有若干个解，称为哈密顿图。
a(甲)
b(乙 c
图9
这个游戏扩展到一般的图上就是：给定一个图，是否能找到一个环，它通过图G的每个结点一次且仅一次?
哈密尔顿的十二面体图上存在一条哈密尔顿环，按照结点编号的顺序：1-2-3…20-1。与欧拉图不同，确定一个图是否为哈密尔顿图是很困难的，目前还不存在有效的算法。但许多哈密尔顿图的充分条件都被证明,这里介绍其中的两个，其证明过程具有较好的示范意义，而且在研究哈密尔顿图的性质中得到了广泛的应用。
图10.31
定义2：给定图G，若存在一条路经过图中的每个顶点恰好一次，这条路称作哈密顿路(hamilton walk)。若存在一条圈经过图中的每个顶点恰好一次，称作哈密顿圈，具有哈密顿圈的图称为哈密顿图（hamilton graph）。
注意哈密顿图、哈密顿通路与欧拉图、欧拉路径之间的区别。它们之间几乎没
有什么联系。有的图既是哈密顿图又是欧拉图，有的图只是哈密顿图不是欧拉图，有的图只是欧拉图不是哈密顿图，有的图则两者皆非。特别要留意的是, 哈密顿图并不要求其哈密顿回路遍历图的所有的边,仅仅要求遍历图的所有的顶点. 例6、判断下图是否具有哈密顿闭链，通路。
图10
解：(1) 存在哈密顿通路，但不存在哈密顿闭链。
(2) 是哈密顿图，存在哈密顿闭链和通路。
(3) 不存在哈密顿闭链，也不存在哈密顿通路。
哈密顿图的判定
虽然至今尚未找到一个像欧拉图的充要条件那样的“非平凡的”（不是定义的同义反复）关于哈密顿图、哈密顿通路的充分必要条件，但关于它们的充分性和必要性分别有一些研究成果。简单现介绍如下
定理5：若图(),G V E =具有哈密顿圈，则对于顶点集V 的每个非空子集S 均有()k G S S -≤成立。其中()k G S S -≤是G S -中连通分支数。（该定理用于证明某些图不是哈密顿图）
证明思路:链c 删1个顶点变成路，但仍连通,删2个顶点至多增加1个分支(删端点处的顶点不增加分支),依此类推。所以,增加的分支数不大于删除的顶点数|s|。 定理6：设图G 具有n 个顶点的简单图,如果G 中每一对顶点度数之和大于等于n-1,则G 中存在一条哈密顿路。
证明思路：1) 先证G 连通:
若G 有两个或多个互不连通的分支,设一个分图有1n 个顶点,任取一个顶点1v ,另一分图有2n 个顶点,任取一个顶点2v ,因为：
()11deg 1v n ≤-, ()22deg 1v n ≤-,
()()1212deg deg 21v v n n n +≤+-<-
与假设矛盾, G 是连通的。
2) 先证(构造)要求的哈密顿路存在:
设中有p-1条边的路,p 在这条路上的一个顶点,立刻扩展该路,使它包含这个顶点,从而得到p 条边的路。否则1v 和p v 都只邻接于这条路上的顶点,我们证明在这种情况下,存在一条链包含顶 点12,,p v v v 。 若1v 邻接于p v ,则12 ,,p v v v 即为所求。 若1v 邻接于顶点集{1,, ,,,m j t v v v v }中之一, 21,,,,,1m j t p ≤≤-,如果1v p v 是邻接于11v -, 1m v -,…,…, 1j v -, …, 1t v -中之一,譬如是1j v -,则 12111,,,,,j p p j v v v v v v v -- 是所求链。 如果p v 不邻接于11v -, 1m v -,…,…, 1j v -, …, 1t v -中任一个,则p v 最多邻接于p-k-1 个顶点, ()deg 1p v p k ≤--, ()1deg v k =,故 ()()1deg deg 11p v v p k k n +≤--+<-, 即1v 与p v 度数之和最多为n-2，得到矛盾。 至此，已经构造出一条包含顶点12 ,,p v v v 的链,因为G 是连通的,所以在G 中必有一个不属于该链的顶点x v 与链中某一顶点k v 邻接,于是就得到一条包含p 条边的链111121,,,,,, ,x k k j p p j k v v v v v v v v v v +---，重复前述构造方法，直到得到n-1条边的路。 定理7：设图G 具有n 个顶点的简单图,如果G 中每一对顶点度数之和大于等于n,则G 中存在一条哈密顿链。 证明思路：由定理6知,必有一条哈密顿路,设为12 ,,n v v v ,若1v 与n v 邻接,则定理得证。 若1v 与n v 不邻接,假设1v 邻接于12,,,k i i i v v v , 2≤i ，j≤n -1, n v 必邻接于 12111,,,k i i i v v v ---中之一。若n v 不邻接于12111,, ,k i i i v v v ---中之一,则n v 至多邻接于n-k-1个顶点,因而, ()deg 1n v n k ≤--, ()1deg v k =, ()()1d e g d e g 1 1n v v n k k n +≤--+=- , 与假设矛盾, 所以必有一条哈密顿路12111,, ,,,j n n j v v v v v v v -- 注：利用以上定理不难明白： （1）顶点数目不少于3的完全图都是哈密顿图。 （2）每个顶点度数均不小于n/2的图，特别地，k-正则图在k≥n/2时都是哈密顿 图（n为图的顶点数）。 注意，定理7给出的条件只是充分条件，不是必要条件。例如，形如六边形的图显然是哈密顿图，但它的任意两个顶点的度数和都是4,小于n – 1 = 5 。 例题7考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。 证明：设G是具有七个顶点的图，每个顶点对应于一门课程考试，如果这两个顶点对应的课程考试是由不同教师担任的，那么这两个顶点之间有一条边，因为每个教师所担任课程数不超过4，故每个顶点的度数至少是3，任两个顶点的度数之和至少是6，故G总是包含一条汗密尔顿路，它对应于一个七门考试课目的一个适当的安排。 定义3 给定图G= 定理8 当且仅当一个简单图的闭包是哈密顿图时，这个简单图是哈密顿图。 例8试构造满足下列条件的图G （1）G是欧拉图又是哈密顿图。 （2）G是欧拉图但不是哈密顿图。 （3）G是哈密顿图，但不是欧拉图。 （4）G既不是欧拉图也不是哈密顿图。 解： 图11 例9在图12中，哪些是欧拉图？哪些是哈密顿图？哪些是平面图？ 图12 例10．在下列两图中各求一条哈密顿回路。 图13 解：我们将图中顶点依次编号，按1，2，3，4，5，6，7，8，9，10的顺序在图中沿边旅行，就得到一条哈密顿回路。 哈密尔顿图具有很好的应用意义，比如说旅行商人问题（Travel Salers Problem，TSP），时间分配问题等。 例10.26旅行商人问题 同哈密顿图有密切关系的一个问题是旅行商人问题,也称为货郎担问题。这个问题有两种提法。一种是货郎到各村去卖货，再回到出发处，每村都要串到(仅到一次)，为其设计一条路线，使得所走路程最短。本问题的数学模型是在有权图G上求一个哈密顿环，使得 W(C)=={W(C i)|W(C i)为生成环的C i的权} 另一种提法是限制货郎每村都次数不限，这在实际问题中更有应用意义。 从算法理论上讲，这两种提法的难度是相当的。下面考虑后一种提法，其难度相当大，其理由有二：(1) 如何判定G是否为哈密顿图，至今尚无有效算法，也不知这种算法是否存在。(2) 已知G是哈密顿图，至今亦无求G的哈密顿环的有效算法，这种算法的存在性问题也未解决。因此，货郎担问题的有效算法的存在问题，是当今图论中面临的一个难题。但可以采用近似法来求解，下面介绍一个较好的近似算法——最邻近方法。 设G=(V，E，W)，｜V｜=n，对V中任意三个结点i，j，k，满足： w(i，j)+w(j，k)≥w(i，k) 求最小权的哈密顿回路的步骤如下： 任选一点v0作起始点，找一个与v0最近的邻接点v，得到一边构成的路。 1) 设v是新加到这条路中的一点，从不在路中的所有点中，选一个与v最近的邻接点，将它与v连成一边，构成一条新路。 2) 若所有结点均在路中，则连接最后加入的结点与v0，构成一条回路，它就是所求的哈密顿回路，否则转1)。 演化算法是对于求解大规模TSP问题较为有效的近似算法，是一种近年研究较多的模拟达尔文进化理论的算法，读者若有兴趣，请查阅相关文献。 例10.27 时间分配问题 考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，请应用有关图论性质证明：如果教师所担任的课程都不多于四门，则存在满足上述要求的考试安排方案. 解设G为七个结点的图，每一个结点对应一门功课的考试，如果这两个结点对应的课程的考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任的课程不超过4，故每个结点的度数至少是3，任两个结点度数的和至少是6，故根据定理10.10，G总包含一条哈密尔顿路，它对应于一个七门考试课目的一个适当安排。 波函数和薛定谔方程-力学量算符 1．一维运动的粒子处在 的状态，其中，求： （1）粒子动量的几率分布函数； （2）粒子动量的平均值。 [解]首先将归一化，求归一化系数A。 （1）动量的几率分布函数是 注意到中的时间只起参数作用，对几率分布无影响，因此可有 令 代入上式得 （2） 动量p的平均值的结果从物理上看是显然的，因为对本题说来，粒子动量是和是的几率是相同的。讨论： ①一维的傅里叶变换的系数是而不是。 ②傅里叶变换式中的t可看成参变量。因此，当原来坐标空间的波函数不含时间变量时， 即相当于的情况，变换式的形式保持不变。 ③不难证明，若是归一化的，则经傅里叶变换得到也是归一化的。 2．设在时，粒子的状态为 求粒子动量的平均值和粒子动能的平均值。 [解]方法一：根据态迭加原理和波函数的统计解释。任意状态总可以分解为单色 平面波的线性和，即，展开式的系数表示粒子的动量为p时的几率。知道了几率分布函数后，就可按照 求平均值。 在时，动量有一定值的函数，即单色德布罗意平面波为，与的展开式比较可知，处在状态的粒子动量可以取 ，而， 粒子动量的平均值为 A可由归一化条件确定 故 粒子动能的平均值为 。 方法二：直接积分法 根据函数的性质，只有当函数的宗量等于零时，函数方不为零，故的可能值有 而 则有及。 讨论：①由于单色德布罗意平面波当时不趋于零，因此的归一化积分是发散的，故采用动量几率分布的概念来求归一化系数。 ②本题的不是平方可积的函数，因此不能作傅氏积分展开，只能作傅氏级数展 开，即这时对应于波函数的是分立谱而不是连续谱，因此计算积分， 得到函数。 ③在连续谱函数还未熟练以前，建议教学时只引导学生按方法一做，在第三章函 数讲授后再用函数做一遍，对比一下，熟悉一下函数的运算。 3．一维谐振子处在 的状态，求： （1）势能的平均值； （2）动量的几率分布函数； （3）动能的平均值 [解]先检验是否归一化。 是归一化的。 （1） 第十五章欧拉图与哈密顿图 15.1 欧拉图 (2) 一、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义 (3) 二、判别定理 (4) 三、求欧拉图中欧拉回路的算法 (6) 1．Fleury算法，能不走桥就不走桥： (6) 2．逐步插入回路法 (7) 四、中国邮路问题 (8) 练习题： (9) 15.2哈密顿图 (11) 一、哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图的定义 (12) 二、哈密顿图与半哈密顿图的一些必要与充分条件 (12) 练习题 (18) 15.3 带权图与货郎担问题 (24) 一、带权图 (24) 二、货郎担问题 (24) 15.1 欧拉图 主要内容： 1. 欧拉通路、欧拉回路、欧拉图、半欧拉图的定义。 2. 判别定理。 3. 求欧拉图中欧拉回路的算法。 学习要求： 1. 深刻理解欧拉通路与欧拉回路的定义以及它们的区别与联系。 2. 以无向欧拉图为例，进一步理解欧拉图的结构，即，欧拉图是若干个边不重的圈之并。 让我们先从两个例子出发，获得有关图的一些直观认识。 图论的研究起源于哥尼斯堡七桥问题。哥尼斯堡城位于Pnsel河畔，河中有两个岛，有7座桥与4块陆地彼此相连，如上图所示。 居住于该城的居民想做这样的游戏：从4块陆地的任一块出发，经过每座桥一次且仅一次，最后返回原出发地。当地的人们进行了许多次尝试，都没有成功。后来，欧拉给出了问题的解。首先欧拉将4块陆地表示成4个结点，凡陆地间有桥相连的，便在两点间连一条边，从而可将左图改画为右图如下：这样，哥尼斯堡七桥问题可描述为：能否有从A、B、C、D任一点出发，经过每条边一次且仅一次而返回出发点的回路? 欧拉证明了这样的回路是不存在的。他的理由是，从图任一点出发，要回到原出发点，要求与每个点关联的边的数目为偶数，才能保证从一条边进入某点再从另一条边出去，一进一出才能回到原出发点。而图中的顶点A、B、C和D均有奇数条边与其相关联，显然这样的回路是不存在的。 另一个例子是20世纪40年代的一个数学游戏。 欧拉图与哈密顿图 欧拉图定理 哈密顿算符不同形式下的表达式 胡连钦(08180218) 范世炜(08180218) 摘要：由直角坐标系中的哈密顿算符向不同坐标系转换，将得到不同形式（极坐标、柱坐标、球坐标和矩阵）的哈密顿表达式。本文采用直接微分运算的方法，详细的介绍了哈密顿算符表达式的数学推导过程，降低了初学时的难度。另外本文还通过计算，直接给出了动量分量的算符表述，并且针对不同情况补充相应的例题或是加上哈密顿算符的具体应用。 关键词：哈密顿算符 微分运算 推导过程 动量分量 算符表述 应用 1.引言 在经典力学中，我们定义哈密顿算符为总能量算符： V m p V T H +=+=2/????2 如果我们从波函数)?(r ψψ=出发，位置算符是空间矢量自身： r r =? 它的分量是 x x =? ，y y =? ， z z =? 动量算符表示为 ?-= i p ? 它的分量是 x i p x ??-= ? ，y i p y ??-= ? ，z i p z ??-= ? 对应的哈密顿算符可以通过标准的替换规则?-→ i p 得到 V m H +?-=22 2? 在教科书中，给出了哈密顿算符的柱坐标及球坐标的表达式，但因数学推导过程难度过大，一般教科书中都是略去的。接下来，我们给出了方程的数学推导过程，降低初学时的难度。 2、哈密顿算符在不同坐标中推广表达式 2.1、极坐标下的哈密顿算符 极坐标中独立变量ρ、?与直角坐标中独立变量 x 、y 之间的关系： ?? ? ??=+=x y y x a r c t a n 22?ρ 图1 极坐标与直角坐标的关系 根据上述关系有： ? ρ?ρ? ??ρρ?? - ??=????+ ????= ??s i n c o s x x x ? ρ?ρ ???ρρ?? + ??=????+????=??cos sin y y y x y ρ ? 第三章欧拉图与哈密顿图 （七桥问题与一笔画，欧拉图与哈密顿图） 教学安排的说明 章节题目：§3.1环路；§3.2 欧拉图；§3.3 哈密顿图 学时分配：共2课时 本章教学目的与要求：认识七桥问题的实质，理解一笔画问题的解决方法，会正确理解关于欧拉图和哈密顿图的判断定理，并进行识别． 其它：由于欧拉图与一笔画问题密切相关，因此本章首先从一笔画问题讲起，章节内容与教材有所不同。 课堂教学方案 课程名称：§3.1环路；§3.2欧拉图；§3.3哈密顿图 授课时数：2学时 授课类型：理论课 教学方法与手段：讲授法 教学目的与要求：认识七桥问题的实质，理解一笔画问题的解决方法，会正确理解关于欧拉图和哈密顿图的判断定理，并进行识别． 教学重点、难点： （1）理解环路的概念； （2）掌握欧拉图存在的充分必要条件； （3）理解哈密顿图的一些充分和必要条件； 教学内容： 看图1，有点像“回”字，能不能从某一点出发，不重复地一笔把它画出来？这就是中国民间古老的一笔画游戏，而这个图形实际上也是来源于生活。中国古代量米用的“斗”?上下都是四方的，底小口大，从上往下看就是这样的图形。 这类“一笔画”问题中最著名的当属“哥尼斯堡七桥问题”了。 一、问题的提出图1 哥尼斯堡七桥问题。18世纪，哥尼斯堡为东普鲁士的首府，有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥联结起来，见图2（1），当时那里的居民热衷于一个难题：游人怎样不重复地走遍七桥，最后回到出发点。1735年，一群执着好奇的大学生写信请教当时正在圣彼得堡科学院担任教授的著名数学家欧拉。欧拉通过数学抽象成功地解决了这一问题。欧拉发现欧几里得几何并不适用于这个问题，因为桥不涉及“大小”，也不能用“量化计算”来解决。相反地，这问题属于提出的“位置几何”。欧拉想到，岛与河岸陆地仅是桥梁的连接地点和通往地点，桥仅是从一地通往另一地的路径，一次能否不重复走遍七桥与河岸陆地大小是没有 哈密顿算符的运算规则 厦门大学物理系李明哲 【摘要］本文从哈密顿算符的定义出发，根据哈密顿算符的性质．给｜＿｝｛哈离顿算符完整、统…的运算规划，以克服现有物理教剩书中该算符运算规则升；…‘致的缺点，进而帮助学习者更好地掌握该算符。 【关键词】晗密顿算符运算规则场论 物理学中处理“场”的问题时，熟练掌握哈鬻顿算符非常关键。例如。本科《电动力学》整门谋程在菜种程度上可以说就是利用哈密顿算符的性质处理壹克斯市方程组的。该课程被物理系的本科生视为最难的谋私之。，实质原幽在于对晗密顿算符的运算掌握ａｉ好。所以，在正式学习该课程之前，总是需要先温习这部分知识。 然而，～些常用教科书（例如《电动力学》…）在舟绍哈密顿算符的运算规则时并没有给出宠籀、统一、清晰的规则，导致读肴不耪理解和掌握；而另外一然教科书（例如《经典电动力学》“）则直接将其列为公式，并未给山证明，读者遇到列出的公式之外的运算就无法进行，当然也就无法真正掌握。 本文希望能克服这一不足之处，从哈密顿算符豹定义出发，分析暗密顿算符的两个报本性质，并由此给出一套哈密顿算符的完整、统…的运算规则。 一、哈密顿算符的定义 哈密顿算符定义为： 甲＝磋＋瑶＋礓 ∞Ｗ∞ 由上图可以看出算符同时具有失罱性和微分性两个根本性质，所以在其运算过程中要同时ｊ主意这两方面的性质。由该定义，场的梯度、教度和旋度可以分别理解为算符Ｖ直接作用、点乘和义乘该场。 二、哈密顿算符的运算规则 根姑前商晗密顿算符的定义和性质的分析，哈密顿算符的运算规则为： 步骤１．根据口的微分性写成几项，在Ｖ的下标标明算符Ｖ作用于哪个函数上。 步骤２．将甲看成…．个矢量，利用失?９０?量和标量的性质重新排列，使得甲叫纠。【即舻＋∥ｌ纠（４１）墨繁慕嚣翌霈善ｖ㈤：嗽７＋四回㈣面。排列时注意汛注意各符号７够』２Ｖ掣；歹＋掣Ｖｊｑ纠荽嚣差耋篁嚣兰嚣置。和，。㈤书曲。刊ｖ。刁㈤Ｘ的位置；ｂ．注意正负号。…惮，一ｔ’…，“，１…～’“ｏ，…叫：≤凳耋耋耋０等萝二墓ｖ西司：ｉ婶ｘ７卜７ｐ函＂）三个运算步骤充分体现了哈密…叫。、 叫。㈩’’ 篓苎篓竺翌０警烹性质?以下举Ｆ×西裔：善形．（Ｖ疆＋ｐ裔再旷ｖ蓐（４５）例示范这三个步骤： …“”’…、……。。 步骤１．类似于做微分运算。例如： Ｖ啦曲＝口，缸¨＋已∞∽（２１） ｖ∞却，㈤＋ｖ㈤（２．２） ｖｘ∞＝Ｆ，ｘ∞＋Ｌ×∞ｏ．３） Ｖ晒＝Ｖ，嘲＋ｖ，黼儡４） ９ｘＢ西＝Ｄｘ｜７硝＋Ｖ。×∞西让５） 步骤２．常用的矢量性质有： 于将看成个矢量，然后还需注意正在 处理的是矢量和标量的点乘（标秘）和叉 乘（矢积）等逛算。它是有别于数乘的。掌 握了．匕述哈密顿算符的运葬规则，对物 理学中场的问题的处理就能够得心应手 了。 于喜＝ｇ，，／ｘｇ＝一ｇｘ， ７Ｅｘ茅）＝；Ｆ×动＝≯Ｆ×动，Ａ管×习：矿疆一萨蕊例如：Ｖ，扣囝十Ｖ，（￡ｆ计＝妒∥≯＋“０∽ｏ１） 甲，翰＋ｏ㈤＝帆∞丸妒，回（３２） ｏｘ㈤＋巧ｘ∞＝盹办丸毋，×另 ０ｘ够ｊ＋巧ｘ㈣＝Ｒ咖，十心，×力（３筇 ＬＶｘ鲫＋可ｌｐ×ｇ）＝ｇＰ，ｘ，Ｊ一，甲ｌｘ酣（３４）÷÷＿—｝｛，■～●—＊÷，．ｈ●＿＿ Ｖ，ｘ扩。ｇ）＋Ｖｊｘ矿。ｇｊ＝培，Ｖ，弦一ｐ，ｊ，）ｇ＋审，ｇ驴一ＶＶ，量（３５） 步骤３壤简单，抹玉的下标即可－所参考文献 以，由（２．１）～（２．５）和（３．１）一（３．５）得【１］郭硕鸿．电动力学【Ｍ】．北京：高总结；由以Ｌ哈密顿Ｖ算符的运算等教育出版社．１９９７ 规则的三个步骤可以看出，第二二步垠容【２］蘩圣善，束耘经典电动力学【Ｍ】，崭出错。在做这一步运算时茸先要习惯ｔ海：复旦夫学出版社，１９８５※ 万方数据 第二章（一维）算符理论 本章提要：本章从线性变换和微分算子出发，建立算符理论统一它们来处理「观测行为」，引入观测公设。接着，从观测值=本征值为实数的要求出发，找到了符合条件的厄米矩阵来描述力学量，引入算符公设。之后介绍了运算法则、基本的位置和动量算符、复合算符的对易子、哈密顿算符等。最后，作为对上述内容的综合应用，讨论了不确定性原理。 1.算符：每一个可观测量，在态空间中被抽象成算符。在态空间中，观测行为被抽象为，某可测量对应的算符「作用」在态矢量上 ①线性变换：线性代数告诉我们，一个线性变换「作用」到n 维向量上会获得一个新的n 维向量，这等价于一个n 阶方阵「作用」在n 行1列矩阵上得到新的n 行1列矩阵，用数学语言可表示为()Ta b T =?=αβ 。总之，方阵与线性变换一一对应。由于方阵性质比矩阵更丰富，我们将只研究方阵。 ②微分算子：在微积分中2222,,,i i x f x f dx f d dx df ???? 也可简写成f f f D Df 22,,,??。前两种在解 欧拉方程和高阶方程式时常用，后两种则经常出现在矢量分析中。简写法可看作是微分算子「作用」在函数上，我们知道它遵守加法和数乘法则，是一种线性运算 ③本征值和本征矢：在矩阵方程x Ax λ=中，把λ称为矩阵本征值，x 称为矩阵的本征矢 ④本征值和本征函数：在微分方程f f D mix μ=中，把μ称为问题本征值，f 称为本征函数 ⑤线性算符：现在把上述概念统一为线性算符理论。 考虑一个可测量Q ，定义它的对应算符为Q ?，它的本征方程是ψ=ψλQ ?或λψψ=Q ?，把λ称为算符的「本征值」，λ的取值集合称为算符的「谱」， ψ称为算符的「本征态」 （或本征矢），ψ称为算符的「本征函数」 （注意：有时也把ψ记作本征值的对应本征态λ， 如后面将遇到的坐标算符本征态x 、动量算符本征态p ） ⑥第三公设——观测公设：对于量子系统测量某个量Q ，这过程可以抽象为对应的算符Q ?作用于系统粒子的态矢量ψ，测量值只能为算符Q ?的本征值i λ。在这次测量后，假设得到 第三章 形式理论 本章主要内容概要： 1. 力学量算符与其本征函数 量子力学中力学量（可观测量）用厄米算符表示，厄米算符满足 () * *??()()()()f x Qg x dx Qf x g x dx =? ? 或者用狄拉克符号，??f Qg Qf g =，其中(),()f x g x 为任意满足平方可积条件的函数（在x →±∞，(),()f x g x 为零）。 厄米算符具有实本征值的本征函数（系），具有不同本征值的本征函数相互正交，若本征值为分离谱，本征函数可归一化，是物理上可实现的态。若本征值为连续谱，本征函数可归一化为δ函数，这种本征函数不是物理上可实现的态，但是它们的叠加可以是物理上可实现的态。 一组相互对易的厄米算符有共同的本征函数系。而两个不对易的厄米算符没有共同的本 征函数系，它们称为不相容力学量。对任意态测量不相容力学量??,Q F ，不可能同时得到确定值，它们的标准差满足不确定原理 2 22 1??,2Q F Q F i σσ????≥ ????? 2. 广义统计诠释 设力学量?Q 具有分离谱的正交归一本征函数系{}()n f x 本征值为{}n q ，即 ()*?()(), ()(), ,1,2,3,...n n n m n mn Qf x q f x f x f x dx m n δ===? 或 ?, n n n m n mn Q f q f f f δ== 这个本征函数系是完备的，即1n n n f f =∑ （恒等算符，封闭型），任意一个波函数可以 用这个本征函数系展开 (,)(),n n n x t c f x ψ=∑ 或n n n n n n f f c f ψ=ψ=∑∑ 展开系数为 *()()(,)n n n c t f f x x t dx =ψ= ψ? 若(,)x t ψ是归一化的，n c 也是归一化的， 2 1n n c =∑。广义统计诠释指出，对(,)x t ψ态 测量力学量Q ，得到的可能结果必是Q 本征值中的一个，得到n q 几率为2 n c 。对系综测量力学量Q （具有大量相同ψ态系综中的每一个ψ进行测量）所得的平均值（期待值）为 自主学习01 教材内容 第三章力学量与算符 知识框架重点难点第一节第二节第三节第四节 第五节第六节第七节第八节本章习题本章自测 重点难点 通过本章的学习，应使学生掌握量子力学中的力学量用算符表示的基本原理， 表示力学量的算符，动量算符和角动量算符，厄米算符本征函数的正交性，算符与力学量的关系，算符的关系，两力学量同时有确定值的条件，不确定性关系，力学量平均值随时间的变化，守恒定律，掌握力学量随时间的演化规律。 §3.1 力学量的平均值，力学量用算符表示 [本节要求] 理解力学量的平均值的概念，掌握力学量的算符表示 [重点难点] 力学量的算符表示 [本节内容] 粒子处于波函数 )(r ψ所描述的状态下,虽然不是所有的力学量都有确定的观测值,但它们都有确定 的几率分布,因而有确定的平均值. 粒子处于归一化状态 )(r ψ,其位置坐标的几率密度为ψψ*.这样,位置坐标的平均值为 ()()()()x d r r r x d r r r r 33 ψψ ψψ ??* * == (1) 波长是用以刻画波动在空间变化快慢的,是属于整个波动的量.因此,“空间某一点的波长”的提法是没有意义的.再根据德布罗意关系式p=h/λ,“微观粒子在空间某点的动量”的提法也是没有意义的.因此, 不能像求位置的平均值那样求动量的平均值.按前面所述,给定波函数)(r ψ后,测得粒子的动量在p 到p d p +之间的几率为 p d p 3 2 )( ?,其中 x d e r p r p i 32 3)() 2(1)( ?-?∞ -∞ += ψπ? (2) 其逆变换为 ()()()p d r p i e p r 32 321 ?∞+∞ -?= ?πψ (3) ?：向量微分算子、哈密尔顿算子、Nabla算子、劈形算子，倒三角算子是一个微分算子。 Strictly speaking, ?del is not a specific operator, but rather a convenient mathematical notation for those three operators, that makes many equations easier to write and remember. The del symbol can be interpreted as a vector of partial derivative operators, and its three possible meanings—gradient, divergence, and curl—can be formally viewed as the product of scalars, dot product, and cross product, respectively, of the del "operator" with the field. Δ、?2 or ?·?：拉普拉斯算子（Laplace operator），定义为梯度（▽f）的散度（▽·f）。 , grad F=▽F，梯度（gradient），标量场的梯度是一个向量场。标量场中某一点上的梯度 指向标量场增长最快的方向，梯度的长度是这个最大的变化率。▽f= div F=▽·F,散度(divergence),是算子▽点乘向量函数,矢量场的散度是一个标量函数，与求 梯度正好相反,div F表示在点M处的单位体积内散发出来的矢量F的通量，描述了通量源的密度，可用表征空间各点矢量场发散的强弱程度。当div F>0 ，表示该点有散发通量的正源；当div F<0 表示该点有吸收通量的负源；当div =0，表示该点为无源场。即闭合曲面 的面积分为0是无源场，否则是有源场。 rot F 或curl F=? × F,旋度(curl，rotation)，是算子▽叉乘向量函数,矢量场的旋度依然是 矢量场，意义是向量场沿法向量的平均旋转强度，向量场在曲面上旋量的总和等于该向量场沿该曲面边界曲线的正向的环量，也就是封闭曲线的线积分。旋量为0的向量场叫无旋场，只有这种场才有势函数，也就是保守场。即闭合环路的线积分为0是无旋场，否则就是有旋场。 基本关系： 一个标量场f的梯度场是无旋场，也就是说它的旋度处处为零： 类氢离子的哈密顿算符的简单计算 摘要：多年来，类氢离子一直是科学家简化分子模型以及进行相关理论研究的一种重要参考物。同时这些离子的许多物理性质已经通过实验证实，从而更好的帮助验证科学家的假设。像离子的极化率可以可由斯塔克效应实验测定[1]。这样子极大的推动了理论的发展。利用Born- Oppenheimer 近似方法求解类氢离子的哈密顿算符。 关键字：氢分子离子; 哈密顿算符; Born- Oppenheimer近似; 首先通过分析氢原子在考虑到核运动的情况下的哈密顿算符及其本征函数,来类推之后的类氢离子的哈密顿算符考虑到核质量有限, 电子与核都在运动时, 体系的哈密顿算符为H=-h2?e2*2mp-h2?p2*2mp-e12/=-h2?c2/2(me+mp) - h2?e2/2μ-e2/r .其中μ=mlmp/(me+mp)为折合质量, 拼为电子相对核的位矢. -h2?c2/2(me+mp), h2?e2分为原子质心运动的动能算符和相对运动的动能算符[2]。 一．Hz+ 的哈密顿算符的简单计算 氢分子离子是目前已知的最简单的离子，虽然不稳定，但在解释许多电子原子结构方面起到了很好的作用。在实验室参考系, 多点电荷体系的非相对论哈密顿量( 原子单位) 可以表示为H2+是一个包含两个原子核和一个电子的体系。其坐标如图所示。图中和代表电子与两个核的距离,代表两个核的距离。 对于氢分子离子H2+系统, 坐标矢量由图给出, e 表示电子, m1 和m2 表示两个原子核的质量, G 表示两原子核的几何中心, O 为实验室参考系的原点,c 为质量中心. 为两核之间的距离, Rcm 为质量中心相对于实验室坐标为两核之间的距离, 为质量中心相对于实验室坐标原点的距离. 无论在哪个坐标系, 势能算 波函数和薛定谔方程-力学量算符1．一维运动的粒子处在 的状态，其中，求： （1）粒子动量的几率分布函数； （2）粒子动量的平均值。 [解]首先将归一化，求归一化系数A。 （1）动量的几率分布函数是 注意到中的时间只起参数作用，对几率分布无影响，因此可有 令 代入上式得 （2） 动量p的平均值的结果从物理上看是显然的，因为对本题说来，粒子动量是和是的几率是相同的。讨论： ①一维的傅里叶变换的系数是而不是。 ②傅里叶变换式中的t可看成参变量。因此，当原来坐标空间的波函数不含时间变量时， 即相当于的情况，变换式的形式保持不变。 ③不难证明，若是归一化的，则经傅里叶变换得到也是归一化的。 2．设在时，粒子的状态为 求粒子动量的平均值和粒子动能的平均值。 [解]方法一：根据态迭加原理和波函数的统计解释。任意状态总可以分解为单 色平面波的线性和，即，展开式的系数表示粒子的动量为p时的几率。知道了几率分布函数后，就可按照 求平均值。 在时，动量有一定值的函数，即单色德布罗意平面波为，与的展开式比较可知，处在状态的粒子动量可以取 ，而， 粒子动量的平均值为 A可由归一化条件确定 故 粒子动能的平均值为 。 方法二：直接积分法 根据函数的性质，只有当函数的宗量等于零时，函数方不为零，故的可能值有 而 则有及。 讨论：①由于单色德布罗意平面波当时不趋于零，因此的归一化积分是发散的，故采用动量几率分布的概念来求归一化系数。 ②本题的不是平方可积的函数，因此不能作傅氏积分展开，只能作傅氏级数展 开，即这时对应于波函数的是分立谱而不是连续谱，因此计算积分， 得到函数。 ③在连续谱函数还未熟练以前，建议教学时只引导学生按方法一做，在第三章函 数讲授后再用函数做一遍，对比一下，熟悉一下函数的运算。 3．一维谐振子处在 的状态，求： （1）势能的平均值； （2）动量的几率分布函数； （3）动能的平均值 [解]先检验是否归一化。 是归一化的。 （1）波函数和薛定谔方程-力学量算符
离散数学结构 第15章 欧拉图与哈密顿图
欧拉图与哈密顿图
Euler and Hamilton Graph
高晓沨 (Xiaofeng Gao)
Department of Computer Science Shanghai Jiao Tong Univ.
2016/12/6
欧拉道路与欧拉回路
Euler Path and Euler Circuit
IntroductionToCS--Xiaofeng Gao
3
目录
1 欧拉道路与欧拉回路 2 哈密顿道路与哈密顿回路
2016/12/6
IntroductionToCS--Xiaofeng Gao
2
欧拉回路
【定义】给定无向连通图G=(V, E)，包含 图G的所有边的简单道路称为欧拉道路(或 欧拉通道、欧拉迹) ， 包含图G的所有边的简单回路称为欧拉回路 (或欧拉闭迹) 。 假设G没有孤立点，若G含有欧拉回路，则 称G是欧拉图。
2016/12/6
IntroductionToCS--Xiaofeng Gao
4
【定理】图G是欧拉图的充要条件是G连通 且没有奇点。
【证】必要性 ： 若G中有欧拉回路C,则C过每一条边有且仅 有一次。对任一节点v,如果C由ei进入v, 则 一定通过另一条边ej从v离开。因此v的度是 偶数。
2016/12/6
IntroductionToCS--Xiaofeng Gao
5
证明(3)
G1可能是非连通图，每个顶点的度保持为 偶数。这时，G1中一定存在某个度非零的 节点vi，同时也是C中顶点。否则C的顶点 与G1的顶点之间无边相连，与G是连通图矛 盾。同理，从vi出发，G1中所在的连通分量 内存在一条简单回路C1。C ∪ C1仍然是G 的一条简单回路，但它包括的边数比C多。 继续构造，最终有C’=C ∪ C1 ∪… ∪ Ck是 一条欧拉回路。
2016/12/6
IntroductionToCS--Xiaofeng Gao
7
证明(2)
充分性 ：由于G是有穷图，因此可断定从 G的任一节点v0出发一定存在G的一条简单 回路C。这是因为各节点的度都是偶数，所 以这条简单回路不可能停留在v0以外的某个 节点，而不能再向前伸延以构成闭通道C。
如果E=C, 则C就是欧拉回路，充分性得证。 否则在G中删去C的各边，得到G1=G―C。
2016/12/6
IntroductionToCS--Xiaofeng Gao
6
范例
【例】 判断下图是否欧拉图：
a
b
e
d
c
G
a
b
d
c
H
2016/12/6
IntroductionToCS--Xiaofeng Gao
8哈密顿算符不同坐标下的表示
第三章 欧拉图和哈密顿图
哈密顿算符的运算规则
量子力学 第二章 算符理论
量子力知识学知识题解答-第3章
自主学习01 教材内容 第三章 力学量与算符
算子总结;哈密尔顿算子;拉普拉斯算子
类氢离子的哈密顿算符的简单计算2
波函数和薛定谔方程-力学量算符
相关主题
文本预览