离散数学-图论基础课件.ppt

1、第七章第七章 图论基础图论基础 Graphs2022年年12月月28日星期三日星期三第一节第一节 图的基本概念图的基本概念一个图一个图G定义为一个三元组：定义为一个三元组：V 非空有限集合，非空有限集合，V中的元素称为中的元素称为或或E 有限集合（可以为空），有限集合（可以为空），E中的元素称为中的元素称为 从从E到到V的有序对或无序对的的有序对或无序对的关联映射关联映射(associative mapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)2022年年12月月28日星期三日星期三图的基本概念图的基本概念图图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年年12月月28日星期三日星期三图的基本概念图的基本概念若若va和和vb与边（弧）与边（弧）e相联结，则称相联结，则称va和和vb是是e的的va和和vb是是，记作：，记作：(adjoin)也称也称e关联关联va和和vb，或称或称va和和v

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

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

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

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

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

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

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

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

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

12、问题：类似问题：1.晚会上大家握手言欢，握过奇数次手的人数一定是偶数晚会上大家握手言欢，握过奇数次手的人数一定是偶数2.碳氢化合物中，氢原子个数是偶数碳氢化合物中，氢原子个数是偶数3.是否有这样的多面体，它有奇数个面，每个面有奇数条是否有这样的多面体，它有奇数个面，每个面有奇数条棱？棱？2022年年12月月28日星期三日星期三结点的次数结点的次数问题问题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年年12月月28日星期三日星期三结点的次数结点的次数问题问题2：是否存在这种情况：两个人或以上的人群中，至少：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？有两个人在此人群中的朋友数一样多？若若 0 d(v1)d(v2)d(vn)n-1，则有：，则有：由于由于d

14、(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年年12月月28日星期三日星期三结点的次数结点的次数定义：在无向图定义：在无向图G=中，若每个结点的度数都是中，若每个结点的度数都是k，即即(v)(v V d(v)=k)

15、，则称，则称G为为v1v2v6v33度正则图度正则图v4v5v7v8v9v103度正则图度正则图v1v5v6v2v3v42022年年12月月28日星期三日星期三子图子图三、子图三、子图定义：给定无向图定义：给定无向图G1=，G2=若若V2 V1，E2 E1，则称，则称G2是是G1的的，记作记作若若V2 V1，E2 E1，且，且E2 E1，则称，则称G2是是G1的的，记作记作若若V2=V1，E2 E1，则称，则称G2是是G1的的，记作，记作2022年年12月月28日星期三日星期三子图子图例如：例如：v2v1(a)v3v4v5(a)的真子图的真子图v2v3v4v5(a)的生成子图的生成子图v2v3

16、v4v5v12022年年12月月28日星期三日星期三子图子图定义：对于图定义：对于图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年年12月月28日星期三日星期三子图子图例如：例如：v2v1G=v3v4v5G=V或或E的诱导子图的诱导子图v2v3v4v52022年年

17、12月月28日星期三日星期三补图补图定义：定义：设设G1=和和G2=是是G=的子图，的子图，若若，且且，即，即G2=则称则称G2是是2022年年12月月28日星期三日星期三补图补图图图G1和和G2互为互为相对于相对于G补图补图G1v2v1v3v4v5G2v2v3v4v5Gv2v1v3v4v52022年年12月月28日星期三日星期三补图补图定义：定义：给定图给定图G1=，若存在图若存在图G2=且且 ，及图，及图则称则称，记作，记作G2=G12022年年12月月28日星期三日星期三补图补图 G2=G1v2v1G1v3v4v5v2v1K5v3v4v5G2v2v3v4v5v12022年年12月月28日

18、星期三日星期三图的同构图的同构四、图的同构四、图的同构定义：定义：给定图给定图G1=，G2=若存在双射函数若存在双射函数f:V1 V2，使得对于任意使得对于任意u,v V1有有（或或 E1 E2）则称则称，记作，记作 2022年年12月月28日星期三日星期三图的同构图的同构例例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)=d可知，边可知，边v1,v2,v2,v3,v3,v4,v4,v1被分别映射成被分别映射成a,b,b,

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

20、等边数相等边数相等度数相等的结点数相等度数相等的结点数相等要注意的是，这不是充分条件要注意的是，这不是充分条件2022年年12月月28日星期三日星期三图的同构图的同构例例7.1.3 证明下面两个无向图是不同构的证明下面两个无向图是不同构的G1v1v2v3v4v5v6v7v8G2abcdefgh v1是是3度结点，故度结点，故f(v1)只能是只能是c或或d或或g或或h。若若f(v1)=c，由于，由于v2、v4和和v5与与v1邻接，因邻接，因此此f(v2)、f(v4)和和f(v5)应当分别为与应当分别为与c邻接的邻接的b、d和和g。但是，但是，v2、v4和和v5中，只有一个中，只有一个3度结点，度

21、结点，而而b、d、g中却有中却有2个个3度结点，故度结点，故f(v1)c。同理可说明，同理可说明，f(v1)也不可能是也不可能是d、g和和h。因此这样的因此这样的f是不存在的。是不存在的。因此因此G1和和G2是不同构的。是不同构的。2022年年12月月28日星期三日星期三第二节第二节 路路(链链)与回路与回路(圈圈)一、路一、路(链链)与回路与回路(圈圈)定义：给定图定义：给定图G=，令令v0,v1,vm V，e1,e2,em E称交替序列称交替序列为连接为连接v0到到vm的的称称v0和和vm为链（路）的为链（路）的和和链的链的为边（弧）的数目为边（弧）的数目m若若v0=vm，该链（路）称为，

22、该链（路）称为2022年年12月月28日星期三日星期三链和圈链和圈在链中：在链中：若任意若任意ei只出现一次，则称该链（路）为只出现一次，则称该链（路）为（路）（路）若任意若任意vi只出现一次，则称该链（路）为只出现一次，则称该链（路）为（路）（路）在圈中：在圈中：若任意若任意ei只出现一次，则称该圈只出现一次，则称该圈（回路）为回路）为（回路）回路）若任意若任意vi只出现一次，则称该圈只出现一次，则称该圈（回路）为回路）为（回路）回路）2022年年12月月28日星期三日星期三链和圈链和圈例例7.2.1 下图中：下图中：v3v1v4v5v2e1e2e3e4e5e6e7e8P1=(v1 e1 v

23、2 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 v5 e8 v4 e6 v2)是一个基本圈，也是一个简单圈是一个基本圈，也是一个简单圈2022年年12月月28日星期三日星期三链和圈链和圈上例中：上例中：(v2e2v3e3v3e4v1e1v2)也

24、可表示为也可表示为(e2e3e4e1)(v4e6v2e7v5e8v4e6v2e2v3)也可表示为也可表示为(e6e7e8e6e2)v3v1v4v5v2e1e2e4e5e6e3e8图中：图中：(v2e2v3e4v1e1v2e3v5e8v4)可表示为可表示为(e2e4e1e3e8)也可表示为也可表示为(v2v3v1v2v5v4)2022年年12月月28日星期三日星期三链和圈链和圈定理：定理：证明：证明：1)若从若从vi到到vj给定的链本身就是基本链，定理成立给定的链本身就是基本链，定理成立2)若从若从vi到到vj给定的链不是基本链，则给定的链不是基本链，则至少含有一个结点至少含有一个结点vk，它，

25、它在该链中至少出现两次以上在该链中至少出现两次以上。也就是说，经过也就是说，经过vk有一个圈有一个圈 ，于是可以从原有链中去除，于是可以从原有链中去除 中中所有出现的边（弧）。对于原链中所含的所有圈都做此处理，所有出现的边（弧）。对于原链中所含的所有圈都做此处理，最终将得到一条基本链（路）最终将得到一条基本链（路）2022年年12月月28日星期三日星期三链和圈链和圈问题：问题：例例7.2.2 若若u和和v是一个圈上的两个结点，是一个圈上的两个结点，u和和v一定是某个基本一定是某个基本圈上的结点吗？圈上的结点吗？(习题习题7-16)答：不一定答：不一定vaudcb本图中，本图中，u和和v在一个圈

26、上，在一个圈上，但是却不在一个基本圈上但是却不在一个基本圈上2022年年12月月28日星期三日星期三链和圈链和圈定理：在一个具有定理：在一个具有n个结点的图中，个结点的图中，证明：证明：1)根据基本链的定义可知，出现在基本链中的结点都是根据基本链的定义可知，出现在基本链中的结点都是不同的。因此在长度为不同的。因此在长度为m的基本链中，不同的结点数为的基本链中，不同的结点数为m+1又因为图中仅有又因为图中仅有n个结点，故个结点，故 m+1 n，即，即 m n-12)根据基本圈的定义可知，长度为根据基本圈的定义可知，长度为k的基本圈中，不同的结点数的基本圈中，不同的结点数为为k，图中共有图中共有n

27、个结点，所以个结点，所以 k n2022年年12月月28日星期三日星期三可达可达二、连通图二、连通图定义：定义：在一个图中，若从在一个图中，若从vi到到vj存在任何一条链存在任何一条链则称则称，简称，简称规定：规定：2022年年12月月28日星期三日星期三连通无向图连通无向图（一）连通无向图（一）连通无向图对于无向图对于无向图G=而言，可证明而言，可证明“可达性可达性”是一个是一个_关系关系。它对它对V给出一个划分，每个块中的元素形成一个诱导子图。给出一个划分，每个块中的元素形成一个诱导子图。两个结点间是可达的，当且仅当它们属于同一个子图两个结点间是可达的，当且仅当它们属于同一个子图称这样的子

28、图为称这样的子图为G的的，G的连通分图的个数记为的连通分图的个数记为(G)若若G中只有一个连通分图，则称中只有一个连通分图，则称G是是(即任意两结点可达即任意两结点可达)否则称否则称G为为，或，或等价等价2022年年12月月28日星期三日星期三连通无向图连通无向图定义：在无向图定义：在无向图G=中中若任意两个结点可达，则称若任意两个结点可达，则称G是是，称称G为为；否则称否则称G是非连通的，称是非连通的，称G为为或或。若若G的子图的子图G是连通的，且不存在包含是连通的，且不存在包含G的更大的的更大的G的的子图子图G是连通的，则称是连通的，则称G是是G的的，简称分图。，简称分图。G中连通分图的个

29、数记为中连通分图的个数记为。2022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.3v3v1v4v5v2v3v1v4v5v2G1G2G1是连通图，是连通图，(G1)=1G2是非连通图，是非连通图，(G2)=22022年年12月月28日星期三日星期三连通无向图连通无向图定义：定义：，是指是指V-SE-与与S中结点相连结的边中结点相连结的边而得到的子图，记做而得到的子图，记做G-SG-v3v3v1v4v5v2Gv3v1v4v5v2v3v1v4v5v22022年年12月月28日星期三日星期三连通无向图连通无向图定义：定义：，是指是指V-SE-与与S中结点相连结的边中结点相连结的边而

30、得到的子图，记做而得到的子图，记做G-SG-v3v1v4v5v2G2022年年12月月28日星期三日星期三连通无向图连通无向图定义：定义：，是指是指V不变不变E-T而得到的子图，记做而得到的子图，记做G-TG-e1,e3,e4v3v1v4v5v2Ge1e2e3e4e5e6e7v3v1v4v5v22022年年12月月28日星期三日星期三连通无向图连通无向图定义：定义：，是指是指V不变不变E-T而得到的子图，记做而得到的子图，记做G-TG-e1,e3,e4v3v1v4v5v2Ge2e5e6e72022年年12月月28日星期三日星期三连通无向图连通无向图定义：给定连通无向图定义：给定连通无向图G=，

31、S V若若 (G-S)(G)=1且对任意且对任意 T S，(G-T)=(G)则称则称S是是G的一个的一个若若S中仅含有一个元素中仅含有一个元素v，则称则称v是是G的的2022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.4G如下图所示，如下图所示，S=v1,v3v2v1v5v6v4Gv3v2v1v5v6v4G-Sv3v2v5v6v4G-S(G)=1，(G-S)=2(G-S)(G)2022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.4G如下图所示，如下图所示，S=v1,v3v2v1v5v6v4Gv3(G)=1，(G-S)=2(G-S)(G)(G-v1)=1v

32、2v5v6v4G-v1v32022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.4G如下图所示，如下图所示，S=v1,v3v2v1v5v6v4Gv3(G)=1，(G-S)=2(G-S)(G)(G-v1)=1v2v1v5v6v4G-v3(G-v3)=12022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.4G如下图所示，如下图所示，S=v1,v3v2v1v5v6v4Gv3v2v5v6v4G-S(G)=1，(G-S)=2(G-S)(G)(G-v1)=1(G-v3)=12022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.5G如下图所示，如下图所

33、示，S=v2v1v4v5v3Gv2(G)=1，(G-S)=2(G-S)(G)v1v4v5v3G-S2022年年12月月28日星期三日星期三连通无向图连通无向图定义：给定连通无向图定义：给定连通无向图G=，T E若若 (G-T)(G)=1且对任意且对任意 F T，(G-F)=(G)则称则称T是是G的一个的一个若若T中仅含有一个元素中仅含有一个元素e，则称则称e是是G的的，或桥，或桥2022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.6G如下图所示，如下图所示，T=e1,e2(G)=1，(G-T)=2(G-T)(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e

34、32022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.6G如下图所示，如下图所示，T=e1,e2(G)=1，(G-T)=2(G-T)(G)v1v3v4Gv2e1e4e2e3v1v3v4G-e1v2e4e2e3(G-e1)=12022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.6G如下图所示，如下图所示，T=e1,e2(G)=1，(G-T)=2(G-T)(G)v1v3v4Gv2e1e4e2e3(G-e1)=1(G-e2)=1v1v3v4G-e2v2e1e4e32022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.6G如下图所示，如下图所示

35、，T=e1,e2(G)=1，(G-T)=2(G-T)(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e3(G-e1)=1(G-e2)=12022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.7G如下图所示，如下图所示，T=e1(G)=1，(G-T)=2(G-T)(G)v1v3v4Gv2e1e2e3v1v3v4G-Tv2e2e32022年年12月月28日星期三日星期三连通无向图连通无向图定义：对连通的非平凡图定义：对连通的非平凡图G=，称称 (G)=min|S|S是是G的分离结点集的分离结点集为为G的的它表明产生分离图需要删去结点的最少数目它表明产生分离图需要

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

37、=0对存在割边的连通图对存在割边的连通图G而言，而言，(G)=1对无向完全图对无向完全图Kn，(Kn)=?T En-12022年年12月月28日星期三日星期三连通无向图连通无向图例例7.2.9求求G1和和G2的边连通度的边连通度 (G1)=2 (G2)=1v1v3v4G1v2e1e4e2e3v1v3v4G2v2e1e2e32022年年12月月28日星期三日星期三连通无向图连通无向图定理：对于任何一个无向图定理：对于任何一个无向图G，有有 证明：证明：1)若若G是分离图，则是分离图，则 (G)=(G)=0，而而 (G)02)若若G是连通图，先证明是连通图，先证明若若G是平凡图，则是平凡图，则 (

38、G)=0=(G)若若G不是平凡图，则当删去所有联结一个具有最小度的结点的边不是平凡图，则当删去所有联结一个具有最小度的结点的边（除了环）后，便产生了一个分离图，因此（除了环）后，便产生了一个分离图，因此 (G)(G)再证明再证明 若若 (G)1，则则G存在一个割边，存在一个割边，显然显然 (G)=(G)=1v3v1v4v5v2v1v1v3v4Gv2e1e2e3v1v3v4G e1v2e2e3v1v3v4Gv2e1e2e3v1v3v4G e1v2e2e3v3v4G v1v2e32022年年12月月28日星期三日星期三连通无向图连通无向图若若 (G)2，则删去某则删去某 (G)条边后，条边后，G就

39、成为分离图就成为分离图若只删除若只删除 (G)-1条边，则仍得到连通图且存在一割边条边，则仍得到连通图且存在一割边e=u,v对于对于 (G)-1条边中的每一条边，选取一个不同于条边中的每一条边，选取一个不同于u和和v的结点，的结点，把这些结点删去，将必须至少删去把这些结点删去，将必须至少删去 (G)-1条边条边若这样会产生分离图，则若这样会产生分离图，则若这样产生的仍是连通图且若这样产生的仍是连通图且e是割边，再删除结点是割边，再删除结点u或或v必将产生必将产生分离图，因此分离图，因此v1v3v4Gv2e4e3v1v3v4G v2e2e3v1v4G v3综上所述，有综上所述，有 2022年年1

40、2月月28日星期三日星期三连通无向图连通无向图定理：一个连通无向图定理：一个连通无向图G中的结点中的结点v是割点，充要条件是是割点，充要条件是存在两个结点存在两个结点u和和w，使得联结使得联结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

41、和和w不可达。故不可达。故G中联结中联结u和和w的每条链的每条链必经过必经过v2022年年12月月28日星期三日星期三连通无向图连通无向图同理可以证明：同理可以证明：定理：一个连通无向图定理：一个连通无向图G中的边中的边e是割边，充要条件是是割边，充要条件是存在两个结点存在两个结点u和和w，使得联结使得联结u和和w的每条链都经过的每条链都经过e定理：一个连通无向图定理：一个连通无向图G中的边中的边e是割边，充要条件是是割边，充要条件是e不包含在不包含在G的任何基本圈中的任何基本圈中证明：教材证明：教材P172（定理（定理7.8)2022年年12月月28日星期三日星期三乌拉姆猜想（乌拉姆猜想（1

42、929）左右两张相片，捂住左边相片的一部分，也捂住右边相片左右两张相片，捂住左边相片的一部分，也捂住右边相片的相应部分，例如都捂住左眼，能看到的相片的大部分形的相应部分，例如都捂住左眼，能看到的相片的大部分形象一致；再分别捂住左右相片的另一个对应部分，例如右象一致；再分别捂住左右相片的另一个对应部分，例如右耳，结果能看到的相片的大部分仍然一致。如此轮番地观耳，结果能看到的相片的大部分仍然一致。如此轮番地观察各次对应的暴露部分，都会看到相同的形象，那么谁都察各次对应的暴露部分，都会看到相同的形象，那么谁都会相信这两张照片是同一个人或孪生兄弟的留影。会相信这两张照片是同一个人或孪生兄弟的留影。数学

43、描述：有图数学描述：有图G1=V1,E1和和G2=V2,E2，V1=v1,v2,vn，V2=u1,u2,un（n3）。）。如果如果G1-vi G2-ui，i=1,2,n，则，则G1 G22022年年12月月28日星期三日星期三连通有向图连通有向图（二）连通有向图（二）连通有向图对于有向图对于有向图G=而言，而言，它仅仅是它仅仅是定义：对于给定的有向图定义：对于给定的有向图G，要略去要略去G中每条边的方向，中每条边的方向，便得到一个无向图便得到一个无向图G，称称G是是G的的2022年年12月月28日星期三日星期三连通有向图连通有向图定义：在简单有向图定义：在简单有向图G中，中，若任何两个结点间都

44、是可达的，则称若任何两个结点间都是可达的，则称G是是的的若任何两个结点间，至少是从一个结点可达另一个结点，若任何两个结点间，至少是从一个结点可达另一个结点，则称则称G是是的的若若G的基础图是连通的，则称的基础图是连通的，则称G是是的的2022年年12月月28日星期三日星期三连通有向图连通有向图例例7.2.10 判断判断G1、G2和和G3是强连通？单向连通？弱连通？是强连通？单向连通？弱连通？G1是强连通的是强连通的v1v3v4G1v2v1v3v4G2v2v1v3v4G3v2G2是单向连通的是单向连通的G3是弱连通的是弱连通的2022年年12月月28日星期三日星期三连通有向图连通有向图由定义可知

45、：由定义可知：若若G是强连通的，则它必定是单向连通的是强连通的，则它必定是单向连通的反之未必真反之未必真若若G是单向连通的，则它必是弱连通的是单向连通的，则它必是弱连通的反之未必真反之未必真2022年年12月月28日星期三日星期三连通有向图连通有向图定理：有向图定理：有向图G是强连通的，当且仅当是强连通的，当且仅当证明：证明：1)充分性：若充分性：若G中存在一条回路，它至少通过每个结点一中存在一条回路，它至少通过每个结点一回，则回，则G中任何两个结点都是互相可达的，所以中任何两个结点都是互相可达的，所以G是强连通的。是强连通的。2)必要性：若必要性：若G是强连通的，则是强连通的，则G中任何两个

46、结点都是互相可达中任何两个结点都是互相可达的，因此可以做出一条回路经过的，因此可以做出一条回路经过G中所有结点，中所有结点，否则，必有某结点否则，必有某结点v不在该回路上不在该回路上，v与回路上的各结点不可能都与回路上的各结点不可能都互相可达。与互相可达。与G是强连通的矛盾是强连通的矛盾2022年年12月月28日星期三日星期三连通有向图连通有向图定义：在简单有向图定义：在简单有向图G中中具有强连通性质的极大子图，称为具有强连通性质的极大子图，称为具有单向连通性质的极大子图，称为具有单向连通性质的极大子图，称为具有弱连通性质的极大子图，称为具有弱连通性质的极大子图，称为2022年年12月月28日

47、星期三日星期三连通有向图连通有向图例例7.2.11求求G的强分图、单向分图和弱分图的强分图、单向分图和弱分图v3v2v1Gv4v5v6v3v2v1v4v5v6G的强分图有：的强分图有：定理：定理：简单有向图简单有向图G中的任意一个结点，恰位于一个强分图中中的任意一个结点，恰位于一个强分图中2022年年12月月28日星期三日星期三连通有向图连通有向图定理：定理：简单有向图简单有向图G中的任意一个结点，恰位于一个强分图中中的任意一个结点，恰位于一个强分图中证明：由强分图的定义可知，证明：由强分图的定义可知，G中每个结点位于一个强分图中中每个结点位于一个强分图中假设假设G中存在结点中存在结点v位于两

48、个强分图位于两个强分图G1和和G2中中则由强分图的定义可知，则由强分图的定义可知，G1中的每个结点与中的每个结点与v互相可达，互相可达，G2中中的每个结点也与的每个结点也与v互相可达互相可达故故G1中的每个结点与中的每个结点与G2中的每个结点通过中的每个结点通过v，能够互相可达，这能够互相可达，这与与G1和和G2是两个强分图矛盾是两个强分图矛盾因此因此G中每个结点只能位于一个强分图中中每个结点只能位于一个强分图中2022年年12月月28日星期三日星期三连通有向图连通有向图例例7.2.11求求G的强分图、单向分图和弱分图的强分图、单向分图和弱分图G的单向分图有：的单向分图有：v3v2v1Gv4v

49、5v6v3v2v1v4v5v5v6定理：定理：简单有向图简单有向图G中的每个结点和每条弧中的每个结点和每条弧,至少位于一个单向分图中至少位于一个单向分图中2022年年12月月28日星期三日星期三连通有向图连通有向图例例7.2.11求求G的强分图、单向分图和弱分图的强分图、单向分图和弱分图G的弱分图有：的弱分图有：v3v2v1Gv4v5v6v3v2v1v4v5v6定理：定理：简单有向图简单有向图G中的每个结点和每条弧中的每个结点和每条弧 恰位于一个弱分图中恰位于一个弱分图中2022年年12月月28日星期三日星期三结点间的距离结点间的距离三、结点间的距离三、结点间的距离定义：在图定义：在图G中，若

50、结点中，若结点u可达结点可达结点v，它们之间可能存在不止它们之间可能存在不止一条链（路）。一条链（路）。在所有链中，在所有链中，称为结点称为结点u和和v之间的之间的（或短程线、测地线）。记做：（或短程线、测地线）。记做：2022年年12月月28日星期三日星期三结点间的距离结点间的距离距离满足下面性质：距离满足下面性质：d 0d=0d+d d若若u不可达不可达v，则则 d=+即使即使u和和v互相可达，互相可达，d未必等于未必等于d 2022年年12月月28日星期三日星期三有向图在计算机中的应用有向图在计算机中的应用四、有向图在计算机中的应用四、有向图在计算机中的应用这里给出一个简单有向图在计算机