图论4课件.ppt

雄关漫道真如铁，而今迈步从头越！ 26--* 证明(续3) 证明存在比P更长的路径。 因为k＜n，所以V中还有一些结点不在C中，由G的连通性知，存在C外的结点与C上的结点相邻，不妨设vk+1∈V－V(C)且与C上结点vt相邻，在C中删除边(vt-1,vt)而添加边(vt,vk+1)得到路径P＝vt-1…v1vir…vkvir-1…vtvk+1。显然，P比P长1，且P上有k+1个不同的结点。 对P重复1）～3），得到G中的哈密尔顿路径或比P更长的基本路径，由于G中结点数目有限，故在有限步内一定得到G中的一条哈密尔顿路径。 雄关漫道真如铁，而今迈步从头越！ 26--* 例8.4 某地有5个风景点，若每个风景点均有两条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？ 解　将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密尔顿路径，因此本题有解。 雄关漫道真如铁，而今迈步从头越！ 26--* 例8.6 判断右图所示的图是否存在哈密尔顿回路。　 解　若该图中存在哈密尔顿回路，则该回路组成的图中任何结点的度数均为 2。因而结点1、2、3、4、5所关联的边均在回路中，于是在结点a、b、c、d、e处均应将不与1、2、3、4、5关联的边删除，而要删除与结点a、b、c、d、e关联的其他边，这样一来，图就不连通了，因而图中不存在哈密尔顿回路。 雄关漫道真如铁，而今迈步从头越！ 26--* 例 　　证明右图所示的图中 没有哈密尔顿路径。 证明　任取一结点如1用A标记，所有与它邻接的结点用B标记。继续不断地用 A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直到所有结点都标记完毕。 如果图中有一条哈密尔顿路径，那么它必交替通过结点A和B，故而或者结点A与结点B数目相同，或者两者相差1个。然而该图中有3个结点标记为A，5个结点标记为B，它们相差两个，所以该图不存在哈密尔顿路径。 雄关漫道真如铁，而今迈步从头越！ 26--* 定理（补充） 设G＝V,E是有n(n≥2)个结点的一些简单 例　在右图中，它所对应的无向图中含完全图K5，由定理知，图中含有哈密尔顿路径。事实上，路径v3v5v4v2v1为一条哈密尔顿路径。 有向图。如果忽略G中边的方向所得的无向图中 含生成子图Kn（Kn是含n个结点的无向完全图）， 则有向图G中存在哈密尔顿路径。 雄关漫道真如铁，而今迈步从头越！ 26--* 巡回售货员问题 最邻近算法 雄关漫道真如铁，而今迈步从头越！ 26--* 第262页 13 14 19 习　题 * 回顾命题演算的永真公式和几条规则 雄关漫道真如铁，而今迈步从头越！ C S | S W U S T XDC 雄关漫道真如铁，而今迈步从头越！ 雄关漫道真如铁，而今迈步从头越！ 26--* * 第8章图论 雄关漫道真如铁，而今迈步从头越！ 26--* 特殊图 8.2　Euler路径和Euler图 哥尼斯堡七桥问题： 雄关漫道真如铁，而今迈步从头越！ 26--* 欧拉图的定义 定义　设G是无孤立结点的图，若存在一 条路径（回路），经过图中每边一次且仅一次， 则称此路径（回路）为该图的一条欧拉路径（回 路）。具有欧拉回路的图称为欧拉图。 　　规定平凡图为欧拉图。 　　欧拉路径是经过图中所有边的路径中长度最短的路径（即为通过图中所有边的简单路径）； 　　欧拉回路是经过图中所有边的回路中长度最短的回路（即为通过图中所有边的简单回路）。 雄关漫道真如铁，而今迈步从头越！ 26--* 例8.1 图a和图d是欧拉图；图b和图e不是欧拉图，但存在欧拉路径；图c和图f不存在欧拉路径。 雄关漫道真如铁，而今迈步从头越！ 26--* 判断无向欧拉路径的方法 定理8.2-4　无向图G＝V，E具有一条欧拉路径当且仅当G是连通的，且仅有零个或者两个奇度数结点。若有两个奇度数结点，则它们是G中每条欧拉路径的端点。P255 雄关漫道真如铁，而今迈步从头越！ 26--* 若G＝(1，0)是一个平凡图，则定理显然成立。 证明 下面讨论G是非平凡图的情况。 “?”设G具有一条Euler路径L。 ①设该欧拉路径L＝v0e1v1e2v2e3……ekvk。即从v0出发，经过结点v1，v2，……vk-1，边e1，e2……ek到达vk，其中的结点可以重复出现，但边不重复，并且L中的边是包括了G中所有的边。由于G中无孤立结点，因而L经过了G中的所有结点，所以G是连通的。 ②对于欧拉路径L的任意非端点的结点vi，在L中每出现vi一次，都关联着G中的两条边，而当vi又重复出现时，它又关联着G中的另外的