第6章图论PPT讲稿.ppt

《第6章图论PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第6章图论PPT讲稿.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章图论章图论第1页，共91页，编辑于2022年，星期一转化转化Euler1736年年 图论中讨论的图 问题：是否能从四块陆地中问题：是否能从四块陆地中的任一块开始，通过每座桥的任一块开始，通过每座桥恰好一次再回到起点？恰好一次再回到起点？是否能从任意一个顶点开始，通过每条边恰好一次再回到起点？包含两个要素：对象（陆地）及对象间的二元关系（是否有桥连接）问题一问题一:哥尼斯哥尼斯堡堡七桥问題七桥问題第2页，共91页，编辑于2022年，星期一Leonhard Euler(公元1707-1783年)1707年出生在瑞士的巴塞尔城，13岁就进巴塞尔大学读书，师从著名的数学家约翰.伯努利。他从19

2、岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明欧拉在数学上的建树很多，对著名的哥尼斯堡七

3、桥问题的解答开创了图论的研究。第3页，共91页，编辑于2022年，星期一问题二：四色问题问题二：四色问题四四色色问问题题是是世世界界近近代代三三大大数数学学难难题之一。题之一。四四色色问问题题的的内内容容是是：任任何何一一张张地地图图只只用用四四种种颜颜色色就就能能使使具具有有共共同同边界的国家着上不同的颜色。边界的国家着上不同的颜色。它它的的提提出出来来自自英英国国。1852年年，毕毕业业于于伦伦敦敦大大学学的的弗弗南南西西斯斯格格思思里里发发现现了了一一种种有有趣趣的的现现象象：“看看来来，每每幅幅地地图图都都可可以以用用四四种种颜颜色色着着色色，使使得得有有共共同同边边界界的的国国家家都

4、都被被着着上上不不同同的的颜颜色色。”这这个个现现象象能能不不能能从从数数学上加以严格证明呢？学上加以严格证明呢？第4页，共91页，编辑于2022年，星期一进进入入20世世纪纪以以来来，科科学学家家们们对对四四色色猜猜想想的的证证明明基基本本上上是是按按照照肯肯肯肯普普普普的的想想法法在在进进行行。后后来来美美国国数数学学家家富富富富兰兰兰兰克克克克林林林林于于1939年年证证明明了了22国国以以下下的的地地图图都都可可以以用用四四色色着着色色。1950年年，有有人人从从22国国推推进进到到35国国。1960年年，有有人人又又证证明明了了39国国以以下下的的地地图图可可以以只只用四种颜色着色；

5、随后又推进到了用四种颜色着色；随后又推进到了50国。国。1976年年6月月，美美国国伊伊利利诺诺大大学学哈哈哈哈肯肯肯肯与与阿阿阿阿佩佩佩佩尔尔尔尔在在两两台台不不同同的的电电子子计计算算机机上上，用用了了1200个个小小时时，作作了了100亿亿判判断断，终终于于完完成成了四色定理的证明，轰动了世界。了四色定理的证明，轰动了世界。然而，真正数学上的严格证明仍然没有得到！数学家仍为此努然而，真正数学上的严格证明仍然没有得到！数学家仍为此努力，并由此产生了多个不同的图论分支。力，并由此产生了多个不同的图论分支。问题二：四色问题问题二：四色问题第5页，共91页，编辑于2022年，星期一问题三：问题三

6、：Hamilton问题问题Hamilton问问题题源源于于1856年年，英英国国数数学学家家Hamilton设设计计了了一一个个名名为为周周游游世世界界的的游游戏戏：他他用用一一个个正正十十二二面面体体的的二二十十个个端端点点表表示示世世界界上上的的二二十十座座大大城城市市（见见图图），提提出出的的问问题题是是要要求求游游戏戏者者找找一一条条沿沿着着十十二二面面体体的的棱棱通通过过每每个个端端点点恰恰好好一一次次的的行行走走路路线线。反反映映到到图图论论上上就就是是判判断断一一个个给给定定的的图图是是否否存存在一条含所有顶点的回路。在一条含所有顶点的回路。Hamilton至今尚无有效方法來解決

7、！至今尚无有效方法來解決！第6页，共91页，编辑于2022年，星期一问题四问题四:校园网络校园网络第7页，共91页，编辑于2022年，星期一一直往前走一直往前走碰壁就回碰壁就回头头換条路找換条路找沿途要沿途要记录记录下走过的下走过的路线路线问题五问题五:游戏游戏第8页，共91页，编辑于2022年，星期一程序调用的图论模型程序调用的图论模型第9页，共91页，编辑于2022年，星期一设备更新问题设备更新问题。第i年初1234购置费（万元）2.52.62.83.1使用年限1234每年的维修与运行费（万元）11.524某工厂的某台机器可连续工作某工厂的某台机器可连续工作4年，决策者每年年初都要决定年，

8、决策者每年年初都要决定机器是否需要更新。若购置新的，就要支付一定的购置费用；机器是否需要更新。若购置新的，就要支付一定的购置费用；若继续使用，则要支付一定的维修与运行费用，而且随着机若继续使用，则要支付一定的维修与运行费用，而且随着机器使用年限的增加费用逐年增多。计划期（器使用年限的增加费用逐年增多。计划期（4 年）中每年年初年）中每年年初的购置价格及各个年限内维修与运行费用由下表给出，试制的购置价格及各个年限内维修与运行费用由下表给出，试制订今后订今后4年的机器更新计划，使总的支付费用最少。年的机器更新计划，使总的支付费用最少。第10页，共91页，编辑于2022年，星期一解解：把把该该问问题

9、题看看成成一一个个最最短短路路问问题题。设设v1和和v5分分别别表表示示计计划划期期的的始始点点和和终终点点（x5可可理理解解为为第第4年年年年末末）。图图中中各各边边(vi,vj)表表示示在在第第i 年年初初购购进进的的机机器器使使用用到到第第j 年年初初（即即第第j 1年底），边旁的数字由表中的数据得到。年底），边旁的数字由表中的数据得到。第11页，共91页，编辑于2022年，星期一又又如如果果已已知知不不同同役役龄龄机机器器年年末末的的处处理理价价格格如如下下表表所所示示，那那末末在在这这计计划划期期内内机机器器的的最最优优更更新新计计划又会怎样？划又会怎样？年度第1年末第2年末第3年末

10、第4年末机器处理价（万元）2.01.61.31.1第12页，共91页，编辑于2022年，星期一 关于第二问，类似于第一问，可转化为求下图中从 v1 到 v5 的最短路问题。按照最短路算法可得最短路 v1,v2,v3,v5，即计划期内机器更新最优计划为第 1 年、第 3 年初各购进一台新机器，4 年总的支付费用为 6.8万元。第13页，共91页，编辑于2022年，星期一1.图的定义图的定义图G(graph)主要由主要由2部分组成部分组成:(1)节点集合节点集合V,其中的元素称为其中的元素称为节点.(2)边集合边集合E,其中的元素称为其中的元素称为边.通常将图通常将图G记为记为G=(V,E).第1

11、4页，共91页，编辑于2022年，星期一(a)节点又可以称为点、顶点或结点节点又可以称为点、顶点或结点,常用一个实心点或空心点常用一个实心点或空心点表示表示,但在实际应用中还可以用诸如方形、圆形、菱形等符但在实际应用中还可以用诸如方形、圆形、菱形等符号号.(b)边及其的表示边及其的表示.无向边?b3=AB=BA=A,B(可重).有向边(弧)?几点说明几点说明:所有边都是无向边的图称为无向图；所有边都是无向边的图称为无向图；所有边都是有向边的图称为有向图所有边都是有向边的图称为有向图.第15页，共91页，编辑于2022年，星期一(c)图的拓扑不变性质图的拓扑不变性质.需要注意的是需要注意的是,我

12、们讨论的图我们讨论的图不但与节点位置无关不但与节点位置无关,而且与边的形状和长短也无而且与边的形状和长短也无关关.有有n个节点的图称为个节点的图称为n阶图阶图,有有n个节点个节点m条边的图称条边的图称为为(n,m)图图.在图在图G=(V,E)中中,称称V=的图为空图的图为空图,记为记为.几点说明几点说明:第16页，共91页，编辑于2022年，星期一若若V 但但E=的图称为的图称为零图,n阶零图可记为阶零图可记为Nn.仅一个节点的零图称为平凡图仅一个节点的零图称为平凡图.第17页，共91页，编辑于2022年，星期一定义：设定义：设G=(V,E)是图是图,对于任意对于任意u,v V,若从节若从节点

13、点u到节点到节点v有边有边,则称则称u邻接到v或称或称u和和v是邻接的是邻接的.2.邻接邻接无向图无向图?有向图有向图?第18页，共91页，编辑于2022年，星期一(无向图的两条边邻接是指它们有公共端点无向图的两条边邻接是指它们有公共端点.)(平面图的面相邻平面图的面相邻?)第19页，共91页，编辑于2022年，星期一3.关联关联定义：定义：设设G=(V,E)是图是图,e E,e的两个端点分别的两个端点分别为为u和和v,则称边则称边e与节点与节点u以及边以及边e与节点与节点v是关联的是关联的.图的任意一条边都关联两个节点图的任意一条边都关联两个节点.关联相同两个节点关联相同两个节点的边称为吊环

14、的边称为吊环,可简称环可简称环.关联的起点相同与终点也相关联的起点相同与终点也相同的边称为多重边或平行边同的边称为多重边或平行边,其边数称为边的重数其边数称为边的重数.第20页，共91页，编辑于2022年，星期一4.简单图简单图(1)简单图简单图定义：定义：设设G=(V,E)是图是图,若若G中既无吊环又无多中既无吊环又无多重边重边,则称则称G是是简单图.彼得森彼得森(Petersen,18311910)图图,是一种妖怪图是一种妖怪图.第21页，共91页，编辑于2022年，星期一第22页，共91页，编辑于2022年，星期一妖怪图妖怪图?Petersen图称为图称为单星妖怪单星妖怪.下面的图称为下

15、面的图称为双星妖怪双星妖怪.第23页，共91页，编辑于2022年，星期一(2)完全无向图完全无向图Def设设G=(V,E)是是n阶简单无向图阶简单无向图,若若G中任意中任意节点都与其余节点都与其余n-1个节点邻接个节点邻接,则称则称G为为n阶阶完全无向图，记为，记为Kn.K5:第24页，共91页，编辑于2022年，星期一将将n阶完全无向图阶完全无向图Kn的边任意加一个方向所得到的有向的边任意加一个方向所得到的有向图称为图称为n阶阶竞赛图.设设G=(V,E)是是n阶简单有向图阶简单有向图,若若G中任意节点都与其中任意节点都与其余余n-1个节点邻接个节点邻接,则称则称G为为n阶阶完全有向图。第25

16、页，共91页，编辑于2022年，星期一(3)补图补图Def设设G=(V,E)是是n阶简单无向图阶简单无向图,由由G的所有节的所有节点以及由能使点以及由能使G成为成为Kn需要添加的边构成的图称需要添加的边构成的图称为为G的的补图,记为记为(u和和v在在G中不邻接中不邻接u和和v在在中邻接中邻接)第26页，共91页，编辑于2022年，星期一6.2 节点的度数“七桥七桥”中从一个地方出发的桥的数目就是对中从一个地方出发的桥的数目就是对应节点的度数应节点的度数.边与节点的边与节点的关联次数关联次数?第27页，共91页，编辑于2022年，星期一Def设设G=(V,E)是无向图是无向图,v V,称与节点称

17、与节点v关联的所有边的关联次数之和为节点关联的所有边的关联次数之和为节点v的的度数(degree),记为记为deg(v).一个环算一个环算2度度?第28页，共91页，编辑于2022年，星期一Def设设G=(V,E)是有向图是有向图,v V,称以称以v为为起点的起点的边的数目为节点的边的数目为节点的出度(out-degree),记为记为deg+(v),以以v为终点的边的数目为节点的为终点的边的数目为节点的入度(in-degree),记为记为deg-(v),称称deg+(v)+deg-(v)为节点为节点v的的度数,记为记为deg(v).一个环算一个环算2度度?第29页，共91页，编辑于2022年，

18、星期一图论第一定理图论第一定理,常称为常称为“握手握手(?)定理定理”.Theorem6-1在任何在任何(n,m)图图G=(V,E)中中,其所其所有节点度数之和等于边数有节点度数之和等于边数m的的2倍倍,即即Corollary 在任意图在任意图G=(V,E)中中,度数为奇数的度数为奇数的节点个数必为偶数节点个数必为偶数.Proof第30页，共91页，编辑于2022年，星期一由定理及其推论很容易知道由定理及其推论很容易知道,在任何一次聚会上在任何一次聚会上,所有人握手次数之和必为偶数并且握了奇数次手所有人握手次数之和必为偶数并且握了奇数次手的人数必为偶数的人数必为偶数.(环的解释环的解释?)Th

19、eorem6-2在任意有向图中在任意有向图中,所有节点的出度之和所有节点的出度之和等于入度之和等于入度之和.在任意图中在任意图中,度数为度数为0的节点称为的节点称为孤立点。度数为。度数为1的节点称为的节点称为悬挂点。第31页，共91页，编辑于2022年，星期一例例6-1 6-1 证明证明:对于任意对于任意n(n 2)个人的组里个人的组里,必有两必有两个人有相同个数的朋友个人有相同个数的朋友.Proof将组里的每个人看作节点将组里的每个人看作节点,两个人是朋友当且两个人是朋友当且仅当对应的节点邻接仅当对应的节点邻接,于是得到一个于是得到一个n阶简单无向阶简单无向图图G,进而进而G中每节点的度数可

20、能为中每节点的度数可能为0,1,2,n-1中一个中一个.第32页，共91页，编辑于2022年，星期一当当G中无孤立点时中无孤立点时,于是每节点的度数可能为于是每节点的度数可能为1,2,n-1.由于共有由于共有n个节点个节点,于是必有两节点度于是必有两节点度数相同数相同.当当G中有孤立点时中有孤立点时,这时每节点的度数只可能为这时每节点的度数只可能为0,1,2,n-2.同样由于共同样由于共n有个节点有个节点,因此必有两节因此必有两节点度数相同点度数相同.第33页，共91页，编辑于2022年，星期一若一个若一个Simple无向图无向图G的每节点度数均为的每节点度数均为k,则称则称G为为k-正则图(

21、k-regulargraph).例例6-2设无向图设无向图G是一个是一个3-正则正则(n,m)图图,且且2n3=m,求求n和和m各是多少各是多少?Hint 根据握手定理有根据握手定理有:第34页，共91页，编辑于2022年，星期一Def最大度、最小度；最小出度、最小入度最大度、最小度；最小出度、最小入度任意图任意图G=(V,E):有向图有向图G=(V,E):第35页，共91页，编辑于2022年，星期一对于无向图对于无向图G=(V,E),V=v1,v2,vn,称称deg(v1),deg(v2),deg(vn)为的为的度数序列.对于有向对于有向图图,还可以定义其出度序列和入度序列还可以定义其出度序

22、列和入度序列.例例6-36-3是否存在一个无向图是否存在一个无向图G,其度数序列分别为其度数序列分别为(1)7,5,4,2,2,1.(2)4,4,3,3,2,2.(1)由于序列由于序列7,5,4,2,2,1中中,奇数个数为奇数奇数个数为奇数,根据握手定理的根据握手定理的推论知推论知,不可能存在一个图其度数序列为不可能存在一个图其度数序列为7,5,4,2,2,1.(2)因为序列因为序列4,4,3,3,2,2中中,奇数个数为偶数奇数个数为偶数,可以得到一可以得到一个无向图个无向图,其度数序列为其度数序列为4,4,3,3,2,2.第36页，共91页，编辑于2022年，星期一6.3 子图、图的运算和图

23、同构1.子图子图可以通过一个图的子图去考察原图的有关性可以通过一个图的子图去考察原图的有关性质以及原图的局部结构质以及原图的局部结构.Def设设G=(V,E)和和H=(W,F)是图是图,若若W V且且F E,则称则称H=(W,F)是是G=(V,E)的的子图.若若H=(W,F)是是G=(V,E)的子图且的子图且W=V,则称则称H=(W,F)是是G=(V,E)的的生成子图.第37页，共91页，编辑于2022年，星期一例例子图子图子图子图第38页，共91页，编辑于2022年，星期一第39页，共91页，编辑于2022年，星期一第40页，共91页，编辑于2022年，星期一常见的常见的4种产生种产生G=(

24、V,E)的子图的方式如下的子图的方式如下:(1)GW设设W V,则以则以W为节点集合为节点集合,以两端以两端点均属于点均属于W的所有边为边集合构成的子图的所有边为边集合构成的子图,称为称为由W导出的子图(inducedsubgraphbyW),记记为为GW.第41页，共91页，编辑于2022年，星期一(2)GW设设W V,导出子图导出子图GVW记为记为GW,是在是在G中去掉所有中去掉所有W中的节点中的节点,同时也要同时也要去掉与去掉与W中节点关联的所有边中节点关联的所有边.通常将通常将Gv记为记为G-v.(3)GF设设F E,则以则以F为边集合为边集合,以以F中边的中边的所有端点为节点集合构成

25、的子图所有端点为节点集合构成的子图,称为称为由F导出的子图(inducedsubgraphbyF),记为记为GF.第42页，共91页，编辑于2022年，星期一(4)GF设设F E,则从则从G中去掉中去掉F中的所有边中的所有边得到的生成子图记为得到的生成子图记为GF.第43页，共91页，编辑于2022年，星期一简单图简单图G=(V,E)的补图的补图G+U:(与子图无关与子图无关)第44页，共91页，编辑于2022年，星期一2.*图的运算图的运算图的运算就是通过一定的操作图的运算就是通过一定的操作,产生产生“新新”的图的图.前面的子图的产生实际上就是图的运算前面的子图的产生实际上就是图的运算,但它

26、们都但它们都是在一个图中进行讨论的是在一个图中进行讨论的.也便于用代数方法讨也便于用代数方法讨论图论图.Def(1)第45页，共91页，编辑于2022年，星期一(2)(3)(4)思考 图的每种运算的性质有哪些图的每种运算的性质有哪些?它与集合的并、它与集合的并、交、差、交、差、(补补)及环和及环和(对称差对称差)运算的性质有什么运算的性质有什么不同不同?第46页，共91页，编辑于2022年，星期一3.图同构图同构由于图的拓扑性质由于图的拓扑性质,有可能两个表面上看起来不同的有可能两个表面上看起来不同的图本质上是同一个图图本质上是同一个图,这就是图同构的问题这就是图同构的问题.Def设设G1=(

27、V1,E1)和和G2=(V2,E2)是无向图，若存在一是无向图，若存在一个双射个双射:V1V2使得对于任意使得对于任意u,vV1，(u,v)E1当且仅当且当且仅当且(u)(v)E2且边的重数相同，则称且边的重数相同，则称G1与与G2同构，记为同构，记为G1 G2.直观理解直观理解:G1 G2是指其中一个图仅经过下列两种是指其中一个图仅经过下列两种变换可以变为另一个图变换可以变为另一个图:(a)挪动节点的位置；挪动节点的位置；(b)伸缩边的长短伸缩边的长短.第47页，共91页，编辑于2022年，星期一无向图无向图:第48页，共91页，编辑于2022年，星期一有向图有向图:对于两个有向图同构的判断

28、对于两个有向图同构的判断,特别要注特别要注意边的方向的一致性意边的方向的一致性.思考 给出至少给出至少4个两个图同构的必要条件个两个图同构的必要条件.第49页，共91页，编辑于2022年，星期一Ulam猜想猜想?Simplegraphs:第50页，共91页，编辑于2022年，星期一6.4 路与回路在图在图G=(V,E)中中,经常考虑从一个节点出发经常考虑从一个节点出发,沿着一些边连续移动到另一个节点的问题沿着一些边连续移动到另一个节点的问题,这这就是路的概念就是路的概念.1.路路(walk,way)Def对于任意图对于任意图G=(V,E)中，称中，称G中节点与中节点与边交替出现的序列为一条路。

29、边交替出现的序列为一条路。第51页，共91页，编辑于2022年，星期一路的起点路的起点;终点终点;路的长度路的长度;平凡路平凡路.需要注意的是需要注意的是,有向图中的路须按边的方向走有向图中的路须按边的方向走,有向有向图中的路可称为有向路图中的路可称为有向路.第52页，共91页，编辑于2022年，星期一有两种特殊的路有两种特殊的路:一种是节点不重复的路一种是节点不重复的路,称为称为路径.一种是边不重复的路一种是边不重复的路,称为称为轨迹.显然显然,路径是轨迹路径是轨迹,但轨迹不一定是路径但轨迹不一定是路径.说明由于图论应用的广泛性由于图论应用的广泛性,很多概念存在很多概念存在意义上的差别意义上

30、的差别.之所以选择之所以选择“路径路径”,它有捷它有捷径之意；径之意；“轨迹轨迹”强调边不重复强调边不重复,它是它是(可能多可能多次次)走过后留下的痕迹走过后留下的痕迹.第53页，共91页，编辑于2022年，星期一在在n阶图阶图G=(V,E)中中,若存在从节点若存在从节点v0到到vl一条路一条路(v0 vl),则存在一条从则存在一条从v0到到vl一条长度一条长度 n-1的的路路径径.Def在图在图G=(V,E),称节点称节点u到到v的边数最少的长度为的边数最少的长度为u到到v的距离，记为的距离，记为d(u,v)。d(u,v):u到到v边数最少的路径长度边数最少的路径长度.称称maxd(u,v)

31、为图为图G的的直径直径，记为，记为diam(G).第54页，共91页，编辑于2022年，星期一2.回路回路Def起点与终点相同的起点与终点相同的(长度长度 1)路称为路称为回路回路.边不重复的回路称为边不重复的回路称为简单回路简单回路（闭迹（闭迹).除起点重复一次外除起点重复一次外,别的节点均不重复的简单回路别的节点均不重复的简单回路称为称为圈或环圈或环,第55页，共91页，编辑于2022年，星期一显然显然,圈圈简单回路简单回路,但反过来不成立但反过来不成立.有有n个节点的圈称为个节点的圈称为n阶圈阶圈,记为记为Cn.在在n-1阶圈阶圈Cn-1的内部放置一个节点的内部放置一个节点,并使之与并使

32、之与Cn-1的每个节点邻接的每个节点邻接,这样得到的图称为这样得到的图称为n阶轮图阶轮图,记记为为Wn.第56页，共91页，编辑于2022年，星期一在在n阶图阶图G=(V,E)中中,若存在从节点若存在从节点v0到到v0一条一条简简单单回路回路,则存在一条从则存在一条从v0到到v0一条长度一条长度 n的的圈圈.第57页，共91页，编辑于2022年，星期一采用采用“最长路径法最长路径法”技巧技巧.Theorem在无向图在无向图G=(V,E)中中,若任意若任意v V有有deg(v)2,则则G中存在圈中存在圈.Proof不妨设不妨设G是简单图是简单图.在在G中选取一条最长的路径中选取一条最长的路径L:

33、v0v1vl.第58页，共91页，编辑于2022年，星期一6.5 图的连通性图的基本性质之一是其连通性图的基本性质之一是其连通性,它与图中从节它与图中从节点到节点的路密切相关点到节点的路密切相关.为了讨论方便为了讨论方便,先给先给出出Def在任何图在任何图G=(V,E)中中,若从节点若从节点u到到v存存在一条路在一条路,则称则称u可达可达v(accessible).由于节点由于节点v到到v总存在一条长度为总存在一条长度为0的路的路,因此因此任意节点任意节点v可达可达v自身自身.第59页，共91页，编辑于2022年，星期一先讨论无向图的连通性先讨论无向图的连通性.1.无向图的连通性无向图的连通性

34、Def6-17设设G=(V,E)是无向图是无向图,对于对于G中任意两中任意两个节点个节点u和和v均可达均可达,则称则称G是是连通图.第60页，共91页，编辑于2022年，星期一Def设设G=(V,E)是无向图是无向图,G中极大的连通子图中极大的连通子图称为称为G的的连通分支(connectedcomponent),图图G的的连通分支数记为连通分支数记为w(G).由定义知由定义知,图图G的连通分支满足的连通分支满足3个条件个条件:(1)连通分连通分支是支是G的子图；的子图；(2)该子图本身是连通图；该子图本身是连通图；(3)在在该子图中再添加原图的任意边或节点都不连通该子图中再添加原图的任意边或

35、节点都不连通.第61页，共91页，编辑于2022年，星期一Theorem设设G=(V,E)是无向图是无向图,则则G是连通图当是连通图当且仅当且仅当w(G)=1.G是非连通图当且仅当w(G)2.例例6-5G不连通不连通连通连通.Hint u,v:(1)u,v在在G中不邻接中不邻接.(2)u,v在在G中邻接中邻接:第一种方法:根据定义证明!第62页，共91页，编辑于2022年，星期一例例6-6 设设G=(V,E)是是n阶简单无向图阶简单无向图,若若对于对于任意的任意的G中不相邻的节点中不相邻的节点u和和v有有deg(u)+deg(v)n-1,则则G是连通图是连通图.Hint(反证反证)Theore

36、m6-7去掉简单回路上的去掉简单回路上的一条一条边或度为边或度为1的节的节点点,图的连通性不变图的连通性不变.第二种方法:反证法!第63页，共91页，编辑于2022年，星期一2.无向连通图的点连通度与边连通度无向连通图的点连通度与边连通度对于无向连通图对于无向连通图,其连通的程度是不同的其连通的程度是不同的,有些很有些很“脆弱脆弱”,有的则相反有的则相反.(1)点割集与点连通度点割集与点连通度(G).Def设设G=(V,E)是是连通连通无向图无向图,W V,(i)GW不连通或是不连通或是1阶图阶图;(ii)删除删除W的任意真子集均连的任意真子集均连通通,则称则称W为为G的点割集的点割集.“割”

37、是分割、分离、分开的意思,恰使得G不连通或是1阶图所要去掉的节点集合称为的点割集.若点割集W=v,则称v为的割点或关节点.第64页，共91页，编辑于2022年，星期一点割集点割集:a,b;c,d.(G)=2.边割集边割集:e1,e2,e3.(G)=3.第65页，共91页，编辑于2022年，星期一割点割点:A;B.(G)=1.割边割边:e.(G)=1.第66页，共91页，编辑于2022年，星期一Def根据定义根据定义,一个连通无向图的点连通度是使得一个连通无向图的点连通度是使得G不连通或为不连通或为1阶图所要删去的最少的节点个数阶图所要删去的最少的节点个数.于是于是,1阶图的点连通度为阶图的点连

38、通度为0,而完全无向图而完全无向图Kn的点连的点连通度为通度为n-1.第67页，共91页，编辑于2022年，星期一点连通度为点连通度为2的图的图G称为称为2-连通或连通或重连通图.确定一个无向图是否重连通具有重要的意义确定一个无向图是否重连通具有重要的意义.假定无假定无向图的节点表示电话交换站向图的节点表示电话交换站,边表示电话线边表示电话线,则在点连则在点连通度为通度为2的通讯网络系统中的通讯网络系统中,一个站发生故障系统仍可一个站发生故障系统仍可正常工作正常工作.第68页，共91页，编辑于2022年，星期一(2)边割集与边连通度边割集与边连通度(G).Def设设G=(V,E)是连通无向图且

39、是连通无向图且F E,若从若从G中删中删除除F的所有边所得到的子图不连通或是平凡图的所有边所得到的子图不连通或是平凡图,而删除而删除F的任意真子集都连通的任意真子集都连通,则称则称F为为G的的边割集.恰使得恰使得G不连通或是平凡图所要去掉的边的集合称为不连通或是平凡图所要去掉的边的集合称为G的边割集的边割集.若边割集若边割集F=e,则称则称e为的割边或桥为的割边或桥.第69页，共91页，编辑于2022年，星期一Def根据定义根据定义,一个连通无向图一个连通无向图G的边连通度是使得的边连通度是使得G不连通或为平凡图所要删去的最少的边的数不连通或为平凡图所要删去的最少的边的数目目.H.Whitne

40、y在在1932年给出的关于点连通度、边连通年给出的关于点连通度、边连通度及最小度之间的联系的一个结论度及最小度之间的联系的一个结论.Theorem6-8设设G=(V,E)是连通是连通无向图无向图,则则第70页，共91页，编辑于2022年，星期一Proof(1)由于将任意一个节点所关联的边全去掉由于将任意一个节点所关联的边全去掉后都不连通后都不连通,所以有所以有(2)设设F是是G的恰具有的恰具有条边的边割集条边的边割集.考虑删除考虑删除F中中条边条边.删除后不连通删除后不连通,显然显然若删除后连通若删除后连通,则存在桥则存在桥uv=u,v.再删除再删除u或或v,即得知结论成立即得知结论成立.第7

41、1页，共91页，编辑于2022年，星期一3.有向图的连通性有向图的连通性(1)强连通图强连通图Def设设G=(V,E)是有向图是有向图,u,v V均均相互相互可达可达,则称则称G为强连通图为强连通图.(2)单向连通图单向连通图Def设设G=(V,E)是有向图是有向图,对于任意对于任意u,v V,从从u可达可达v或者或者从从v可达可达u,则称则称G为为单向连通图.(3)弱连通图弱连通图Def设设G=(V,E)是有向图是有向图,若不考虑边的方向是若不考虑边的方向是一个无向连通图一个无向连通图,则称有向图则称有向图G为弱连通图，简称为弱连通图，简称有向图连通有向图连通.第72页，共91页，编辑于20

42、22年，星期一强强连通图连通图单向单向连通图连通图弱弱连通图连通图.但反过来均不成立但反过来均不成立!第73页，共91页，编辑于2022年，星期一Theorem6-9设设G=(V,E)是是n阶阶(n2)有向图有向图,则则G强连通当且仅当强连通当且仅当G中存在一条回路中存在一条回路,它通过所有它通过所有节点节点.Def设设G=(V,E)是有向图是有向图,G的极大的强连通子的极大的强连通子图称为图称为G的的强连通分支.(i)子图子图;(ii)强连通强连通;(iii)极大极大.第74页，共91页，编辑于2022年，星期一Theorem6-10设设G=(V,E)是有向图是有向图,则则G的任的任意节点都

43、位于且仅位于的一个强连通分支中意节点都位于且仅位于的一个强连通分支中.Hint任意节点任意节点v本身强连通本身强连通.第75页，共91页，编辑于2022年，星期一Def设设G=(V,E)是有向图是有向图,G的极大的单向连通的极大的单向连通子图称为子图称为G的的单向连通分支.无向连通图的节点可以位于不同的单向连通分无向连通图的节点可以位于不同的单向连通分支中支中.Def设设G=(V,E)是有向图是有向图,G的极大的弱连通子的极大的弱连通子图称为图称为G的的弱连通分支.第76页，共91页，编辑于2022年，星期一6.6 图的矩阵表示将一个图画出来是最直观的表示图的方式将一个图画出来是最直观的表示图

44、的方式.为为了便于使用计算机存储和处理图了便于使用计算机存储和处理图,更为了借助更为了借助于完善的矩阵理论于完善的矩阵理论(线性代数知识之一线性代数知识之一!)研究研究图的有关性质图的有关性质,有必要学习图的矩阵表示有必要学习图的矩阵表示.本节简单介绍图的常见的本节简单介绍图的常见的3种矩阵表示及一些种矩阵表示及一些简单结论简单结论,不涉及更多的有关图的矩阵方面的不涉及更多的有关图的矩阵方面的知识知识.第77页，共91页，编辑于2022年，星期一1.图的邻接图的邻接(adjacency)矩阵矩阵第一种图的矩阵表示第一种图的矩阵表示邻接矩阵邻接矩阵,它表示的是它表示的是图中任意两个节点间的邻接关

45、系图中任意两个节点间的邻接关系.Def6-29 G=(V,E),对节点编号对节点编号V=v1,v2,vn.其中其中aij是是vi邻接到邻接到vj的边数的边数,i,j=1,2,n.第78页，共91页，编辑于2022年，星期一第79页，共91页，编辑于2022年，星期一显然显然,无向图的邻接矩阵是对称矩阵无向图的邻接矩阵是对称矩阵.一个图与其邻接矩阵是一一对应的一个图与其邻接矩阵是一一对应的.从一个图从一个图G的邻接矩阵的邻接矩阵A(G)容易得出每个节点的容易得出每个节点的度数度数.以有向图为例以有向图为例,A(G)中第中第i行元素之和为行元素之和为第个第个i节点的出度节点的出度vi,i=1,2,

46、n,第第j列元素之列元素之和为第个和为第个j节点的入度节点的入度,j=1,2,n.第80页，共91页，编辑于2022年，星期一从图的邻接矩阵可以得出从节点从图的邻接矩阵可以得出从节点vi到到vj长度为长度为l(l 1)的路的数目的路的数目.Theorem6-12设设A是图是图G的邻接矩阵的邻接矩阵,则则Al中中(i,j)位置元素为从节点位置元素为从节点vi到到vj长度为长度为l(l 1)的路的的路的数目数目.Proof对对l归纳归纳.l=1,显然显然.Al=Al-1A:第81页，共91页，编辑于2022年，星期一例例6-7第82页，共91页，编辑于2022年，星期一第83页，共91页，编辑于2

47、022年，星期一第84页，共91页，编辑于2022年，星期一2.图的可达图的可达(accessible)矩阵矩阵第二种图的矩阵表示第二种图的矩阵表示可达矩阵可达矩阵,它表示的是图中它表示的是图中任意两个节点间的可达关系任意两个节点间的可达关系.Def G=(V,E),对节点编号对节点编号V=v1,v2,vn.其中其中pij=1,若若vi可达可达vj,否则否则pij=0,i,j=1,2,n.第85页，共91页，编辑于2022年，星期一例例6-7(continue)第86页，共91页，编辑于2022年，星期一容易由图的邻接矩阵得出其可达矩阵容易由图的邻接矩阵得出其可达矩阵,一个非一个非常有效的算法

48、是常有效的算法是Warshall算法算法.根据我们的可根据我们的可达矩阵的定义知达矩阵的定义知,中所有主对角线上的元素全中所有主对角线上的元素全为为1,这是由于任意节点可达自身所致这是由于任意节点可达自身所致.更容易从图的可达矩阵得出图的连通性质更容易从图的可达矩阵得出图的连通性质.第87页，共91页，编辑于2022年，星期一3.图的关联图的关联(incidence)矩阵矩阵第三种图的矩阵表示第三种图的矩阵表示关联矩阵关联矩阵,它表示的是图中它表示的是图中节点与边之间的关联关系节点与边之间的关联关系.(1)无向图无向图Def 无向图无向图G=(V,E),对节点编号对节点编号V=v1,v2,vn

49、,对边编号对边编号E=e1,e2,em.其中其中mij是是vi与与ej的关联次数的关联次数,i,j.第88页，共91页，编辑于2022年，星期一第89页，共91页，编辑于2022年，星期一(2)有向图有向图Def 无自环无自环(loop)有向图有向图G=(V,E),对节点对节点编号编号V=v1,v2,vn,对边编号对边编号E=e1,e2,em:例子例子?图与其关联矩阵是一一对应的图与其关联矩阵是一一对应的.第90页，共91页，编辑于2022年，星期一图还有其他矩阵表示图还有其他矩阵表示,如距离矩阵、圈矩阵以如距离矩阵、圈矩阵以及割集矩阵等及割集矩阵等,参考有关文献参考有关文献.前面已经谈到前面已经谈到,有了这些图的矩阵表示有了这些图的矩阵表示,可以用线性代数中的可以用线性代数中的知识知识,特别是矩阵理论对图做更深入的研究特别是矩阵理论对图做更深入的研究,由由于篇幅所限于篇幅所限,本书不涉及这些内容的进一步讨本书不涉及这些内容的进一步讨论论,可参见有关图论文献可参见有关图论文献.第91页，共91页，编辑于2022年，星期一