图论7课件1.pptVIP

数学科学学院 杨春 Email：yc517922@126.com * 第11章　特殊图 11.2　Euler图 哥尼斯堡七桥问题： 欧拉图的定义 定义11.2.1　设G是无孤立结点的图，若存在一 例1 图a和图d是欧拉图；图b和图e不是欧拉图，但存在欧拉通路；图c和图f不存在欧拉通路。 “一笔画问题” 判断无向欧拉通路的方法 定理11.2.1　无向图G＝V，E具有一条欧拉通路当且仅当G是连通的，且仅有零个或者两个奇度数结点。若有两个奇度数结点，则它们是G中每条欧拉通路的端点。 判断无向欧拉图的方法 推论11.2.2　无向图G＝V，E是欧拉图当且仅当G是连通的，且G的所有结点的度数都为偶数。 例2 由定理11.2.2容易看出： 一笔画问题 对于上图，有 图(a)能一笔画并且能回到出发点的， 图(b)能一笔画但不能回到出发点的。 判断有向欧拉通路、欧拉图的方法 定理11.2.3　有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。 推论11.2.4　有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。 例3 图a)存在一条的欧拉通路：v3v1v2v3v4v1； 图(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b)是欧拉图； 图(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是欧拉图。 Fleury算法 任取v0∈V，令P0＝v0； 设P0＝v0e1v1e2…eivi，按下面的方法从E-{e1,e2,…,ei}中选取ei+1： ei+1与vi相关联； 除非无别的边可选取，否则ei+1不应该为G＝G-{e1,e2,…,ei}中的桥； 当2）不能再进行时，算法结束。 例4 　　在右图所示的欧拉图 中，求从v1出发的欧拉回 路。 13.2　哈密尔顿图 周游世界问题 11.3 哈密尔顿图的定义 定义11.3.1　经过图中每个结点一次且仅一次的通路（回路）称为哈密尔顿通路（回路）。存在哈密尔顿回路的图称为哈密尔顿图。 规定平凡图为哈密尔顿图。 例5 既存在哈密尔顿通路，又存在哈密尔顿回路，即为哈密尔顿图。 定理11.3.1 设无向图G＝V,E是哈密尔顿图，V1是V的任意非空子集，则 p(G-V1)≤|V1| 其中p(G-V1)是从G中删除V1后所得到图的连通分支数。 证明 设C是G中的一条哈密尔顿回路，V1是V的任意非空子集。下面分两种情况讨论： V1中结点在C中均相邻，删除C上V1中各结点及关联的边后，C-V1仍是连通的，但已非回路，因此p(C-V1)＝1≤|V1|。 V1中结点在C上存在r(2≤r≤|V1|)个互不相邻，删除C上V1中各结点及关联的边后，将C分为互不相连的r段，即p(C-V1)＝r≤|V1|。 一般情况下，V1中的结点在C中即有相邻的，又有不相邻的，因此总有p(C-V1)≤|V1|。 又因C是G的生成子图，从而C-V1也是G-V1的生成子图，故有 p(G-V1)≤p(C-V1)≤|V1| 推论13.3.1 设无向图G＝V,E中存在哈密尔顿通路，则对V的任意非空子集V1，都有 p(G-V1)≤|V1|＋1 注意 定理给出的是哈密尔顿图的必要条件，而不是充分条件。下图所示的彼得森图，对V的任意非空子集V1，均满足p(G-V1)≤|V1|，但它不是哈密尔顿图。 定理11.3.2 设G＝V,E是具有n个结点的简单无向图。如果对任意两个不相邻的结点u,v∈V，均有 deg(u)+deg(v)≥n-1 则G中存在哈密尔顿通路。 推论 推论11.3.2　设G＝V,E是具有n个结点的简单无向图。如果对任意两个不相邻的结点u,v∈V，均有 deg(u)+deg(v)≥n 则G中存在哈密尔顿回路。 推论11.3.3　设G＝V,E是具有n个结点的简单无向图，n≥3。如果对任意v∈V，均有 deg(v)≥n/2， 则G是哈密尔顿图。 例6 某地有5个风景点，若每个风景点均有两条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？ 解　将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密尔顿通路，因此本题有解。 例7 证明下图(a)所示的图中，不存在哈密尔顿回路。 例7 判断右图所示的图是否存在哈密尔顿回路。　 定理11.3.3 设G＝V,E是有n(n≥2)个结点的一些简单 * * 条通路（回路），经过图中每边一次且仅一次， 则称此通路（回路）为该图的一条欧拉通路（回 路）。具有