图论中欧拉道路与尔顿道路核心概念与定理.pdfVIP

1.图的概念/IntroductionofGraph

2.图的术语/GraphTerminology

3.图的表示与同构/

RepresentingGraphandGraphIsomorphism

4.连通性/Connectivity

5.欧拉道路与尔顿道路/

EulerandHamiltonPaths

6.最短道路问题/ShortestPathProblem

7.平面图/narGraphs

8.图的/GraphColoring

9/26/20224:35PMDerenChen,Univ.1

7.5EulerandHamiltonPath

Konigsberg(哥尼斯堡)七桥问题

A

D

C

B

问题：能否从河岸或小岛出发，通过每座桥，

而且仅仅通过次回到原地

9/26/20224:35PMDerenChen,Univ.2

Euler(欧拉)1736年对这个问题，给出了否

定的回答。将河岸和小岛作为图的顶点，七座

桥为边，构成一个无向重图，问题化为图论中

简单道路的问题：

[定义]欧拉道路（回路）：Ｇ＝（Ｖ，Ｅ）

，称包含Ｅ中所有边的简

单道路为欧拉道路/EulerPath/E道路。

包含Ｅ中所有边的简单回路为欧拉回路

/EulerCircuit/E回路

。

9/26/20224:35PMDerenChen,Univ.3

[定理1]（欧拉定理）：

没有次为０的孤立顶点的无向图存

在欧拉道路的充要条件是：

(1)图是连通的；

(2)图中奇次顶点个数是０个或2个。

9/26/20224:35PMDerenChen,Univ.4

证明：

必要性：

若存在欧拉道路，且没有０次顶点，则每个顶

点都有边关联，而边又全在欧拉道，故所有顶

点都连通。

除了起点，终点外，欧拉道路每经过一个顶点，

使顶点的次增加２，故只有起点和终点才可能成为

奇次顶点，而一个奇次顶点是不可能的，当无奇次顶

点时，是欧拉回路。

充分性：

若(1），(2)成立,构造欧拉道路.

9/26/20224:35PMDerenChen,Univ.5

若图Ｇ存在奇次顶点，任取一个作为起点，若

不存在，则任取一个顶点作为起点。

若此图有ｎ条边，总次为２ｎ。每进入或离开

一个顶点，让此顶点的次减１，由于除了两个（或

没有）奇次顶点外，其余顶点次为偶数，只要进得

去，一定出得来，直至进入另一个奇次顶点（或起

点）作为终点。这样构造的是简单道路，如果经过

所有的边，即得到一条欧拉道路。

不然，记走过的简单道路为ｐ，ｐ上顶点集

11

Ｖ，边集Ｅ，Ｇ＝（Ｖ，Ｅ）是Ｇ的子图。

11111

9/26/20224:35PMDerenChen,Univ.6

若Ｇ＝（Ｖ，Ｅ）是Ｇ的关于Ｇ的余图，Ｅ

2