画一个欧拉图.ppt

1/77
欧拉图
(一) 欧拉通路欧拉回路
(二) 欧拉图
(三) 欧拉定理(1836年)
(四) 欧拉图的示例
2/77
例(蚂蚁比赛问题)
甲、乙两只蚂蚁分别位于如下图中的结点A,B处,并设图中的边长度是相等的。甲、乙进行比赛:从它们所在的结点出发,走过图中的所有边最后到达结点C处。如果它们的速度相同,问谁先到达目的地?
A (甲)
B(乙)
C
3/77
哥德尼斯堡七桥问题
十八世纪初,在当时德国哥德尼斯堡(现加里林格勒)城的普雷格尔河上有7座桥。当地人经常在桥上散步,有人提出,从岛和河岸的某一处出发是否能找到一条通过每一座桥一次且仅一次的通路。
(a)
(b)
4/77
欧拉(Leonhard Euler,1707-1783)
瑞士数学家及自然科学家。在1707年4月15日出生於瑞士的巴塞尔,1783年9月18日於俄国的彼得堡去逝。欧拉出生於牧师家庭,13岁时入读巴塞尔大学,15岁大学毕业,16岁获得硕士学位。 1733年,,共写下了886本书籍和论文。彼得堡科学院为了整理他的著作,足足忙碌了四十七年。
欧拉还创设了许多数学符号,例如π(1736年),i(1777年),e(1748年),sin和cos(1748年),tg(1753年),△x(1755年),Σ(1755年),f(x)(1734年)等.
5/77
欧拉通路、欧拉回路、欧拉图
定义 G=(V,E)是一个图,
◆ G中一条通路称为欧拉通路,若此条通路经过了图中每条边一次且仅一次。
◆若一条欧拉通路是一个回路,则称此回路为欧拉回路。
◆一个图若有欧拉回路,则称这个图为欧拉图。
6/77
定理1(欧拉,1736年)
一个没有孤立点的无向图具有欧拉通路,当且仅当它是连通的,并且或者没有奇数度的顶点或者有且仅有2个奇数度的顶点。
7/77
例找欧拉通路
从奇数度顶点走到奇数度顶点。
在顶点C可以将通路延伸如下:
ABCDGC
A G F
B C D E
8/77
例找欧拉通路
在绿顶点处,走完所有黑边,再走完剩余的红边。有三种通路。
A G F
B C D E
9/77
定理1的推论
一个无向图有欧拉回路当且仅当所有顶点均为偶数度。
10/77
一笔画问题
一个无向图是否有欧拉通路的问题与此图能否一笔画是同一个问题。
一个图能够一笔画即此图要么没有奇数度顶点,要么仅有两个奇数度顶点。