哥尼斯堡（Konigsberg） 七桥问题

Presentation on theme: "哥尼斯堡（Konigsberg） 七桥问题"— Presentation transcript:

1 哥尼斯堡（Konigsberg） 七桥问题
在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？ 哥尼斯堡（Konigsberg） 七桥问题

2 1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的报告，在解答问题的同时，开创了数学的一个新的分支——图论，也由此展开了数学史上的新历程。
欧拉的论文《Solutio problematis ad geometriam situs pertinentis /The solution of a problem relating to the geometry of position/依 据几何位置的解题方法》1741年发表于《Journal Commentarii academiae scientiarum Petropolitanae》。 ——这是关于图论的第一篇论文

3 每一块陆地考虑成一个点 连接两块陆地的桥以线（边）表示 因为点A关联了5条边，即与岛A相连接的有5座桥， 故这些桥不可能每座恰好被走过1次
C B A D 因为点A关联了5条边，即与岛A相连接的有5座桥， 故这些桥不可能每座恰好被走过1次

4 再论七桥问题：从图的基本概念说起 图的定义 一个图G是一个有序二元组(V, E)，其中 (1) V是一个有限的非空集合，称为顶点集合,其
元素称为顶点或点。用|V|或v(G)或υ表示顶点数； (2) E是由V中的点组成的无序对构成的集合，称 为边集，其元素称为边，且同一点对在E中可以 重复出现多次。用|E|或e(G)或ε表示边数。

5 相邻：同一条边的两个端点称为相邻 关联：一条边的端点和边关联 环：端点重合的边 重边：端点相同的边（两条以上） 有限图：顶点集和边集都是有限的图 平凡图：只有一个顶点的图 简单图：不含重边和环的图

6 顶点v的度数d(v)：与v关联的边的条数
图：G=(V,E) 点集：V={A,B,C,D} 点数：|V|=v(G)=4 边集：E={{A,C},{A,C},{A,B},{B,C},{A,D},{A,D},{B,D}} :={AC,AC,AB,BC,AD,AD,BD} :={e1,e2,e3,e4,e5,e6,e7} 边数：|E|=e(G)=7 e8 e4 e1 e2 顶点v的度数d(v)：与v关联的边的条数 e3 d(A)=5,d(B)=3,d(C)=3,d(D)=3 e5 e6 e7 注：一个环（如果存在的话）算两条边 d(C)=5

7 最大度： 最小度： 最大度=5，在点A处达到 最小度=3，在点B,C,D处达到

8 度和关系式： 推论：在任何图中，奇度点个数为偶数 （1）图中每条不是环的边恰好关联2个顶点；
（2）图中每个环只关联1个顶点，但一个环算2条边 推论：在任何图中，奇度点个数为偶数 奇数 x ？+ 偶数 x 偶数或者奇数 = 偶数

9 途径：图中点边交替出现的有限序列（以点开始，以点结束）
v1 e12 v2 e23 v3 e23 v2 迹：一条边互不相同的途径 v1 e12 v2 e23 v3 e34 v4 路：一条点互不相同的迹 Euler迹：经过图的每一条边的迹 v1 e12 v2 e23 v3 e34 v4 e45 v5 e56 v6 e64 v4 e42 v2 e26 v6 e61 v1 Euler环游：闭（起点和终点一样）的Euler迹 v1 e12 v2 e26 v6 e56 v5 e45 v4 e42 v2 e23 v3 e34 v4 e64 v6 e61 v1 Euler通路：开（起点和终点不一样）的Euler迹 此图存在Euler通路吗 ？？？ Euler图：存在Euler环游的图

10 引理1：若简单图G的最小度至少为k≥2， 则G包含一个边数至少为k+1的圈。 证明：取图G的一条长度最长的路P，
其经过的点依次记为v0,v1,...,vt-1,vt 则点v0与点vt的邻点都在路P上 （为什么？） 由于G的最小度至少为k，故点v0至少有k个邻点 设其为vi1,vi2,...vik （ik≥...≥i2≥i1） 从而有 t≥ik≥k 于是，v0v1...vikv0为图G中的一个包含ik+1≥k+1条边的圈。

11 如果对图G=(V,E)的任何两个顶点u与v， 图G中存在一条u-v路， 则称图G是连通的，否则称图G是不连通的。

12 引理2：设简单连通图G中有一个圈C， G'是从G中去掉C的所有边所得到的图。 如果H是图G'的任何一个连通分支，则 V(C)∩V(H)≠Φ

13 定理1：设G是一个非平凡的连通图， 则G是Euler图 当且仅当 图G没有度数为奇数的点。
必要性：“几乎”显然~~ 当沿着Euler环游前进时，每经过一个点必定是“一进一出”

14 充分性：（对图的边数进行归纳） G中没有度数为奇数的点且G连通 ==> δ(G) ≥ 2 ==> G中含有一个圈C (引理1) 将C的所有边从图G中去除，然后删去度数为0的点 得到图G'（其边数比G少） 设H1，H2，……，Ht为图G'的连通分支（最小度至少为2） 再设它们与圈C分别交于点v1，v2，……，vt （引理2） 由归纳假设，Hi存在 始于vi 终于 vi 的Euler环游Ri 最后，将C与R1，R2，……，Rt拼接起来得到图G的Euler环游

15

16 定理2：设G是一个非平凡的连通图， 则G有Euler通路 当且仅当 图G恰好有两个度数为奇数的点。 若Euler通路的起点和终点分别为u,v
则有且仅有d(u)与d(v)为奇数 若图G仅有两个奇点u,v 则G+uv存在一个从u出发的Euler回路 此回路中删去“新边”uv，得到G的Euler通路