离散数学-图论基础

1、第七章第七章 图论基础图论基础 Graphs2022年年4月月12日星期二日星期二第一节第一节 图的基本概念图的基本概念一个图一个图G定义为一个三元组：定义为一个三元组：V 非空有限集合，非空有限集合，V中的元素称为中的元素称为或或E 有限集合（可以为空），有限集合（可以为空），E中的元素称为中的元素称为 从从E到到V的有序对或无序对的的有序对或无序对的关联映射关联映射(associative mapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)2022年年4月月12日星期二日星期二图的基本概念图的基本概念图图G=中的每条边都与图中的无序对或有序对联系中的每条边都与图中的无序

2、对或有序对联系若边若边e E 与无序对结点与无序对结点va, vb相联系，即相联系，即(e)= va, vb（va, vb V）则称则称e是是（或边、棱）（或边、棱）若边若边e E与有序对结点与有序对结点相联系，即相联系，即(e)=（va, vb V）则称则称e是是（或（或）va是是e的的， vb是是e的的v1v2v3(a)v1v2v3(b)v1v2v3(c)2022年年4月月12日星期二日星期二图的基本概念图的基本概念若若va和和vb与边（弧）与边（弧）e相联结，则称相联结，则称va和和vb是是e的的va和和vb是是，记作：，记作： (adjoin)也称也称e关联关联va和和vb，或称或称v

3、a和和vbe若若va和和vb不与任何边（弧）相联结，则称不与任何边（弧）相联结，则称va和和vb是是，记作：记作：关联同一个结点的两条边（弧），称为关联同一个结点的两条边（弧），称为（弧）（弧）关联同一个结点及其自身的边，称为关联同一个结点及其自身的边，称为，环的方向没有，环的方向没有意义意义v1v2v3(a)v1v2v3(b)v1v2v3(c)2022年年4月月12日星期二日星期二图的基本概念图的基本概念若将图若将图G中的每条边（弧）都看作联结两个结点中的每条边（弧）都看作联结两个结点则则G简记为：简记为：每条边都是弧的图，称为每条边都是弧的图，称为（如图（如图b）每条边都是无向边的图，称为

4、每条边都是无向边的图，称为（如图（如图a） 有些边是弧，有些边是无向边的图，称为有些边是弧，有些边是无向边的图，称为（如图（如图c）v1v2v3(a)v1v2v3(b)v1v2v3(c)2022年年4月月12日星期二日星期二图的基本概念图的基本概念若图若图G中的任意两个结点之间不多于一条无向边（或不多于一条中的任意两个结点之间不多于一条无向边（或不多于一条同向弧），且任何结点无环，则称同向弧），且任何结点无环，则称G为为（如图（如图c）若图若图G中某两个结点之间多于一条无向边（或多于一条同向弧），中某两个结点之间多于一条无向边（或多于一条同向弧），则称则称G为为（如图（如图a, b） 两个结点

5、间的多条边（同向弧）称为两个结点间的多条边（同向弧）称为，平行边（弧）的条数，称为平行边（弧）的条数，称为v1v2v3(a)v1v2v3(b)v1v2v3(c)2022年年4月月12日星期二日星期二图的基本概念图的基本概念在多重图的表示中，可在边（弧）上标注正整数，以表示平行边在多重图的表示中，可在边（弧）上标注正整数，以表示平行边（弧）的重数（弧）的重数把重数作为分配给边（弧）上的数，称为把重数作为分配给边（弧）上的数，称为将权的概念一般化，使其不一定是正整数，则得到加权图的概念：将权的概念一般化，使其不一定是正整数，则得到加权图的概念：给每条边（弧）都赋予权的图，叫做给每条边（弧）都赋予权

6、的图，叫做记作记作G=，v1v2v3(a)v1v2v3(b)v1v2v3(c)11111122112022年年4月月12日星期二日星期二图的基本概念图的基本概念在无向图在无向图G=中，中，V中的每个结点都与其余的所有结点邻中的每个结点都与其余的所有结点邻接，即接，即( va)( vb)(va, vb V va, vb E)，如图，如图(a)则称该图为则称该图为，记作，记作v1v2v3(a)v1v2v3(b)2022年年4月月12日星期二日星期二图的基本概念图的基本概念在有向图在有向图G=中，中，V中的任意两个结点间都有方向相反的中的任意两个结点间都有方向相反的两条弧，即两条弧，即 ( va)(

7、 vb)(va,vb V E E)，如图，如图(a) 则称该图为则称该图为，记作，记作K|V|v1v2v3(a)v1v2v3(b)2022年年4月月12日星期二日星期二图的基本概念图的基本概念在图在图G=中，若有一个结点不与其他任何结点邻接中，若有一个结点不与其他任何结点邻接则该结点称为则该结点称为，如图如图(a)中的中的v4仅有孤立结点的图，称为仅有孤立结点的图，称为，零图的，零图的 E = ，如图如图(b)仅有一个孤立结点的图，称为仅有一个孤立结点的图，称为(trivial graph)，如图如图(c) v1v2v3(a)v1v2v3(b)v1(c)v42022年年4月月12日星期二日星期

8、二问题问题问题问题1：是否存在这种情况：是否存在这种情况：25个人中，由于意见不同，每个人中，由于意见不同，每个人恰好与其他个人恰好与其他5个人意见一致？个人意见一致？问题问题2：是否存在这种情况：是否存在这种情况：2个或以上的人群中，至少有个或以上的人群中，至少有2个人在此人群中的朋友数一样多？个人在此人群中的朋友数一样多？2022年年4月月12日星期二日星期二结点的次数结点的次数二、结点的次数二、结点的次数定义：在有向图定义：在有向图G=中，对任意结点中，对任意结点v V以以v为起始结点的弧的条数，称为为起始结点的弧的条数，称为（引出次数），记为（引出次数），记为以以v为终结点的弧的条数，

9、称为为终结点的弧的条数，称为（引入次数），记为（引入次数），记为v的出度和入度的和，称为的出度和入度的和，称为v的的（次数），记为（次数），记为v1v2v3(a)2022年年4月月12日星期二日星期二结点的次数结点的次数定义：在无向图定义：在无向图G=中，对任意结点中，对任意结点v V结点结点v的的d(v) ，等于联结它的边数，等于联结它的边数记记G的的为：为： (G) = max d(v)| v V记记G的的为：为： (G) = min d(v)| v Vv1v2v3(a)v1v2v3(b)v42022年年4月月12日星期二日星期二结点的次数结点的次数在图在图G中的任意一条边中的任意一条边e

10、 E，都对其联结的结点贡献度数都对其联结的结点贡献度数2定理：定理：通常，将度数为奇数的结点称为通常，将度数为奇数的结点称为 将度数为偶数的结点称为将度数为偶数的结点称为定理：定理：2022年年4月月12日星期二日星期二结点的次数结点的次数问题问题1：是否存在这种情况：是否存在这种情况：25个人中，由于意见不同，每个人中，由于意见不同，每个人恰好与其他个人恰好与其他5个人意见一致？个人意见一致？在建立一个图模型时，一个基本问题是决定这个图是什么在建立一个图模型时，一个基本问题是决定这个图是什么 ？在这个问题里，我们在这个问题里，我们人；人；表示表示2个人意见一致。个人意见一致。也就是说，意见一

11、致的也就是说，意见一致的2个人（结点）间存在一条边。个人（结点）间存在一条边。2022年年4月月12日星期二日星期二结点的次数结点的次数问题问题1：是否存在这种情况：是否存在这种情况：25个人中，由于意见不同，每个人中，由于意见不同，每个人恰好与其他个人恰好与其他5个人意见一致？个人意见一致？这样我们可以知道，如果存在题目所述情况，那么每个结这样我们可以知道，如果存在题目所述情况，那么每个结点都与其他点都与其他5个结点相关联。个结点相关联。也就是说，每个结点的度为也就是说，每个结点的度为5。由定理可知：由定理可知：现在是否能够得出结论了？现在是否能够得出结论了？2022年年4月月12日星期二日

12、星期二结点的次数结点的次数类似问题：类似问题：1.晚会上大家握手言欢，握过奇数次手的人数一定是偶数晚会上大家握手言欢，握过奇数次手的人数一定是偶数2.碳氢化合物中，氢原子个数是偶数碳氢化合物中，氢原子个数是偶数3.是否有这样的多面体，它有奇数个面，每个面有奇数条是否有这样的多面体，它有奇数个面，每个面有奇数条棱？棱？2022年年4月月12日星期二日星期二结点的次数结点的次数问题问题2：是否存在这种情况：两个人或以上的人群中，至少：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？有两个人在此人群中的朋友数一样多？以人为结点，仅当二人为朋友时，在此二人之间连一边，以人

13、为结点，仅当二人为朋友时，在此二人之间连一边，得一得一“友谊图友谊图”G(V,E)， 设设V=v1, v2, , vn，不妨，不妨设各结点的次数为设各结点的次数为d(v1)d(v2) d(vn)n-1。假设命题不成立，则所有人的朋友数都不一样多，则假设命题不成立，则所有人的朋友数都不一样多，则 0 d(v1)d(v2) d(vn)n-1。2022年年4月月12日星期二日星期二结点的次数结点的次数问题问题2：是否存在这种情况：两个人或以上的人群中，至少：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？有两个人在此人群中的朋友数一样多？若若 0 d(v1)d(v2)

14、d(vn) n-1，则有：，则有：由于由于d(v1)0 ，则有，则有d(v2)1，d(v3)2，d(vn)n-1；又因为；又因为d(vn) n-1，所以：，所以： d(vn)=n-1因为因为d(vn)=n-1，则每个结点皆与，则每个结点皆与vn相邻，则相邻，则d(v1)1。于是有：于是有：d(v2)2，d(v3)3，d(vn)n，矛盾。，矛盾。故假设不成立，即故假设不成立，即d(v1)d(v2) d(vn)中至少有一中至少有一个等号成立，命题成立。个等号成立，命题成立。2022年年4月月12日星期二日星期二结点的次数结点的次数定义：在无向图定义：在无向图G=中，若每个结点的度数都是中，若每个结

15、点的度数都是k，即即( v)( v V d(v) = k)，则称，则称G为为v1v2v6v33度正则图度正则图v4v5v7v8v9v103度正则图度正则图v1v5v6v2v3v42022年年4月月12日星期二日星期二子图子图三、子图三、子图定义：给定无向图定义：给定无向图G1=， G2=若若V2 V1，E2 E1，则称，则称G2是是G1的的，记作记作若若V2 V1，E2 E1，且，且E2 E1，则称，则称G2是是G1的的，记作记作若若V2 = V1，E2 E1，则称，则称G2是是G1的的，记作，记作2022年年4月月12日星期二日星期二子图子图例如：例如：v2v1(a)v3v4v5(a)的真子

16、图的真子图v2v3v4v5(a)的生成子图的生成子图v2v3v4v5v12022年年4月月12日星期二日星期二子图子图定义：对于图定义：对于图G=，G1=G，G2= G1和和 G2都是都是G的生成子图，称为的生成子图，称为定义：设定义：设G2=是是G1=的子图的子图对任意结点对任意结点u, v V2，若有若有u, v E1，则有则有u, v E2，则则G2由由V2唯一地确定，则称唯一地确定，则称记作记作，或或G2=若若G2中无孤立结点，且由中无孤立结点，且由E2唯一地确定，则称唯一地确定，则称，记作，记作，或或G2=2022年年4月月12日星期二日星期二子图子图例如：例如：v2v1G=v3v4

17、v5G=V或或E的诱导子图的诱导子图v2v3v4v52022年年4月月12日星期二日星期二补图补图定义：定义：设设G1=和和G2=是是G=的子图，的子图，若若 ，且且，即，即G2= 则称则称G2是是2022年年4月月12日星期二日星期二补图补图图图G1和和G2互为互为相对于相对于G补图补图G1v2v1v3v4v5G2v2v3v4v5Gv2v1v3v4v52022年年4月月12日星期二日星期二补图补图定义：定义：给定图给定图G1= ，若存在图若存在图G2=且且 ，及图，及图则称则称，记作，记作G2 = G12022年年4月月12日星期二日星期二补图补图 G2 = G1v2v1G1v3v4v5v2

18、v1K5v3v4v5G2v2v3v4v5v12022年年4月月12日星期二日星期二图的同构图的同构四、图的同构四、图的同构定义：定义：给定图给定图G1=， G2=若存在双射函数若存在双射函数f : V1 V2 ，使得对于任意使得对于任意u, v V1有有 （或或 E1 E2）则称则称，记作，记作 2022年年4月月12日星期二日星期二图的同构图的同构例例7.1.1 证明下面两个图证明下面两个图G1=， G2=同构同构证明：证明：V1=v1, v2, v3, v4, V2=a, b, c, d构造双射函数构造双射函数f : V1 V2 ，f(v1)=a ，f(v2)=bf(v3)=c ，f(v4

19、)=d可知，边可知，边v1, v2, v2, v3, v3, v4, v4, v1被分别映射成被分别映射成a, b, b, c, c, d, d, a，故，故G1 G2v2v1G1v3v4badcG22022年年4月月12日星期二日星期二图的同构图的同构例例7.1.2 证明下面两个有向图是同构的。证明下面两个有向图是同构的。G1eabcd证明：如图所示，证明：如图所示，G1=，G2=，结点编号如图所示。，结点编号如图所示。构造函数构造函数f: V1V2 ，使得使得f(a)=1, f(b)=3, f(c)=4, f(d)=5, f(e)=2 则则, , , , , , , 被分别映射成被分别映射

20、成, , , , , ,故故f是双射函数，所以是双射函数，所以G1与与G2同构同构G1312452022年年4月月12日星期二日星期二图的同构图的同构可以给出可以给出：结点数相等结点数相等边数相等边数相等度数相等的结点数相等度数相等的结点数相等要注意的是，这不是充分条件要注意的是，这不是充分条件2022年年4月月12日星期二日星期二图的同构图的同构例例7.1.3 证明下面两个无向图是不同构的证明下面两个无向图是不同构的G1v1v2v3v4v5v6v7v8G2abcdefgh v1是是3度结点，故度结点，故f(v1)只能是只能是c或或d或或g或或h。 若若f(v1)=c，由于，由于v2、v4和和

21、v5与与v1邻接，因邻接，因此此f(v2)、f(v4)和和f(v5)应当分别为与应当分别为与c邻接的邻接的b、d和和g。 但是，但是，v2、v4和和v5中，只有一个中，只有一个3度结点，度结点，而而b、d、g中却有中却有2个个3度结点，故度结点，故f(v1)c。 同理可说明，同理可说明， f(v1)也不可能是也不可能是d、g和和h。 因此这样的因此这样的f是不存在的。是不存在的。 因此因此G1和和G2是不同构的。是不同构的。2022年年4月月12日星期二日星期二第二节第二节 路路(链链)与回路与回路(圈圈)一、路一、路(链链)与回路与回路(圈圈)定义：给定图定义：给定图G=，令令v0,v1,v

22、m V，e1,e2,em E称交替序列称交替序列为连接为连接v0到到vm的的称称v0和和vm为链（路）的为链（路）的和和链的链的为边（弧）的数目为边（弧）的数目m若若v0=vm，该链（路）称为，该链（路）称为2022年年4月月12日星期二日星期二链和圈链和圈在链中：在链中：若任意若任意ei只出现一次，则称该链（路）为只出现一次，则称该链（路）为（路）（路）若任意若任意vi只出现一次，则称该链（路）为只出现一次，则称该链（路）为（路）（路）在圈中：在圈中：若任意若任意ei只出现一次，则称该圈只出现一次，则称该圈（回路）为回路）为（回路）回路）若任意若任意vi只出现一次，则称该圈只出现一次，则称该

23、圈（回路）为回路）为（回路）回路）2022年年4月月12日星期二日星期二链和圈链和圈例例7.2.1 下图中：下图中：v3v1v4v5v2e1e2e3e4e5e6e7e8P1=(v1 e1 v2 e7 v5)也可以表示为：也可以表示为：P1=(e1 e7)是一个基本链，也是一个简单链是一个基本链，也是一个简单链P2=(v2 e2 v3 e3 v3 e4 v1 e1 v2)也可以表示为：也可以表示为：P2=(e2 e3 e4 e1 )是一个简单圈，但不是基本圈是一个简单圈，但不是基本圈P3=(v4 e6 v2 e7 v5 e8 v4 e6 v2 e2 v3) 是一个链是一个链P4=(v2 e7 v

24、5 e8 v4 e6 v2) 是一个基本圈，也是一个简单圈是一个基本圈，也是一个简单圈2022年年4月月12日星期二日星期二链和圈链和圈上例中：上例中： (v2e2v3e3v3e4v1e1v2)也可表示为也可表示为 (e2e3e4e1)(v4e6v2e7v5e8v4e6v2e2v3)也可表示为也可表示为 (e6e7e8e6e2)v3v1v4v5v2e1e2e4e5e6e3e8图中：图中：(v2e2v3e4v1e1v2e3v5e8v4)可表示为可表示为 (e2e4e1e3e8)也可表示为也可表示为 (v2v3v1v2v5v4)2022年年4月月12日星期二日星期二链和圈链和圈定理：定理：证明：证

25、明：1) 若从若从vi到到vj给定的链本身就是基本链，定理成立给定的链本身就是基本链，定理成立2) 若从若从vi到到vj给定的链不是基本链，则给定的链不是基本链，则至少含有一个结点至少含有一个结点vk，它，它在该链中至少出现两次以上在该链中至少出现两次以上。 也就是说，经过也就是说，经过vk有一个圈有一个圈 ，于是可以从原有链中去除，于是可以从原有链中去除 中中所有出现的边（弧）。对于原链中所含的所有圈都做此处理，所有出现的边（弧）。对于原链中所含的所有圈都做此处理，最终将得到一条基本链（路）最终将得到一条基本链（路）2022年年4月月12日星期二日星期二链和圈链和圈问题：问题：例例7.2.2

26、 若若u和和v是一个圈上的两个结点，是一个圈上的两个结点，u和和v一定是某个基本一定是某个基本圈上的结点吗？圈上的结点吗？(习题习题7-16)答：不一定答：不一定vaudcb本图中，本图中，u和和v在一个圈上，在一个圈上，但是却不在一个基本圈上但是却不在一个基本圈上2022年年4月月12日星期二日星期二链和圈链和圈定理：在一个具有定理：在一个具有n个结点的图中，个结点的图中，证明：证明：1) 根据基本链的定义可知，出现在基本链中的结点都是根据基本链的定义可知，出现在基本链中的结点都是不同的。因此在长度为不同的。因此在长度为m的基本链中，不同的结点数为的基本链中，不同的结点数为m+1又因为图中仅

27、有又因为图中仅有n个结点，故个结点，故 m+1 n，即，即 m n-12)根据基本圈的定义可知，长度为根据基本圈的定义可知，长度为k的基本圈中，不同的结点数的基本圈中，不同的结点数为为k，图中共有图中共有n个结点，所以个结点，所以 k n2022年年4月月12日星期二日星期二可达可达二、连通图二、连通图定义：定义：在一个图中，若从在一个图中，若从vi到到vj存在任何一条链存在任何一条链则称则称，简称，简称规定：规定：2022年年4月月12日星期二日星期二连通无向图连通无向图（一）连通无向图（一）连通无向图对于无向图对于无向图G=而言，可证明而言，可证明“可达性可达性”是一个是一个_关系关系。它

28、对它对V给出一个划分，每个块中的元素形成一个诱导子图。给出一个划分，每个块中的元素形成一个诱导子图。两个结点间是可达的，当且仅当它们属于同一个子图两个结点间是可达的，当且仅当它们属于同一个子图称这样的子图为称这样的子图为G的的，G的连通分图的个数记为的连通分图的个数记为 (G)若若G中只有一个连通分图，则称中只有一个连通分图，则称G是是(即任意两结点可达即任意两结点可达)否则称否则称G为为，或，或等价等价2022年年4月月12日星期二日星期二连通无向图连通无向图定义：在无向图定义：在无向图G=中中若任意两个结点可达，则称若任意两个结点可达，则称G是是 ，称称G为为；否则称否则称G是非连通的，称

29、是非连通的，称G为为或或。若若G的子图的子图G是连通的，且不存在包含是连通的，且不存在包含G的更大的的更大的G的的子图子图G是连通的，则称是连通的，则称G是是G的的，简称分图。，简称分图。G中连通分图的个数记为中连通分图的个数记为。2022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.3v3v1v4v5v2v3v1v4v5v2G1G2G1是连通图，是连通图， (G1)=1G2是非连通图，是非连通图， (G2)=22022年年4月月12日星期二日星期二连通无向图连通无向图定义：定义：，是指是指V-SE-与与S中结点相连结的边中结点相连结的边而得到的子图，记做而得到的子图，记做G-

30、SG-v3v3v1v4v5v2Gv3v1v4v5v2v3v1v4v5v22022年年4月月12日星期二日星期二连通无向图连通无向图定义：定义：，是指是指V-SE-与与S中结点相连结的边中结点相连结的边而得到的子图，记做而得到的子图，记做G-SG-v3v1v4v5v2G2022年年4月月12日星期二日星期二连通无向图连通无向图定义：定义：，是指是指V不变不变E-T而得到的子图，记做而得到的子图，记做G-TG-e1, e3 , e4v3v1v4v5v2Ge1e2e3e4e5e6e7v3v1v4v5v22022年年4月月12日星期二日星期二连通无向图连通无向图定义：定义：，是指是指V不变不变E-T而

31、得到的子图，记做而得到的子图，记做G-TG-e1, e3 , e4v3v1v4v5v2Ge2e5e6e72022年年4月月12日星期二日星期二连通无向图连通无向图定义：给定连通无向图定义：给定连通无向图G=，S V若若 (G-S) (G)=1且对任意且对任意 T S， (G-T) = (G)则称则称S是是G的一个的一个若若S中仅含有一个元素中仅含有一个元素v，则称则称v是是G的的2022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.4G如下图所示，如下图所示，S=v1, v3v2v1v5v6v4Gv3v2v1v5v6v4G-Sv3v2v5v6v4G-S (G)=1， (G-S)

32、 =2 (G-S) (G) 2022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.4G如下图所示，如下图所示，S=v1, v3v2v1v5v6v4Gv3 (G)=1， (G-S) =2 (G-S) (G) (G-v1)=1v2v5v6v4G-v1v32022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.4G如下图所示，如下图所示，S=v1, v3v2v1v5v6v4Gv3 (G)=1， (G-S) =2 (G-S) (G) (G-v1)=1v2v1v5v6v4G-v3 (G-v3)=12022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.4G如下

33、图所示，如下图所示，S=v1, v3v2v1v5v6v4Gv3v2v5v6v4G-S (G)=1， (G-S) =2 (G-S) (G) (G-v1)=1 (G-v3)=12022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.5G如下图所示，如下图所示，S=v2v1v4v5v3Gv2 (G)=1， (G-S) =2 (G-S) (G) v1v4v5v3G-S2022年年4月月12日星期二日星期二连通无向图连通无向图定义：给定连通无向图定义：给定连通无向图G=，T E若若 (G-T) (G) =1且对任意且对任意 F T， (G-F) = (G)则称则称T是是G的一个的一个若若T

34、中仅含有一个元素中仅含有一个元素e，则称则称e是是G的的，或桥，或桥2022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.6G如下图所示，如下图所示，T=e1, e2 (G)=1， (G-T) =2 (G-T) (G) v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e32022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.6G如下图所示，如下图所示，T=e1, e2 (G)=1， (G-T) =2 (G-T) (G) v1v3v4Gv2e1e4e2e3v1v3v4G-e1v2e4e2e3 (G-e1)=12022年年4月月12日星期二日星期二连通无

35、向图连通无向图例例7.2.6G如下图所示，如下图所示，T=e1, e2 (G)=1， (G-T) =2 (G-T) (G) v1v3v4Gv2e1e4e2e3 (G-e1)=1 (G-e2)=1v1v3v4G-e2v2e1e4e32022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.6G如下图所示，如下图所示，T=e1, e2 (G)=1， (G-T) =2 (G-T) (G) v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e3 (G-e1)=1 (G-e2)=12022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.7G如下图所示，如下图所示，T=

36、e1 (G)=1， (G-T) =2 (G-T) (G) v1v3v4Gv2e1e2e3v1v3v4G-Tv2e2e32022年年4月月12日星期二日星期二连通无向图连通无向图定义：对连通的非平凡图定义：对连通的非平凡图G=，称称 (G) = min |S| | S是是G的分离结点集的分离结点集为为G的的它表明产生分离图需要删去结点的最少数目它表明产生分离图需要删去结点的最少数目对分离图对分离图G而言，而言， (G)=0对存在割点的连通图对存在割点的连通图G而言，而言， (G)=1S V2022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.8求求G1和和G2的结点连通度的结点连

37、通度v2v1v5v6v4G1v3 (G1)=2 (G2)=1v1v4v5v3G2v22022年年4月月12日星期二日星期二连通无向图连通无向图定义：对连通的非平凡图定义：对连通的非平凡图G=，称称 (G) = min |T| | T是是G的分离边集的分离边集为为G的的它表明产生分离图需要删去边的最少数目它表明产生分离图需要删去边的最少数目对分离图对分离图G而言，而言， (G)=0对存在割边的连通图对存在割边的连通图G而言，而言， (G)=1对无向完全图对无向完全图Kn， (Kn) = ?T En-12022年年4月月12日星期二日星期二连通无向图连通无向图例例7.2.9求求G1和和G2的边连通

38、度的边连通度 (G1)=2 (G2)=1v1v3v4G1v2e1e4e2e3v1v3v4G2v2e1e2e32022年年4月月12日星期二日星期二连通无向图连通无向图定理：对于任何一个无向图定理：对于任何一个无向图G，有有 证明：证明：1) 若若G是分离图，则是分离图，则 (G) = (G) = 0， 而而 (G) 02) 若若G是连通图，先证明是连通图，先证明若若G是平凡图，则是平凡图，则 (G) = 0 = (G)若若G不是平凡图，则当删去所有联结一个具有最小度的结点的边不是平凡图，则当删去所有联结一个具有最小度的结点的边（除了环）后，便产生了一个分离图，因此（除了环）后，便产生了一个分离

39、图，因此 (G) (G)再证明再证明 若若 (G)1，则则G存在一个割边，存在一个割边， 显然显然 (G) = (G) = 1v3v1v4v5v2v1v1v3v4Gv2e1e2e3v1v3v4G e1v2e2e3v1v3v4Gv2e1e2e3v1v3v4G e1v2e2e3v3v4G v1v2e32022年年4月月12日星期二日星期二连通无向图连通无向图若若 (G) 2，则删去某则删去某 (G)条边后，条边后，G就成为分离图就成为分离图若只删除若只删除 (G)-1条边，则仍得到连通图且存在一割边条边，则仍得到连通图且存在一割边e=u, v对于对于 (G)-1条边中的每一条边，选取一个不同于条边

40、中的每一条边，选取一个不同于u和和v的结点，的结点，把这些结点删去，将必须至少删去把这些结点删去，将必须至少删去 (G)-1条边条边若这样会产生分离图，则若这样会产生分离图，则若这样产生的仍是连通图且若这样产生的仍是连通图且e是割边，再删除结点是割边，再删除结点u或或v必将产生必将产生分离图，因此分离图，因此v1v3v4Gv2e4e3v1v3v4G v2e2e3v1v4G v3综上所述，有综上所述，有 2022年年4月月12日星期二日星期二连通无向图连通无向图定理：一个连通无向图定理：一个连通无向图G中的结点中的结点v是割点，充要条件是是割点，充要条件是存在两个结点存在两个结点u和和w，使得联

41、结使得联结u和和w的每条链都经过的每条链都经过v证明：证明：1) 充分性：若充分性：若G中联结中联结u和和w的每条链都经过的每条链都经过v，删去删去v，则在子图则在子图G-v中，中， u和和w必定不可达，故必定不可达，故v是是G的割点的割点2) 必要性：若必要性：若v是是G的割点，删去的割点，删去v，则子图则子图G-v中至少有两个中至少有两个连通分图连通分图G1=和和G2 = ，任取两个结点任取两个结点u V1，w V2 ，u和和w不可达。故不可达。故G中联结中联结u和和w的每条链的每条链必经过必经过v2022年年4月月12日星期二日星期二连通无向图连通无向图同理可以证明：同理可以证明：定理：

42、一个连通无向图定理：一个连通无向图G中的边中的边e是割边，充要条件是是割边，充要条件是存在两个结点存在两个结点u和和w，使得联结使得联结u和和w的每条链都经过的每条链都经过e定理：一个连通无向图定理：一个连通无向图G中的边中的边e是割边，充要条件是是割边，充要条件是e不包含在不包含在G的任何基本圈中的任何基本圈中证明：教材证明：教材P172 （定理（定理7.8)2022年年4月月12日星期二日星期二乌拉姆猜想（乌拉姆猜想（1929）左右两张相片，捂住左边相片的一部分，也捂住右边相片左右两张相片，捂住左边相片的一部分，也捂住右边相片的相应部分，例如都捂住左眼，能看到的相片的大部分形的相应部分，例

43、如都捂住左眼，能看到的相片的大部分形象一致；再分别捂住左右相片的另一个对应部分，例如右象一致；再分别捂住左右相片的另一个对应部分，例如右耳，结果能看到的相片的大部分仍然一致。如此轮番地观耳，结果能看到的相片的大部分仍然一致。如此轮番地观察各次对应的暴露部分，都会看到相同的形象，那么谁都察各次对应的暴露部分，都会看到相同的形象，那么谁都会相信这两张照片是同一个人或孪生兄弟的留影。会相信这两张照片是同一个人或孪生兄弟的留影。数学描述：有图数学描述：有图G1=V1, E1和和G2=V2, E2 ，V1=v1, v2, , vn，V2=u1, u2, , un（n3）。）。如果如果G1-vi G2-u

44、i，i=1,2,n，则，则G1 G22022年年4月月12日星期二日星期二连通有向图连通有向图（二）连通有向图（二）连通有向图对于有向图对于有向图G=而言，而言，它仅仅是它仅仅是定义：对于给定的有向图定义：对于给定的有向图G，要略去要略去G中每条边的方向，中每条边的方向， 便得到一个无向图便得到一个无向图G，称称G是是G的的2022年年4月月12日星期二日星期二连通有向图连通有向图定义：在简单有向图定义：在简单有向图G中，中，若任何两个结点间都是可达的，则称若任何两个结点间都是可达的，则称G是是的的若任何两个结点间，至少是从一个结点可达另一个结点，若任何两个结点间，至少是从一个结点可达另一个结

45、点，则称则称G是是的的若若G的基础图是连通的，则称的基础图是连通的，则称G是是的的2022年年4月月12日星期二日星期二连通有向图连通有向图例例7.2.10 判断判断G1、G2和和G3是强连通？单向连通？弱连通？是强连通？单向连通？弱连通？G1是强连通的是强连通的v1v3v4G1v2v1v3v4G2v2v1v3v4G3v2G2是单向连通的是单向连通的G3是弱连通的是弱连通的2022年年4月月12日星期二日星期二连通有向图连通有向图由定义可知：由定义可知：若若G是强连通的，则它必定是单向连通的是强连通的，则它必定是单向连通的反之未必真反之未必真若若G是单向连通的，则它必是弱连通的是单向连通的，则

46、它必是弱连通的反之未必真反之未必真2022年年4月月12日星期二日星期二连通有向图连通有向图定理：有向图定理：有向图G是强连通的，当且仅当是强连通的，当且仅当证明：证明：1) 充分性：若充分性：若G中存在一条回路，它至少通过每个结点一中存在一条回路，它至少通过每个结点一回，则回，则G中任何两个结点都是互相可达的，所以中任何两个结点都是互相可达的，所以G是强连通的。是强连通的。2) 必要性：若必要性：若G是强连通的，则是强连通的，则G中任何两个结点都是互相可达中任何两个结点都是互相可达的，因此可以做出一条回路经过的，因此可以做出一条回路经过G中所有结点，中所有结点，否则，必有某结点否则，必有某结

47、点v不在该回路上不在该回路上，v与回路上的各结点不可能都与回路上的各结点不可能都互相可达。与互相可达。与G是强连通的矛盾是强连通的矛盾2022年年4月月12日星期二日星期二连通有向图连通有向图定义：在简单有向图定义：在简单有向图G中中具有强连通性质的极大子图，称为具有强连通性质的极大子图，称为具有单向连通性质的极大子图，称为具有单向连通性质的极大子图，称为具有弱连通性质的极大子图，称为具有弱连通性质的极大子图，称为2022年年4月月12日星期二日星期二连通有向图连通有向图例例7.2.11求求G的强分图、单向分图和弱分图的强分图、单向分图和弱分图v3v2v1Gv4v5v6v3v2v1v4v5v6

48、G的强分图有：的强分图有：定理：定理：简单有向图简单有向图G中的任意一个结点，恰位于一个强分图中中的任意一个结点，恰位于一个强分图中2022年年4月月12日星期二日星期二连通有向图连通有向图定理：定理：简单有向图简单有向图G中的任意一个结点，恰位于一个强分图中中的任意一个结点，恰位于一个强分图中证明：由强分图的定义可知，证明：由强分图的定义可知，G中每个结点位于一个强分图中中每个结点位于一个强分图中假设假设G中存在结点中存在结点v位于两个强分图位于两个强分图G1和和G2中中则由强分图的定义可知，则由强分图的定义可知， G1中的每个结点与中的每个结点与v互相可达，互相可达， G2中中的每个结点也

49、与的每个结点也与v互相可达互相可达故故G1中的每个结点与中的每个结点与G2中的每个结点通过中的每个结点通过v，能够互相可达，这能够互相可达，这与与G1和和G2是两个强分图矛盾是两个强分图矛盾因此因此G中每个结点只能位于一个强分图中中每个结点只能位于一个强分图中2022年年4月月12日星期二日星期二连通有向图连通有向图例例7.2.11求求G的强分图、单向分图和弱分图的强分图、单向分图和弱分图G的单向分图有：的单向分图有：v3v2v1Gv4v5v6v3v2v1v4v5v5v6定理：定理：简单有向图简单有向图G中的每个结点和每条弧中的每个结点和每条弧, 至少位于一个单向分图中至少位于一个单向分图中2

50、022年年4月月12日星期二日星期二连通有向图连通有向图例例7.2.11求求G的强分图、单向分图和弱分图的强分图、单向分图和弱分图G的弱分图有：的弱分图有：v3v2v1Gv4v5v6v3v2v1v4v5v6定理：定理：简单有向图简单有向图G中的每个结点和每条弧中的每个结点和每条弧 恰位于一个弱分图中恰位于一个弱分图中2022年年4月月12日星期二日星期二结点间的距离结点间的距离三、结点间的距离三、结点间的距离定义：在图定义：在图G中，若结点中，若结点u可达结点可达结点v，它们之间可能存在不止它们之间可能存在不止一条链（路）。一条链（路）。在所有链中，在所有链中，称为结点称为结点u和和v之间的之

51、间的（或短程线、测地线）。记做：（或短程线、测地线）。记做：2022年年4月月12日星期二日星期二结点间的距离结点间的距离距离满足下面性质：距离满足下面性质：d 0d=0d+d d若若u不可达不可达v，则则 d = + 即使即使u和和v互相可达，互相可达，d未必等于未必等于d 2022年年4月月12日星期二日星期二有向图在计算机中的应用有向图在计算机中的应用四、有向图在计算机中的应用四、有向图在计算机中的应用这里给出一个简单有向图在计算机中的应用这里给出一个简单有向图在计算机中的应用 利用资源分配图来纠正和发现死锁利用资源分配图来纠正和发现死锁2022年年4月月12日星期二日星期二有向图在计算

52、机中的应用有向图在计算机中的应用在多道程序的计算机系统中，同一时间内有多个程序需要同时在多道程序的计算机系统中，同一时间内有多个程序需要同时执行。执行。每个程序都共享计算机资源：如每个程序都共享计算机资源：如CPU、内存、外存、输入设备、内存、外存、输入设备、编译系统等，操作系统将对这些资源分配给各个程序。编译系统等，操作系统将对这些资源分配给各个程序。当一个程序需要使用某种资源的时候，要向操作系统发出请求，当一个程序需要使用某种资源的时候，要向操作系统发出请求，操作系统必须保证这个请求得到满足，才能运行该程序操作系统必须保证这个请求得到满足，才能运行该程序2022年年4月月12日星期二日星期

53、二有向图在计算机中的应用有向图在计算机中的应用对资源的请求可能发生冲突，发生对资源的请求可能发生冲突，发生。例如：。例如：程序程序P1占有资源占有资源r1，请求资源请求资源r2程序程序P2占有资源占有资源r2，请求资源请求资源r1有冲突的请求必须要解决，可以利用有向图来模拟对资源的请有冲突的请求必须要解决，可以利用有向图来模拟对资源的请求，从而帮助发现和纠正求，从而帮助发现和纠正“死锁死锁”状态状态2022年年4月月12日星期二日星期二有向图在计算机中的应用有向图在计算机中的应用令令Pt=P1, P2, P3, P4是是t时刻运行的程序集合时刻运行的程序集合 Rt=r1, r2, r3, r4

54、是是t时刻所需要的的资源集合时刻所需要的的资源集合P1占有资源占有资源r4，请求资源请求资源r1P2占有资源占有资源r1，请求资源请求资源r2和和r3P3占有资源占有资源r2，请求资源请求资源r3P4占有资源占有资源r3，请求资源请求资源r1和和r4可得到资源分配图可得到资源分配图G如图所示如图所示r4r3r2r1P1P3P2P2P4P42022年年4月月12日星期二日星期二有向图在计算机中的应用有向图在计算机中的应用解决办法：解决办法： 使使G中的每个强分图中中的每个强分图中都是单个结点都是单个结点r4r3r2r1P1P3P2P2P4P4r4r3r2r1P1P3P2P22022年年4月月12

55、日星期二日星期二3x+1猜想（卡拉兹）猜想（卡拉兹）20世纪世纪30年代，汉堡大学的卡拉兹（年代，汉堡大学的卡拉兹（Callatz）提出一个）提出一个猜想：猜想：x0是一个自然数，是一个自然数，若若x0是偶数，则取是偶数，则取x1= x0/2，若若x0是奇数，则取是奇数，则取x1=(3x0+1)/2。将将x1应用上述规则得到应用上述规则得到x2， 如此进行下去，则到达某一步，如此进行下去，则到达某一步，xk=1。东京大学的东京大学的N.永内达（永内达（Nabuo Yoneda）用计算机检验了）用计算机检验了所有不超过所有不超过2401.21012的自然数，结果都符合卡拉兹的自然数，结果都符合卡

56、拉兹的猜想。的猜想。2022年年4月月12日星期二日星期二3x+1猜想（卡拉兹）猜想（卡拉兹）如果把一批自然数放在最高层，如果把一批自然数放在最高层，用用3x+1问题的规则算出第二问题的规则算出第二层的值，继而算出第三层的层的值，继而算出第三层的值值。图中的结点是自然数，。图中的结点是自然数，当数当数1算出数算出数2时，则在图上画时，则在图上画上有向边上有向边，得到的，得到的有向图称为卡拉兹有向图，如有向图称为卡拉兹有向图，如图所示。图所示。3x+1猜想中，卡拉猜想中，卡拉兹图的最底层结点是兹图的最底层结点是1。2022年年4月月12日星期二日星期二第三节第三节 图的矩阵表示图的矩阵表示一、图

57、的矩阵表示一、图的矩阵表示定义：给定简单图定义：给定简单图G=，V=v1,v2,vnV中的结点按照下标由小到大编序（编序与矩阵形式有密切关中的结点按照下标由小到大编序（编序与矩阵形式有密切关系），则系），则n阶方阵阶方阵AG=(aij)称为图称为图G的的。其中：。其中：aij=i, j = 1, 2, , n1vi adj vj0vi nadj vj2022年年4月月12日星期二日星期二邻接矩阵邻接矩阵例例7.3.1 图图G=如图所示如图所示v4v5v3v2v10 1 1 1 11 0 1 0 01 1 0 1 01 0 1 0 11 0 0 1 0AG= G的邻接矩阵为：的邻接矩阵为：0 1

58、 0 0 11 0 1 0 10 1 0 1 10 0 1 0 11 1 1 1 0AG= G的邻接矩阵变为：的邻接矩阵变为：v3v4v2v1v5若若G中结点编序如下图所示中结点编序如下图所示2022年年4月月12日星期二日星期二邻接矩阵邻接矩阵例例7.3.2 图图G=如图所示如图所示0 1 0 1 0 0 1 01 0 0 1 0 1 0 0AG= G的邻接矩阵为：的邻接矩阵为：v1v3v4v2若若G中结点编序如下图所示中结点编序如下图所示v4v3v1v20 1 0 0 0 0 1 01 0 0 1 1 1 0 0AG= G的邻接矩阵变为：的邻接矩阵变为：2022年年4月月12日星期二日星期

59、二邻接矩阵邻接矩阵对于仅仅结点编序不同的图，是同构的对于仅仅结点编序不同的图，是同构的它们的邻接矩阵也是相似的它们的邻接矩阵也是相似的G1 G2 存在置换矩阵存在置换矩阵P，使得使得AG2 = P-1 AG1 P对于由结点编序不同引起的邻接矩阵的不同将被忽略对于由结点编序不同引起的邻接矩阵的不同将被忽略任取图的任意一个邻接矩阵作为该图的矩阵表示任取图的任意一个邻接矩阵作为该图的矩阵表示2022年年4月月12日星期二日星期二邻接矩阵邻接矩阵图图G的邻接矩阵的邻接矩阵AG可以展示图可以展示图G的一些性质：的一些性质：若邻接矩阵若邻接矩阵AG的元素全是零，则的元素全是零，则G是是若邻接矩阵若邻接矩阵

60、AG的元素主对角线上全是的元素主对角线上全是0，其他元素全是，其他元素全是1，则则G是是无向图无向图G的邻接矩阵的邻接矩阵AG是是在简单有向图的邻接矩阵中，第在简单有向图的邻接矩阵中，第i行元素是由结点行元素是由结点vi出发的弧所确出发的弧所确定的，故定的，故，即，即d+(vi)= aik第第j列元素是由到达结点列元素是由到达结点vj的弧所确定的，故的弧所确定的，故，即，即d-(vj)= akjnk=1nk=12022年年4月月12日星期二日星期二邻接矩阵邻接矩阵定理：设定理：设A为简单图为简单图G的邻接矩阵，则的邻接矩阵，则An中的中的i行行j列的元素列的元素aijn等于等于G中联结中联结v