第11章特殊图105.ppt

《第11章特殊图105.ppt》由会员分享，可在线阅读，更多相关《第11章特殊图105.ppt（62页珍藏版）》请在三一办公上搜索。

1、离 散 数 学,第11章 特殊图,2023/11/18,11.2 欧拉图,11.2.1 欧拉图的引入与定义,定义11.2.1设G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(Eulerian Entry/Circuit)。具有欧拉回路的图称为欧拉图(Eulerian Graph)。规定：平凡图为欧拉图。以上定义既适合无向图，又适合有向图。,2023/11/18,例11.2.1判断下面的6个图中，是否是欧拉图？是否存在欧拉通路？,欧拉图,欧拉图,不是欧拉图，但存在欧拉通路,不存在欧拉通路,不存在欧拉通路,不是欧拉图，但存在欧拉

2、通路,2023/11/18,11.2.2-4 欧拉图的判定及应用,定理11.2.1（含推论11.2.1）（1）无向图G=是欧拉图，当且仅当G是连通的，且仅有零个奇度数结点。（2）无向图G=有欧拉通路但不是欧拉图，当且仅当G是连通的，并且恰有两个奇度数结点。（两个奇度数结点必是G中每条欧拉通路的端点）,2023/11/18,定理11.2.2 有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。推论11.2.2 有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。,

3、例如，对完全图 Kn，因 d(Kn)=n-1，故当n为奇数时是欧拉图，当n为偶时不是欧拉图。,图 G 有欧拉通路,G 能“一笔画”,G 连通且 G 中度数为奇数的点的个数不超过2,2023/11/18,定义11.2.2 设G=，eE，如果p(G-e)p(G)称e为G的桥(Bridge)或割边(Cut edge)。显然，所有的悬挂边都是桥。,求一个欧拉图的欧拉回路的Fleury算法的简述：从任一点出发按下法来描画一条边不重复的通路，使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画。,2023/11/18,例,例：,2023/11/18,例11.2.3,图中的三个图能否一笔画？为什么？

4、,解 因为图(a)和(b)中分别有0个和2个奇度数结点，所以它们分别是欧拉图和存在欧拉通路，因此能够一笔画，并且在(a)中笔能回到出发点，而(b)中笔不能回到出发点。图c中有4个度数为3的结点，所以不存在欧拉通路，因此不能一笔画。,2023/11/18,例11.2.4 蚂蚁比赛问题,甲、乙两只蚂蚁分别位于图的结点A、B处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？,解 图中仅有两个度数为奇数的结点B、C，因而存在从B到C的欧拉通路，蚂蚁乙走到C只要走一条欧拉通路，边数为9条，而蚂蚁甲要想走完所有的边到达C，

5、至少要先走一条边到达B，再走一条欧拉通路，因而它至少要走10条边才能到达C，所以乙必胜。,2023/11/18,11.3 哈密顿图,11.2.1 哈密顿图的引入与定义,定义11.3.1 经过图中每个结点一次且仅一次的通路(回路)称为哈密顿通路(回路)。存在哈密顿回路的图称为哈密顿图。规定：平凡图为哈密顿图。以上定义既适合无向图，又适合有向图。,2023/11/18,二、Hamilton图,例,例2,只有哈密尔顿通路，但不是哈密尔顿图,哈密尔顿图,无哈密尔顿通路,2023/11/18,例：对下面的图,v3,v1,v2,v4,(a),v3,v1,v2,v4,(d),v3,v1,v2,v4,(b),

6、v5,v6,v7,v3,v1,v2,v4,(e),v3,v1,v2,v4,(f),哈密顿图,不存在哈密顿通路,哈密顿图,不是哈密顿图，但存在哈密顿通路,不存在哈密顿通路,2023/11/18,11.3.2 哈密顿图的判定,定理11.3.1 设无向图G=是哈密顿图，V1是V的任意非空子集，则p(G-V1)|V1|其中p(G-V1)是从G中删除V1后所得到图的连通分支数。,证明 设C 是G 中一条哈密尔顿回路。任取 V 中非空子集V，因 C 是G 的哈密尔顿回路含G 的所有点，故V 也是子图 C 的非空子集。由点不重复的回路的特性知任意删去C 中|V|个点，最多将C 分为|V|“段”，即 P(C-

7、V)|V|（*）,而 C 是 G 的生成子图，又有：P(G-V)(C-V)所以 P(G-V)|V|,2023/11/18,推论11.3.1设无向图G=中存在哈密顿通路，则对V的任意非空子集V1，都有p(G-V1)|V1|+1,例 下列图不是哈密顿图，其中V1=蓝色记号。,2023/11/18,例11.3.2,证明图中不存在哈密顿回路。,证明 在图中，删除结点子集d,e,f，得新图，它的连通分支为4个，由定理11.3.1知，该图不是哈密顿图，因而不会存在哈密顿回路。,2023/11/18,可验证彼得森图（下图）不是哈密尔顿图，但满足 p(G-V1)|V1|。这表明定理11.3.1给出的条件只是图

8、 G 是哈密尔顿图的必要条件而不是充分条件。,2023/11/18,例 设G=是具有n个结点的简单无向图。如果对任意两个不相邻的结点u,vV，均有 deg(u)+deg(v)n-1则G是连通的。证明 用反证法：假设G有两个或更多连通分支。设一个连通分支有n1个结点，另一个连通分支有n2个结点。这二个连通分支中分别有两个结点v1、v2。显然，deg(v1)n1-1，deg(v2)n2-1。从而 deg(v1)+deg(v2)n1+n2-2 n-2与已知矛盾，故G是连通的。,2023/11/18,定理11.3.2 设G=是具有n个结点的简单无向图。如果对任意两个不相邻的结点u,vV，均有deg(u

9、)+deg(v)n-1则G中存在哈密顿通路。推论11.3.2 设G=是具有n个结点的简单无向图。如果对任意两个不相邻的结点u,vV，均有deg(u)+deg(v)n则G中存在哈密顿回路。,推论11.3.3 设G=是具有n个结点的简单无向图，n3。如果对任意vV，均有deg(v)n/2，则G是哈密顿图。,2023/11/18,由推论11.3.2可知当n3时 Kn是哈密尔顿图。,故该定理的条件是一个图是哈密尔顿图的充分条件,但不是必要条件。,是哈密尔顿图，但不满足推论11.3.2的条件,2023/11/18,例11.3.3,某地有5个风景点，若每个风景点均有2条道路与其他点相通。问游人可否经过每个

10、风景点恰好一次而游完这5处？解 将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密顿通路，因此游人可以经过每个风景点恰好一次而游完这5处。,2023/11/18,例11.3.4 判断下图是否存在哈密顿回路。,解 方法一：在图中，删除结点子集a,b,c,d,e，得到的图有7个连通分支，由定理11.2.1知，该图不是哈密顿图，因而不会存在哈密顿回路。,方法二：若图中存在哈密顿回路，则图中度数为2的结点1、2、3、4、5 所关联的边必在回

11、路中，而这些边已够成一个回路,但此回路不是哈密顿回路,因而图中不存在哈密顿回路。,2023/11/18,例11.3.5,证明下图没有哈密顿通路。,证明 任取一点(如1)用A标记，所有与1邻接的点用B标记。继续不断地用A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直到所有结点都标记完毕。如果图中有一条哈密顿通路，那么它必交替通过结点A和B，故而标记A的结点与标记B的结点数目或者相同，或者相差1个。然而图中有3个结点标记为A，5个结点标记为B，它们相差两个，所以该图不存在哈密顿通路。,2023/11/18,定理11.3.3,设G=是有n(n2)个结点的一些简单有向图。如果忽略G中边的方向所

12、得的无向图中含生成子图Kn，则有向图G中存在哈密顿通路。,在右图中，它所对应的无向图中含完全图K5，由定理11.3.3知，图中含有哈密顿通路。事实上，通路v3v5v4v2v1为一条哈密顿通路。,2023/11/18,11.3.4 哈密顿图的应用,1、巡回售货员问题简介,问题：一个巡回售货员想访问若干城市（假定各城镇之间均有路可通），然后返回。问如何安排路线使其能恰好访问每个城镇一次且走过的总路程最短？这个问题称为巡回售货员问题，它的图论模型为：在赋权完全图G 中求具有最小权(最短)的哈密尔顿回路。,2023/11/18,8,16,7,12,4,例11.3.6,回路的总距离为47,一个最短的哈密

13、尔顿回路为:cdaebc，总距离为：35,2023/11/18,2、中国邮路问题,一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢？如果将这个问题抽象成图论的语言，就是给定一个连通图，连通图的每条边的权值为对应的街道的长度(距离)，要在图中求一回路，使得回路的总权值最小。,2023/11/18,中国邮路问题,若图为欧拉图，只要求出图中的一条欧拉回路即可。否则，邮递员要完成任务就得在某些街道上重复走若干次。如果重复走一次，就加一条平行边，于是原来对应的图就变成了多重图。只是要求加进的平行边的总权值最小就行了。问题就转化为：在一个有奇度数结点

14、的赋权连通图中，增加一些平行边，使得新图不含奇度数结点，并且增加的边的总权值最小。,2023/11/18,解决问题的步骤,要解决上述问题，应分下面两个大步骤。首先，增加一些边，使得新图无奇度数结点，我们称这一步为可行方案(Feasible Scheme)；其次，调整可行方案，使其达到增加的边的总权值最小，称这个最后的方案为最佳方案(Optimal Scheme)。,有下面的结论：一个可行方案是最优方案中当且仅当 I）图中每条边的重数小于等于2；2）图中每个基本回路上平行边的总权值不大于该回路的权值的一半。,2023/11/18,例11.3.8,在下图中，确定一条v1从v1到的回路，使它的权值最

15、小。事实上，所确定的回路从任何一个结点出发都可以。,2023/11/18,平行边的总权值为：W(v1,v2)+W(v2,v3)+W(v4,v5)+W(v5,v6)=5,上图满足I)、II)两条，从而是最佳方案，即图中的任意一条欧拉回路均为邮递员的最佳送信路线。,解：,2023/11/18,11.4 偶图,11.4.1-2 偶图的定义及判定定义11.4.1 若无向图G=的结点集V能够划分为两个子集V1,V2，满足V1V2=，且V1V2=V，使得G中任意一条边的两个端点，一个属于V1，另一个属于V2，则称G为偶图(Bipartite Graph)或二分图(Bigraph)。V1和V2称为互补结点子

16、集，偶图通常记为G=。偶图没有自回路。平凡图和零图可看成特殊的偶图。,2023/11/18,定义11.4.2 偶图G=中，若V1中的每个结点与V2中的每个结点都有且仅有一条边相关联，则称偶图G为完全偶图或完全二分图，记为Ki,j，其中，i=|V1|，j=|V2|。,2023/11/18,定理11.4.1 一个无向图是偶图当且仅当它不含长度为奇的回路。,例,偶图,不是偶图,证明 必要性：设图G是偶图G=，令C=v0v1v2vkv0是G的一条回路，其长度为k+1。不失一般性，假设v0V1，由偶图的定义知，v1V2，v2V1。由此可知，v2iV1且v2i+1V2。又因为v0V1，所以vkV2，因而k

17、为奇数，故C的长度为偶数。,2023/11/18,充分性：设G中每条回路的长度均为偶数，若G是连通图，任选v0V，定义V的两个子集如下：V1=vi|d(v0,vi)为偶数，V2=V-V1。现证明V1中任两结点间无边存在。假若存在一条边(vi,vj)E，其中vi,vjV1，则由v0到vi间的短程线(长度为偶数)以及边(vi,vj)，再加上vj到v0间的短程线(长度为偶数)所组成的回路的长度为奇数，与假设矛盾。,同理可证V2中任两结点间无边存在。故G中每条边的端点分属于V1与V1，因此G是具有互补结点子集V1和V2的偶图。若G不连通，则可对G的每个连通分支重复上述论证，也可得到同样的结论。,202

18、3/11/18,例：,不是偶图,完全偶图K3,3,又由定理知至少两个点的树是偶图。,2023/11/18,11.4.3 匹配,定义11.4.2 在偶图G=中，V1=v1,v2,vq，若存在E的子集E=(v1,v1)，(v2,v2)，(vq,vq)，其中v1,v2,vq 是V2中的q个不同的结点，则称G的子图G=为从V1到V2的一个完全匹配(Complete Matching)，简称匹配。,由定义：偶图G=中，若存在V1到V2的单射f，使得对任意vV1，都有(v,f(v)E，则存在V1到V2的匹配。故由单射的性质知，存在V1到V2的匹配的必要条件是|V1|V2|然而，这个条件并不是充分条件。,2

19、023/11/18,例11.4.2,下面的3个偶图哪些存在V1到V2匹配？对存在匹配的偶图给出一个匹配。,不存在匹配,不存在匹配,存在匹配,2023/11/18,霍尔定理,定理11.4.2(霍尔定理)偶图G=中存在从V1到V2的匹配的充分必要条件是V1中任意k个结点至少与V2中的k个结点相邻，k=1,2,|V1|。定理11.4.2中的条件通常称为相异性条件(Diversity Condition)。,2023/11/18,例,不满足相异性条件，故没有匹配。,满足相异性条件，故存在匹配,2023/11/18,定理11.4.3,设G=是一个偶图。如果满足条件（1）V1中每个结点至少关联t条边；（2

20、）V2中每个结点至多关联t条边；则G中存在从V1到V2的匹配。其中t为正整数。证明 由条件(1)知，V1中k个结点至少关联tk条边(1k|V1|)，由条件(2)知，这tk条边至少与V2中k个结点相关联，于是V1中的k个结点至少与V2中的k个结点相邻接，因而满足相异性条件，所以G中存在从V1到V2的匹配。,定理11.4.3中的条件通常称为t条件(t-Condition)。,判断t条件非常简单，只需要计算V1中结点的最小度数和V2中结点的最大度数即可。,2023/11/18,11.4.5 偶图的应用,例11.4.3 有n台计算机和n个磁盘驱动器。每台计算机与m0个磁盘驱动器兼容，每个磁盘驱动器与m

21、台计算机兼容。能否为每台计算机配置一台与它兼容的磁盘驱动器？解 用V1表示n台计算机的集合，V2表示n台磁盘驱动器的集合。以V1，V2为互补结点子集，以E=(vi,vj)|viV1,vjV2且vi与vj兼容为边集，构造偶图。它显然满足t条件(t=m)，所以存在匹配，故能够为每台计算机配置一台与它兼容的磁盘驱动器。,2023/11/18,例11.4.4,现有三个课外小组：物理组，化学组和生物组，有五个学生s1,s2,s3,s4,s5。（1）已知s1,s2为物理组成员；s1,s3,s4为化学组成员；s3,s4,s5为生物组成员。（2）已知s1为物理组成员；s2,s3,s4为化学组成员；s2,s3,

22、s4,s5为生物组成员。（3）已知s1即为物理组成员，又为化学组成员；s2,s3,s4,s5为生物组成员。在以上三种情况的每一种情况下，在s1,s2,s3,s4,s5中选三位组长，不兼职，问能否办到？,2023/11/18,解,用c1,c2,c3分别表示物理组、化学组和生物组。V1=c1,c2,c3，V2=s1,s2,s3,s4,s5以V1，V2为互补结点子集，以 E=(ci,sj)|ciV1,sjV2且ci中有成员sj为边集，构造偶图。,不存在匹配,2023/11/18,11.5 平面图,11.5.1 平面图的定义,2023/11/18,问题：假定有三个仓库 x1，x2，x3 和三个车站 y

23、1，y2，y3。为了便于货物运输，准备在仓库与车站间修筑铁路，如图(a)所示,其中边代表铁路。问是否存在一种使铁路不交叉的路线设计方案，以避免修建立交桥。,问题的解答,但如果在 x3 与y1 之间也要修一条铁路，则可验证满足要求的方案不存在。,?,2023/11/18,定义11.5.1,如果能把一个无向图G的所有结点和边画在平面上，使得任何两边除公共结点外没有其他交叉点，则称G为平面图(Plane Graph)，否则称G为非平面图(Nonplanar Graph)。当且仅当一个图的每个连通分支都是平面图时，这个图是平面图。,平面图的平面表示,2023/11/18,平面图,非平面图,=,非平面图

24、,=,2023/11/18,平面图,=,=,平面图,2023/11/18,11.5.3 欧拉公式,定义11.5.2 在平面图G的一个平面表示中，由边所包围的其内部不包含图的结点和边的区域，称为G的一个面(Surface)，包围该面的诸边所构成的回路称为这个面的边界(Bound)，面r的边界的长度称为该面的次数(Degree)，记为D(r)。区域面积有限的面称为有限面(Finite Surface)，区域面积无限的面称为无限面(Infinite Surface)。平面图有且仅有一个无限面。,2023/11/18,例,有5个面：f1，f2，f3，f4，f5（f5 为外部面）,图不连通，其外部面的次

25、数为5,D(f1)=1,D(f2)=2,D(f3)=3,D(f4)=6,D(f5)=10,2023/11/18,例11.5.2,考察下图所示平面图的面、边界和次数。,解 平面图把平面分成4个面：r0，边界为abdeheca，D(r0)=7r1，边界为abca，D(r1)=3r2，边界为becb，D(r2)=9r3，边界为bdeb，D(r3)=3r1、r2和r3是有限面，r0是无限面。,注意：对于平面图的不同平面表示，虽然面的数目相同，但各面的边界和次数会不同。,2023/11/18,定理11.5.1 平面图中所有面的次数之和等于边数 的二倍。证明 因任何一条边，或者是两个面边界的公共边，或者是

26、在一个面中作为边界被重复计算两次，故平面图所有面的次数之和等于其边数的二倍。1750年，欧拉发现，任何一个凸多面体，若有n个顶点、m条棱和r个面，则有n-m+r=2。这个公式可以推广到平面图上来，称之为欧拉公式。定理11.5.2（欧拉公式）设G=是连通平面图，若它有n个结点、m条边和r个面，则有 n-m+r=2（*）,2023/11/18,证明,对 r 用归纳法。,设 r=k 时，（*）式成立。,当r=1时，G 无基本回路又连通，从而是树，有 n=m+1,于是 n-m+r=（m+1）-m+1=2,当 r=k+1 时，此时 G 至少两个面，从而有圈 C。删去 C 中一条边，记所得之图为 G。并设

27、 G 的点数、边数和面数依次为 n,m 和 r,易知 G 仍连通，但只有 k 个面，由归纳假设有,2023/11/18,同时 n=n，m=m-1，r=r-1,代入（*）式得 n-（m-1）+（r-1）=2,即 n m+r=2,n-m+r=2（*）,推论11.5.2 设G是一个(n,m)简单连通平面图，若每个面的次数至少为k(k3)，则有,2023/11/18,推论11.5.1 设G是一个(n,m)简单连通平面图，若m 1，则有 m3n-6证明 设G有k个面，因为G是简单图，所以G的每个面至少由3条边围成，在式（11.5.2)中取 k=3 即得结论.,证明 设G共有r个面，各面的次数之和为T，由

28、条件可知 kr T=2m（由定理11.5.1）故 r 2m/k代入欧拉公式 n m+r=2 n m+2m/k 2从而有m k(n-2)/(k-2)（11.5.2),2023/11/18,例 证明完全图K5是非平面图。证明 因为K5是简单连通图，n=5，m=10，若 K5 是平面图，则应满足推论11.5.1:m3n-6。代入不等式 得 1035 6=9矛盾，所以 K5 是非平面图。例 证明K3,3是非平面图。,证明 因 K 3,3 没有长小于4的基本回路，所以若 K 3,3 是平面图，则对其相应的平面图中每个面的次数至少为4。由推论11.5.2，K 3,3 应满足 k=4 的不等式（11.5.2

29、)即,而K 3,3中m=9，n=6，代入上式得:926-4=8矛盾，所以 K 3,3 是非平面图。,2023/11/18,说明,1。一个简单连通图，若不满足 m3n-6，则一定是非平面图。,2。一个简单连通图，若每个面的次数至少为k(k3)，若不满足 m k(n-2)/(k-2），则一定是非平面图。,3。对1。和2。满足不等式的简单连通图未必是平面图。,2023/11/18,11.5.4 库拉托夫斯基定理,定理11.5.3(库拉托夫斯基定理)一个图是平面图的充分必要条件是它的任何子图都不可能收缩为K5或K3,3。我们将K5和K3,3称为库拉托夫斯基图。,2023/11/18,方法二：找到子图，

30、收缩边(vi,ui)，用wi代替，i=2,3,4,5，得到图即为K3,3。,2023/11/18,11.6 本章总结（主要知识点汇集）,基本概念：欧拉通路、欧拉回路、欧拉图、桥、哈密顿通路、哈密顿回路、哈密顿图、偶图、匹配、平面图、对偶图、图的着色等；判定方法：欧拉图和偶图都有简单的方法，但哈密顿图和平面图的判定却很困难；在哈密顿图、平面图、偶图的匹配中都分别有仅是必要条件的定理，可用来判断一个图不是哈密尔图、是非平面图、无匹配；,在哈密顿图与匹配中，也有充分条件，可用来判断该图是哈密顿图，有匹配；平面图中欧拉公式；特殊的应用：一笔画问题、计算机鼓轮设计、巡回售货员问题、中国邮路问题等。,2023/11/18,主要知识点汇集,在哈密顿图与匹配中，也有充分条件，可用来判断该图是哈密顿图，有匹配；平面图中欧拉公式；特殊的应用：一笔画问题、计算机鼓轮设计、巡回售货员问题、中国邮路问题等。,Thank You!,