在哥尼斯堡的一个公园里， 有七座桥將普雷格尔河中两 个岛及岛与河岸连接起来（如 图)。问是否可能从这四块陆 地中任一块出发，恰好通过 每座桥一次，再回到起点？ 哥尼斯堡(Koni gsberg) 七桥问题
在哥尼斯堡的一个公园里， 有七座桥将普雷格尔河中两 个岛及岛与河岸连接起来(如 图)。问是否可能从这四块陆 地中任一块出发，恰好通过 每座桥一次，再回到起点？ 哥尼斯堡（Konigsberg） 七桥问题
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》 这是关于图论的第一篇论文
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》。 ——这是关于图论的第一篇论文
每一块陆地考虑成一个点 连接两块陆地的桥以线（边）表示 A B 因为点A关联了5条边，即与岛A相连接的有5座桥， 故这些桥不可能每座恰好被走过1次
每一块陆地考虑成一个点 连接两块陆地的桥以线（边）表示 因为点A关联了5条边，即与岛A相连接的有5座桥， 故这些桥不可能每座恰好被走过1次 C A B D
再论七桥问题：从图的基本概念说起 图的定义 一个图G是一个有序二元组(V,),其中 )V是一个有限的非空集合，称为顶点集合，其 元素称为顶点或点。用V或v(G)或v表示顶点数； (2)E是由V中的点组成的无序对构成的集合，称 为边集，其元素称为边，且同一点对在E中可以 重复出现多次。用|E或e(G)或e表示边数
再论七桥问题：从图的基本概念说起 图的定义 (1) V是一个有限的非空集合，称为顶点集合,其 元素称为顶点或点。用|V|或v(G)或υ表示顶点数； (2) E是由V中的点组成的无序对构成的集合，称 为边集，其元素称为边，且同一点对在E中可以 重复出现多次。用|E|或e(G)或ε表示边数。 一个图G是一个有序二元组(V, E)，其中
相邻：同一条边的两个端点称为相邻 关联：一条边的端点和边关联 环：端点重合的边 重边：端点相同的边（两条以上) 有限图：顶点集和边集都是有限的图 平凡图：只有一个项点的图 简单图：不含重边和环的图
相邻：同一条边的两个端点称为相邻 环：端点重合的边 重边：端点相同的边（两条以上） 有限图：顶点集和边集都是有限的图 平凡图：只有一个顶点的图 简单图：不含 和 的图 关联：一条边的端点和边关联
图：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,BDY :={e1,e2,e3,e4,e5,e6,e7} e4 边数：IE=e(G)=7 e2 e3 顶点v的度数d(w):与v关联的边的条数 B d(A)=5,d(B)=3,de=3,d(D)=3 e6 e7 注：一个环（如果存在的话）算两条边 d(C)=5
图：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 顶点v的度数d(v)：与v关联的边的条数 d(A)=5,d(B)=3,d(C)=3,d(D)=3 注：一个环（如果存在的话）算两条边 d(C)=5 e1 e2 e4 e5 e3 e6 e7 e8
●最大度：△(G)=max{d(v)川v∈V ●最小度：(G)=min{d(v)川v∈V} 最大度=5，在点A处达到 A B 最小度=3，在点B,C,D处达到 D
最大度： 最小度： (G) = max{d(v)| v V} (G) = min{d(v)| v V} 最大度=5，在点A处达到 最小度=3，在点B,C,D处达到
度和关系式： ∑d()=2e vel (1)图中每条不是环的边恰好关联2个顶点； (2)图中每个环只关联1个顶点，但一个环算2条边 推论：在任何图中，奇度点个数为偶数 奇数×？+偶数x偶数或者奇数=偶数
( ) 2 . v V d v = 推论：在任何图中，奇度点个数为偶数 度和关系式： （1）图中每条不是环的边恰好关联2个顶点； （2）图中每个环只关联1个顶点，但一个环算2条边 奇数 x ？+ 偶数 x 偶数或者奇数 = 偶数
e ■途径：图中点边交替出现的有限序列（以点开始，以点结束） e26 V1 e12 V2 e23 V3 e23 V2 ■迹：一条边互不相同的途径 e e V1 e12 V2 e23 V3 e34 V4 eso e ●路：一条点互不相同的迹 V1 e12 V2 e23 V3 e34 V4 e Eu1er迹：经过图的每一条边的迹 eas 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图：存在Euleri环游的图
途径：图中点边交替出现的有限序列（以点开始，以点结束） v1 e12 v2 e23 v3 e23 v2 迹：一条边互不相同的途径 v1 e12 v2 e23 v3 e34 v4 路：一条点互不相同的迹 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环游的图
引理1：若简单图G的最小度至少为k父2 则G包含一个边数至少为k+1的圈。 证明：取图G的一条长度最长的路P, 其经过的点依次记为Vo,V1,Vt-1Vt 则点Vo与点V的邻点都在路P上（为什么？) 由于G的最小度至少为k,故点V至少有k个邻点 设其为V12Vk（ik之≥i2≥1) 从而有t≥ik之k 于是，V0V1VkVo为图G中的一个包含ik+1≥k+1条边的圈
引理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条边的圈