西安电子科技大学离散数学软件学院家第四篇图论第6章图论第27-28课时6.1图的基本概念（1）第29课时6.2路径与回路A第30课时6.3图的矩阵表示第32课时6.4欧拉图与汉密尔顿图（2)A第33课时6.5平面图第34课时6.6图的着色6.7 树第35-36课时第37-38课时6.8图的应用
西安电子科技大学 离散数学 软件学院 第四篇 图论 6.1 图的基本概念（1） 第6章 图论 6.4 欧拉图与汉密尔顿图（2） 6.2 路径与回路 6.5 平面图 第29课时 第33课时 第30课时 6.3 图的矩阵表示 第34课时 6.6 图的着色 第32课时 第35－36课时 6.7 树 第27－28课时 第37－38课时 6.8 图的应用
西安电子科技大学$6.4.2汉密尔顿图软件学院1859年爱尔兰数学家威廉·汉密尔顿（WillianHamilton）爵士在给他的朋友的一封信中，首先谈到一个称为“周游世界”的数学游戏。他将正十二面体的20个结点均标上重要城市的名称，希望能够沿着正十二面体的棱行走，找到一个遍历每个城市恰一次的周游。如果我们将正十二面体的结点和边画在一个平面，如图所示，“周游世界”游戏相当于在图中找到一条经过每个结点一次且仅一次的回路，（a）所示。这个问题是有解的，见图（b）的粗线所示
西安电子科技大学 §6.4.2 汉密尔顿图 软件学院 1859年爱尔兰数学家威廉·汉密尔顿（Willian Hamilton）爵士在给他的朋友的一封信中，首先谈 到一个称为“周游世界”的数学游戏。他将正十二 面体的20个结点均标上重要城市的名称，希望能够 沿着正十二面体的棱行走，找到一个遍历每个城市 恰一次的周游。 如果我们将正十二面体的结点和边画在一个平面，如图所 示，“周游世界”游戏相当于在图中找到一条经过每个结点 一次且仅一次的回路，（a）所示。这个问题是有解的，见 图（b）的粗线所示
西安电子科技大学$6.4.2汉密尔顿图软件学院经过图G-中的每个结点一次且仅一次的路径。汉密尔顿路径汉密尔顿回路经过图G-中的每个结点一次且仅一次的回路。汉密尔顿图含哈密尔顿回路的图
西安电子科技大学 软件学院 汉密尔顿路径 §6.4.2 汉密尔顿回路 汉密尔顿图 汉密尔顿图
西安电子科技大学$6.4.2汉密尔顿图软件学院家【例题1判断下图是否为哈密尔顿图，如果是，请写出一条哈密尔顿回路否则证明其不是哈密尔顿图。+解答：该图是哈密尔顿图，哈密尔顿回路为：chfigideabc
西安电子科技大学 §6.4.2 汉密尔顿图 软件学院
西安电子科技大学S6.4.2汉密尔顿图软件学院以下是哈密尔顿图的一个必要条件案定理」若图G-是哈密尔顿图，则对于结点集V的每个非空子集S均满足：U (G-S) ≤S其中，IS表示S中的结点数，①(G-S)表示G删除S中所有结点后得到的连通分支个数。汉密尔顿回路
西安电子科技大学 软件学院 汉密尔顿回路 C vi vj §6.4.2 汉密尔顿图
西安电子科技大学$6.4.2汉密尔顿图软件学院【例题】判断下列图（a）（b）所示的图是不是哈密尔顿图(a)(b)+解答：R(a)(b)+
西安电子科技大学 §6.4.2 汉密尔顿图 软件学院
西安电子科技大学$6.4.2汉密尔顿图软件学院教家教奥尔（Ore）1960年建立了哈密尔顿图的以下充分条件：案「定理」设G-是含有I（I3）个结点的简单无向图，如果G中的每一对结点的度数之和都大于等于I-1，则G中存在哈密尔顿路径。+
西安电子科技大学 §6.4.2 汉密尔顿图 软件学院
西安电子科技大学S6.4.2汉密尔顿图软件学院家家证明（1）首先，证明G是连通的（反证法）假设G中存在两个或更多个互不连通的分支。设G中的结点vi和vj分别属于两个不同的连通分支G1和G2，其中G1和G2分别有n1和n2个结点。显然，nl<n且n2<n，于是有deg(vi)<nl-1且deg(vj) ≤n2-1, 则deg(vi)+deg(vi) ≤n1+n2-2=n2。这与已知题设矛盾，假设错误，G是连通的
西安电子科技大学 §6.4.2 汉密尔顿图 软件学院 证明 （1）首先，证明G是连通的（反证法）。 假设G中存在两个或更多个互不连通的分支。设G 中的结点vi和vj分别属于两个不同的连通分支G1和 G2，其中G1和G2分别有n1和n2个结点。 显然，n1<n且n2<n，于是有deg(vi) ≤n1-1且 deg(vj) ≤n2-1, 则deg(vi)+deg(vj) ≤n1+n2-2=n- 2。 这与已知题设矛盾，假设错误，G是连通的
西安电子科技大学66.4.2汉密尔顿图软件学院家家（2）其次，证明G中有汉密尔顿路。在G中找到一条长度为p-1(O<p<n)的基本路径（通路），如图所示，则该基本路径中含p个结点，设这些结点为：V1，V2,", Vp我们扩充这条基本路径：(a）如果v,或v.还邻接于不在这条路径上的某个结点，则可立即延伸这条路以包含该结点，得P条边，p+1个结点的基本路径。(b）如果v,和v,均只与该基本路径中的结点邻接，那么接下来我们证明“存在一条包含结点V1，V2,，Vp的基本回路（圈）
西安电子科技大学 §6.4.2 汉密尔顿图 软件学院 （2）其次，证明G中有汉密尔顿路。 在G中找到一条长度为p-1(0<p<n)的基本路径（通路）， 如图所示，则该基本路径中含p个结点，设这些结点为：v1, v2,., vp。 我们扩充这条基本路径： （a）如果v1或vp还邻接于不在这条路径上的某个结 点，则可立即延伸这条路以包含该结点，得p条边， p+1个结点的基本路径。 （b）如果v1和vp均只与该基本路径中的结点邻接， 那么接下来我们证明“存在一条包含结点v1, v2,., vp 的基本回路（圈）
西安电子科技大学$6.4.2汉密尔顿图软件学院(i）如果vi与v邻接，则得到一条包含结点Vi，V2V.的基本回路。（ii）如果vi与v,不邻接。不妨设v,邻接于Vi，Yi2，,Vik(2≤ik≤p-1)这k个结点（k≤p-2），则v,至少与Vi11，Vi2-1，，Vik-1中之一邻接。若不然，则v,至多与p-k-1个结点（除Vi1-1，Vi2-1，"，Vik-1外还包含V,自身）邻接。因而deg(vi)+deg(vp)≤pk-1+k=p-1≤n-2，这与已知题设矛盾。?设v1与vit邻接且vp与vit-1邻接，如图所示可以得到基本回路(vl, v2,..-, vit-1, vp, vp-1,.", vit, vl)
西安电子科技大学 §6.4.2 汉密尔顿图 软件学院 （i）如果v1与vp邻接，则得到一条包含结点v1, v2,., vp的基本回路。 （ii）如果v1与vp不邻接。不妨设v1邻接于vi1, vi2, ., vik(2≤ik≤p-1)这k个结点（k≤p-2），则vp至少与vi1- 1, vi2-1, ., vik-1中之一邻接。 若不然，则vp至多与p-k-1个结点（除vi1-1, vi2-1, ., vik-1外还包含vp自身）邻接。因而deg(v1)+deg(vp)≤p- k-1+k=p-1≤n-2，这与已知题设矛盾。 设v1与vit 邻接且vp与vit-1邻接，如图所示可以得到基本回路 (v1, v2,., vit-1, vp, vp-1,., vit, v1)