离散数学 第七章图论-2.ppt

国际学院 第7章　特殊图 7.1　Euler图 哥尼斯堡七桥问题： 欧拉图的定义 定义7.1　设G是无孤立结点的图，若存在一 例7.1 图a和图d是欧拉图；图b和图e不是欧拉图，但存在欧拉路；图c和图f不存在欧拉路。 “一笔画问题” 判断无向欧拉通路的方法 定理7.1　无向图G＝V，E具有一条欧拉路当且仅当G是连通的，且仅有零个或者两个奇度数结点。若有两个奇度数结点，则它们是G中每条欧拉路的端点。 证明 若G＝(1，0)是一个平凡图，则定理显然成立。 证明(续1) 若端点v0?vk，设v0，vk在路中作为非端点分别出 证明(续2) “?”构造性证明。 证明(续3) 由这些结点中的一个开始我们再通过边构造路， 判断无向欧拉图的方法 推论7.1　无向图G＝V，E是欧拉图当且仅当G是连通的，且G的所有结点的度数都为偶数。 例 由定理7.1容易看出： 一笔画问题 对于上图，有 图(a)能一笔画并且能回到出发点的， 图(b)能一笔画但不能回到出发点的。 判断有向欧拉路、欧拉图的方法 定理7.2　有向图G具有一条欧拉路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。 推论7.2　有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。 例 图a)存在一条的欧拉路：v3v1v2v3v4v1； 图(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b)是欧拉图； 图(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是欧拉图。 例7.2(蚂蚁比赛问题) 甲、乙两只蚂蚁分别位于右图 例7.3 　　在右图所示的欧拉图 中，求从v1出发的欧拉回 路。 7.2　汉密尔顿图 周游世界问题 汉密尔顿图的定义 定义7.2　经过图中每个结点一次且仅一次的路（回路）称为汉密尔顿路（回路）。存在汉密尔顿回路的图称为汉密尔顿图。 规定平凡图为汉密尔顿图。 汉密尔顿路是经过图中所有结点的路中长度最短的通路； 汉密尔顿回路是经过图中所有结点的回路中长度最短的回路。 例 既存在汉密尔顿路，又存在汉密尔顿回路，即为汉密尔顿图。 定理7.3 设无向图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| 注意 定理7.3给出的是汉密尔顿图的必要条件，而不是充分条件。下图所示的彼得森图，对V的任意非空子集V1，均满足p(G-V1)≤|V1|，但它不是汉密尔顿图。 定理7.4 设G＝V,E是具有n个结点的简单无向图。如果对任意两个不相邻的结点u,v∈V，均有 deg(u)+deg(v)≥n-1 则G中存在汉密尔顿路。 证明 首先证明满足上述条件的G是连通图。否则G有两个或更多连通分支。设一个连通分支有n1个结点，另一个连通分支有n2个结点。这二个连通分支中分别有两个结点v1、v2。显然，deg(v1)≤n1-1，deg(v2)≤n2-1。从而deg(v1)＋deg(v2)≤n1+n2-2≤n-2与已知矛盾，故G是连通的。 其次，证明G中存在汉密尔顿路。 设P＝v1v2…vk为G中用“延长路法”得到的“极大路”，即P的始点v1与终点vk不与P外的结点相邻，显然k≤n。 证明(续1) 若k＝n，则P为G中经过所有结点的路，即为汉密尔顿通路。 若k＜n，说明G中还有在P外的结点，但此时可以证明存在仅经过P上所有结点的基本回路，证明如下： 若在P上v1与vk相邻，则v1v2…vkv1为仅经过P上所有结点的基本回路。 证明(续2) 若在P上v1与vk不相邻，假设v1在P上与vi1=v2,vi2,vi3,…,vij相邻（j必定大于等于2，否则deg(v1)+deg(vk)≤1+k-2＜n-1），此时vk必与vi2,vi3,…,vij相邻的结点vi2-1,vi3-1,…,vij-1至少之一相邻（否则deg(v1)+deg(vk)≤j+k-2-(j-1)＝k-1＜n-1）。设vk与vir-1（2≤r≤j）相邻，如下图所示。