第6章图论精选文档.ppt

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

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

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

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

4、能能不不能能从从数数学学上上加加以以严严格格证明呢？证明呢？本讲稿第四页，共九十一页进进入入20世世纪纪以以来来，科科学学家家们们对对四四色色猜猜想想的的证证明明基基本本上上是是按按照照肯肯肯肯普普普普的的想想法法在在进进行行。后后来来美美国国数数学学家家富富富富兰兰兰兰克克克克林林林林于于1939年年证证明明了了22国国以以下下的的地地图图都都可可以以用用四四色色着着色色。1950年年，有有人人从从22国国推推进进到到35国国。1960年年，有有人人又又证证明明了了39国国以以下下的的地地图图可可以以只只用用四四种种颜色着色；随后又推进到了颜色着色；随后又推进到了50国。国。1976年年6月

5、月，美美国国伊伊利利诺诺大大学学哈哈哈哈肯肯肯肯与与阿阿阿阿佩佩佩佩尔尔尔尔在在两两台台不不同同的的电电子子计计算算机机上上，用用了了1200个个小小时时，作作了了100亿亿判判断断，终终于于完完成成了了四四色定理的证明，轰动了世界。色定理的证明，轰动了世界。然而，真正数学上的严格证明仍然没有得到！数学家然而，真正数学上的严格证明仍然没有得到！数学家仍为此努力，并由此产生了多个不同的图论分支。仍为此努力，并由此产生了多个不同的图论分支。问题二：四色问题问题二：四色问题本讲稿第五页，共九十一页问题三：问题三：Hamilton问题问题Hamilton问问题题源源于于1856年年，英英国国数数学学家

6、家Hamilton设设计计了了一一个个名名为为周周游游世世界界的的游游戏戏：他他用用一一个个正正十十二二面面体体的的二二十十个个端端点点表表示示世世界界上上的的二二十十座座大大城城市市（见见图图），提提出出的的问问题题是是要要求求游游戏戏者者找找一一条条沿沿着着十十二二面面体体的的棱棱通通过过每每个个端端点点恰恰好好一一次次的的行行走走路路线线。反反映映到到图图论论上上就是判断一个给定的图是否存在一条含所有顶点的回路。就是判断一个给定的图是否存在一条含所有顶点的回路。Hamilton至今尚无有效方法來解決！至今尚无有效方法來解決！本讲稿第六页，共九十一页问题四问题四:校园网络校园网络本讲稿第七

7、页，共九十一页一直往前走一直往前走碰壁就回碰壁就回头头換条路找換条路找沿途要沿途要记录记录下走过的下走过的路线路线问题五问题五:游戏游戏本讲稿第八页，共九十一页程序调用的图论模型程序调用的图论模型本讲稿第九页，共九十一页设备更新问题设备更新问题。第i年初1234购置费（万元）2.52.62.83.1使用年限1234每年的维修与运行费（万元）11.524某工厂的某台机器可连续工作某工厂的某台机器可连续工作4年，决策者每年年初都要年，决策者每年年初都要决定机器是否需要更新。若购置新的，就要支付一定的购决定机器是否需要更新。若购置新的，就要支付一定的购置费用；若继续使用，则要支付一定的维修与运行费用

8、，置费用；若继续使用，则要支付一定的维修与运行费用，而且随着机器使用年限的增加费用逐年增多。计划期（而且随着机器使用年限的增加费用逐年增多。计划期（4 年）中每年年初的购置价格及各个年限内维修与运行费用年）中每年年初的购置价格及各个年限内维修与运行费用由下表给出，试制订今后由下表给出，试制订今后4年的机器更新计划，使总的支年的机器更新计划，使总的支付费用最少。付费用最少。本讲稿第十页，共九十一页解解：把把该该问问题题看看成成一一个个最最短短路路问问题题。设设v1和和v5分分别别表表示示计计划划期期的的始始点点和和终终点点（x5可可理理解解为为第第4年年年年末末）。图图中中各各边边(vi,vj)

9、表表示示在在第第i 年年初初购购进进的的机机器器使使用用到到第第j 年年初初（即即第第j 1年年底），边旁的数字由表中的数据得到。底），边旁的数字由表中的数据得到。本讲稿第十一页，共九十一页又又如如果果已已知知不不同同役役龄龄机机器器年年末末的的处处理理价价格格如如下下表表所所示示，那那末末在在这这计计划划期期内内机机器器的的最最优优更更新新计计划又会怎样？划又会怎样？年度第1年末第2年末第3年末第4年末机器处理价（万元）2.01.61.31.1本讲稿第十二页，共九十一页 关于第二问，类似于第一问，可转化为求下图中从 v1 到 v5 的最短路问题。按照最短路算法可得最短路 v1,v2,v3,v

10、5，即计划期内机器更新最优计划为第 1 年、第 3 年初各购进一台新机器，4 年总的支付费用为 6.8万元。本讲稿第十三页，共九十一页1.图的定义图的定义图G(graph)主要由主要由2部分组成部分组成:(1)节点集合节点集合V,其中的元素称为其中的元素称为节点.(2)边集合边集合E,其中的元素称为其中的元素称为边.通常将图通常将图G记为记为G=(V,E).本讲稿第十四页，共九十一页(a)节点又可以称为点、顶点或结点节点又可以称为点、顶点或结点,常用一个实心点或空心点表常用一个实心点或空心点表示示,但在实际应用中还可以用诸如方形、圆形、菱形等符号但在实际应用中还可以用诸如方形、圆形、菱形等符号

11、.(b)边及其的表示边及其的表示.无向边?b3=AB=BA=A,B(可重).有向边(弧)?几点说明几点说明:所有边都是无向边的图称为无向图；所有边都是无向边的图称为无向图；所有边都是有向边的图称为有向图所有边都是有向边的图称为有向图.本讲稿第十五页，共九十一页(c)图的拓扑不变性质图的拓扑不变性质.需要注意的是需要注意的是,我们讨论的我们讨论的图不但与节点位置无关图不但与节点位置无关,而且与边的形状和长短而且与边的形状和长短也无关也无关.有有n个节点的图称为个节点的图称为n阶图阶图,有有n个节点个节点m条边的图称条边的图称为为(n,m)图图.在图在图G=(V,E)中中,称称V=的图为空图的图为

12、空图,记为记为.几点说明几点说明:本讲稿第十六页，共九十一页若若V 但但E=的图称为的图称为零图,n阶零图可记为阶零图可记为Nn.仅一个节点的零图称为平凡图仅一个节点的零图称为平凡图.本讲稿第十七页，共九十一页定义：设定义：设G=(V,E)是图是图,对于任意对于任意u,v V,若从节若从节点点u到节点到节点v有边有边,则称则称u邻接到v或称或称u和和v是邻接的是邻接的.2.邻接邻接无向图无向图?有向图有向图?本讲稿第十八页，共九十一页(无向图的两条边邻接是指它们有公共端点无向图的两条边邻接是指它们有公共端点.)(平面图的面相邻平面图的面相邻?)本讲稿第十九页，共九十一页3.关联关联定义：定义：

13、设设G=(V,E)是图是图,e E,e的两个端点分别的两个端点分别为为u和和v,则称边则称边e与节点与节点u以及边以及边e与节点与节点v是关联的是关联的.图的任意一条边都关联两个节点图的任意一条边都关联两个节点.关联相同两个节关联相同两个节点的边称为吊环点的边称为吊环,可简称环可简称环.关联的起点相同与终点关联的起点相同与终点也相同的边称为多重边或平行边也相同的边称为多重边或平行边,其边数称为边的重其边数称为边的重数数.本讲稿第二十页，共九十一页4.简单图简单图(1)简单图简单图定义：定义：设设G=(V,E)是图是图,若若G中既无吊环又无多中既无吊环又无多重边重边,则称则称G是是简单图.彼得森

14、彼得森(Petersen,18311910)图图,是一种妖怪图是一种妖怪图.本讲稿第二十一页，共九十一页本讲稿第二十二页，共九十一页妖怪图妖怪图?Petersen图称为图称为单星妖怪单星妖怪.下面的图称为下面的图称为双星妖怪双星妖怪.本讲稿第二十三页，共九十一页(2)完全无向图完全无向图Def设设G=(V,E)是是n阶简单无向图阶简单无向图,若若G中任意节中任意节点都与其余点都与其余n-1个节点邻接个节点邻接,则称则称G为为n阶阶完全无向图，记为，记为Kn.K5:本讲稿第二十四页，共九十一页将将n阶完全无向图阶完全无向图Kn的边任意加一个方向所得到的有向图的边任意加一个方向所得到的有向图称为称

15、为n阶阶竞赛图.设设G=(V,E)是是n阶简单有向图阶简单有向图,若若G中任意节点都与其中任意节点都与其余余n-1个节点邻接个节点邻接,则称则称G为为n阶阶完全有向图。本讲稿第二十五页，共九十一页(3)补图补图Def设设G=(V,E)是是n阶简单无向图阶简单无向图,由由G的所有节的所有节点以及由能使点以及由能使G成为成为Kn需要添加的边构成的图称需要添加的边构成的图称为为G的的补图,记为记为(u和和v在在G中不邻接中不邻接u和和v在在中邻接中邻接)本讲稿第二十六页，共九十一页6.2 节点的度数“七桥七桥”中从一个地方出发的桥的数目就是对中从一个地方出发的桥的数目就是对应节点的度数应节点的度数.

16、边与节点的边与节点的关联次数关联次数?本讲稿第二十七页，共九十一页Def设设G=(V,E)是无向图是无向图,v V,称与节点称与节点v关联的所有边的关联次数之和为节点关联的所有边的关联次数之和为节点v的的度数(degree),记为记为deg(v).一个环算一个环算2度度?本讲稿第二十八页，共九十一页Def设设G=(V,E)是有向图是有向图,v V,称以称以v为为起点的起点的边的数目为节点的边的数目为节点的出度(out-degree),记为记为deg+(v),以以v为终点的边的数目为节点的为终点的边的数目为节点的入度(in-degree),记为记为deg-(v),称称deg+(v)+deg-(v

17、)为节点为节点v的的度数,记为记为deg(v).一个环算一个环算2度度?本讲稿第二十九页，共九十一页图论第一定理图论第一定理,常称为常称为“握手握手(?)定理定理”.Theorem6-1在任何在任何(n,m)图图G=(V,E)中中,其所有节其所有节点度数之和等于边数点度数之和等于边数m的的2倍倍,即即Corollary 在任意图在任意图G=(V,E)中中,度数为奇数的节度数为奇数的节点个数必为偶数点个数必为偶数.Proof本讲稿第三十页，共九十一页由定理及其推论很容易知道由定理及其推论很容易知道,在任何一次聚会上在任何一次聚会上,所有人握手次数之和必为偶数并且握了奇数次手所有人握手次数之和必为

18、偶数并且握了奇数次手的人数必为偶数的人数必为偶数.(环的解释环的解释?)Theorem6-2在任意有向图中在任意有向图中,所有节点的出度之和所有节点的出度之和等于入度之和等于入度之和.在任意图中在任意图中,度数为度数为0的节点称为的节点称为孤立点。度数为。度数为1的节点称为的节点称为悬挂点。本讲稿第三十一页，共九十一页例例6-1 6-1 证明证明:对于任意对于任意n(n 2)个人的组里个人的组里,必有两必有两个人有相同个数的朋友个人有相同个数的朋友.Proof将组里的每个人看作节点将组里的每个人看作节点,两个人是朋友当两个人是朋友当且仅当对应的节点邻接且仅当对应的节点邻接,于是得到一个于是得到

19、一个n阶简单阶简单无向图无向图G,进而进而G中每节点的度数可能为中每节点的度数可能为0,1,2,n-1中一个中一个.本讲稿第三十二页，共九十一页当当G中无孤立点时中无孤立点时,于是每节点的度数可能为于是每节点的度数可能为1,2,n-1.由于共有由于共有n个节点个节点,于是必有两节点度数相于是必有两节点度数相同同.当当G中有孤立点时中有孤立点时,这时每节点的度数只可能为这时每节点的度数只可能为0,1,2,n-2.同样由于共同样由于共n有个节点有个节点,因此必有两因此必有两节点度数相同节点度数相同.本讲稿第三十三页，共九十一页若一个若一个Simple无向图无向图G的每节点度数均为的每节点度数均为k

20、,则则称称G为为k-正则图(k-regulargraph).例例6-2设无向图设无向图G是一个是一个3-正则正则(n,m)图图,且且2n3=m,求求n和和m各是多少各是多少?Hint 根据握手定理有根据握手定理有:本讲稿第三十四页，共九十一页Def最大度、最小度；最小出度、最小入度最大度、最小度；最小出度、最小入度任意图任意图G=(V,E):有向图有向图G=(V,E):本讲稿第三十五页，共九十一页对于无向图对于无向图G=(V,E),V=v1,v2,vn,称称deg(v1),deg(v2),deg(vn)为的为的度数序列.对于有对于有向图向图,还可以定义其出度序列和入度序列还可以定义其出度序列和

21、入度序列.例例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.本讲稿第三十六页，共九十一页6.3 子图、图的运算和图同构1.子图子图可以

22、通过一个图的子图去考察原图的有关性可以通过一个图的子图去考察原图的有关性质以及原图的局部结构质以及原图的局部结构.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)的的生成子图.本讲稿第三十七页，共九十一页例例子图子图子图子图本讲稿第三十八页，共九十一页本讲稿第三十九页，共九十一页本讲稿第四十页，共九十一页常见的常见的4种产生种产生G=(V,E)的子图的方式如下的子图的方式如下:(1)GW设设W V,则以则以W为节点集合为

23、节点集合,以两端点以两端点均属于均属于W的所有边为边集合构成的子图的所有边为边集合构成的子图,称为称为由W导出的子图(inducedsubgraphbyW),记为记为GW.本讲稿第四十一页，共九十一页(2)GW设设W V,导出子图导出子图GVW记为记为GW,是在是在G中去掉所有中去掉所有W中的节点中的节点,同时也要同时也要去掉与去掉与W中节点关联的所有边中节点关联的所有边.通常将通常将Gv记为记为G-v.(3)GF设设F E,则以则以F为边集合为边集合,以以F中边的所中边的所有端点为节点集合构成的子图有端点为节点集合构成的子图,称为称为由F导出的子图(inducedsubgraphbyF),记

24、为记为GF.本讲稿第四十二页，共九十一页(4)GF设设F E,则从则从G中去掉中去掉F中的所有边中的所有边得到的生成子图记为得到的生成子图记为GF.本讲稿第四十三页，共九十一页简单图简单图G=(V,E)的补图的补图G+U:(与子图无关与子图无关)本讲稿第四十四页，共九十一页2.*图的运算图的运算图的运算就是通过一定的操作图的运算就是通过一定的操作,产生产生“新新”的图的图.前前面的子图的产生实际上就是图的运算面的子图的产生实际上就是图的运算,但它们都是在但它们都是在一个图中进行讨论的一个图中进行讨论的.也便于用代数方法讨论图也便于用代数方法讨论图.Def(1)本讲稿第四十五页，共九十一页(2)

25、(3)(4)思考 图的每种运算的性质有哪些图的每种运算的性质有哪些?它与集合的并、它与集合的并、交、差、交、差、(补补)及环和及环和(对称差对称差)运算的性质有什么运算的性质有什么不同不同?本讲稿第四十六页，共九十一页3.图同构图同构由于图的拓扑性质由于图的拓扑性质,有可能两个表面上看起来不同的图有可能两个表面上看起来不同的图本质上是同一个图本质上是同一个图,这就是图同构的问题这就是图同构的问题.Def设设G1=(V1,E1)和和G2=(V2,E2)是无向图，若存在是无向图，若存在一个双射一个双射:V1V2使得对于任意使得对于任意u,vV1，(u,v)E1当且仅当且当且仅当且(u)(v)E2且

26、边的重数相同，且边的重数相同，则称则称G1与与G2同构，记为同构，记为G1 G2.直观理解直观理解:G1 G2是指其中一个图仅经过下列两种变是指其中一个图仅经过下列两种变换可以变为另一个图换可以变为另一个图:(a)挪动节点的位置；挪动节点的位置；(b)伸缩边的长短伸缩边的长短.本讲稿第四十七页，共九十一页无向图无向图:本讲稿第四十八页，共九十一页有向图有向图:对于两个有向图同构的判断对于两个有向图同构的判断,特别要注特别要注意边的方向的一致性意边的方向的一致性.思考 给出至少给出至少4个两个图同构的必要条件个两个图同构的必要条件.本讲稿第四十九页，共九十一页Ulam猜想猜想?Simplegra

27、phs:本讲稿第五十页，共九十一页6.4 路与回路在图在图G=(V,E)中中,经常考虑从一个节点出发经常考虑从一个节点出发,沿着一些边连续移动到另一个节点的问题沿着一些边连续移动到另一个节点的问题,这这就是路的概念就是路的概念.1.路路(walk,way)Def对于任意图对于任意图G=(V,E)中，称中，称G中节点与中节点与边交替出现的序列为一条路。边交替出现的序列为一条路。本讲稿第五十一页，共九十一页路的起点路的起点;终点终点;路的长度路的长度;平凡路平凡路.需要注意的是需要注意的是,有向图中的路须按边的方向走有向图中的路须按边的方向走,有有向图中的路可称为有向路向图中的路可称为有向路.本讲

28、稿第五十二页，共九十一页有两种特殊的路有两种特殊的路:一种是节点不重复的路一种是节点不重复的路,称为称为路径.一种是边不重复的路一种是边不重复的路,称为称为轨迹.显然显然,路径是轨迹路径是轨迹,但轨迹不一定是路径但轨迹不一定是路径.说明由于图论应用的广泛性由于图论应用的广泛性,很多概念存在意很多概念存在意义上的差别义上的差别.之所以选择之所以选择“路径路径”,它有捷径之它有捷径之意；意；“轨迹轨迹”强调边不重复强调边不重复,它是它是(可能多次可能多次)走走过后留下的痕迹过后留下的痕迹.本讲稿第五十三页，共九十一页在在n阶图阶图G=(V,E)中中,若存在从节点若存在从节点v0到到vl一条路一条路

29、(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)为图为图G的的直径直径，记为，记为diam(G).本讲稿第五十四页，共九十一页2.回路回路Def起点与终点相同的起点与终点相同的(长度长度 1)路称为路称为回路回路.边不重复的回路称为边不重复的回路称为简单回路简单回路（闭迹（闭迹).除起点重复一次外除起点重复一次外,别的节点均不重复的简单回路称

30、别的节点均不重复的简单回路称为为圈或环圈或环,本讲稿第五十五页，共九十一页显然显然,圈圈简单回路简单回路,但反过来不成立但反过来不成立.有有n个节点的圈称为个节点的圈称为n阶圈阶圈,记为记为Cn.在在n-1阶圈阶圈Cn-1的内部放置一个节点的内部放置一个节点,并使之与并使之与Cn-1的每个节点邻接的每个节点邻接,这样得到的图称为这样得到的图称为n阶轮图阶轮图,记为记为Wn.本讲稿第五十六页，共九十一页在在n阶图阶图G=(V,E)中中,若存在从节点若存在从节点v0到到v0一条一条简单简单回路回路,则存在一条从则存在一条从v0到到v0一条长度一条长度 n的的圈圈.本讲稿第五十七页，共九十一页采用采

31、用“最长路径法最长路径法”技巧技巧.Theorem在无向图在无向图G=(V,E)中中,若任意若任意v V有有deg(v)2,则则G中存在圈中存在圈.Proof不妨设不妨设G是简单图是简单图.在在G中选取一条最长的路径中选取一条最长的路径L:v0v1vl.本讲稿第五十八页，共九十一页6.5 图的连通性图的基本性质之一是其连通性图的基本性质之一是其连通性,它与图中从节它与图中从节点到节点的路密切相关点到节点的路密切相关.为了讨论方便为了讨论方便,先给先给出出Def在任何图在任何图G=(V,E)中中,若从节点若从节点u到到v存存在一条路在一条路,则称则称u可达可达v(accessible).由于节点

32、由于节点v到到v总存在一条长度为总存在一条长度为0的路的路,因此因此任意节点任意节点v可达可达v自身自身.本讲稿第五十九页，共九十一页先讨论无向图的连通性先讨论无向图的连通性.1.无向图的连通性无向图的连通性Def6-17设设G=(V,E)是无向图是无向图,对于对于G中任意两中任意两个节点个节点u和和v均可达均可达,则称则称G是是连通图.本讲稿第六十页，共九十一页Def设设G=(V,E)是无向图是无向图,G中极大的连通子图中极大的连通子图称为称为G的的连通分支(connectedcomponent),图图G的连的连通分支数记为通分支数记为w(G).由定义知由定义知,图图G的连通分支满足的连通分

33、支满足3个条件个条件:(1)连通连通分支是分支是G的子图；的子图；(2)该子图本身是连通图；该子图本身是连通图；(3)在该子图中再添加原图的任意边或节点都不连通在该子图中再添加原图的任意边或节点都不连通.本讲稿第六十一页，共九十一页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中邻接中邻接:第一种方法:根据定义证明!本讲稿第六十二页，共九十一页例例6-6 设设G=(V,E)是是n阶简单无向图阶简单无向图

34、,若若对于对于任意的任意的G中不相邻的节点中不相邻的节点u和和v有有deg(u)+deg(v)n-1,则则G是连通图是连通图.Hint(反证反证)Theorem6-7去掉简单回路上的去掉简单回路上的一条一条边或度为边或度为1的节点的节点,图的连通性不变图的连通性不变.第二种方法:反证法!本讲稿第六十三页，共九十一页2.无向连通图的点连通度与边连通度无向连通图的点连通度与边连通度对于无向连通图对于无向连通图,其连通的程度是不同的其连通的程度是不同的,有些很有些很“脆弱脆弱”,有的则相反有的则相反.(1)点割集与点连通度点割集与点连通度(G).Def设设G=(V,E)是是连通连通无向图无向图,W

35、V,(i)GW不连通或是不连通或是1阶图阶图;(ii)删除删除W的任意真子集均连通的任意真子集均连通,则称则称W为为G的点割集的点割集.“割”是分割、分离、分开的意思,恰使得G不连通或是1阶图所要去掉的节点集合称为的点割集.若点割集W=v,则称v为的割点或关节点.本讲稿第六十四页，共九十一页点割集点割集:a,b;c,d.(G)=2.边割集边割集:e1,e2,e3.(G)=3.本讲稿第六十五页，共九十一页割点割点:A;B.(G)=1.割边割边:e.(G)=1.本讲稿第六十六页，共九十一页Def根据定义根据定义,一个连通无向图的点连通度是使得一个连通无向图的点连通度是使得G不连通或为不连通或为1阶

36、图所要删去的最少的节点个数阶图所要删去的最少的节点个数.于是于是,1阶图的点连通度为阶图的点连通度为0,而完全无向图而完全无向图Kn的点连的点连通度为通度为n-1.本讲稿第六十七页，共九十一页点连通度为点连通度为2的图的图G称为称为2-连通或连通或重连通图.确定一个无向图是否重连通具有重要的意义确定一个无向图是否重连通具有重要的意义.假定无假定无向图的节点表示电话交换站向图的节点表示电话交换站,边表示电话线边表示电话线,则在点连则在点连通度为通度为2的通讯网络系统中的通讯网络系统中,一个站发生故障系统仍可一个站发生故障系统仍可正常工作正常工作.本讲稿第六十八页，共九十一页(2)边割集与边连通度

37、边割集与边连通度(G).Def设设G=(V,E)是连通无向图且是连通无向图且F E,若从若从G中中删除删除F的所有边所得到的子图不连通或是平凡图的所有边所得到的子图不连通或是平凡图,而删而删除除F的任意真子集都连通的任意真子集都连通,则称则称F为为G的的边割集.恰使得恰使得G不连通或是平凡图所要去掉的边的集合称为不连通或是平凡图所要去掉的边的集合称为G的边割集的边割集.若边割集若边割集F=e,则称则称e为的割边或桥为的割边或桥.本讲稿第六十九页，共九十一页Def根据定义根据定义,一个连通无向图一个连通无向图G的边连通度是使得的边连通度是使得G不连通或为平凡图所要删去的最少的边的数目不连通或为平

38、凡图所要删去的最少的边的数目.H.Whitney在在1932年给出的关于点连通度、边连通年给出的关于点连通度、边连通度及最小度之间的联系的一个结论度及最小度之间的联系的一个结论.Theorem6-8设设G=(V,E)是连通是连通无向图无向图,则则本讲稿第七十页，共九十一页Proof(1)由于将任意一个节点所关联的边全去掉由于将任意一个节点所关联的边全去掉后都不连通后都不连通,所以有所以有(2)设设F是是G的恰具有的恰具有条边的边割集条边的边割集.考虑删除考虑删除F中中条边条边.删除后不连通删除后不连通,显然显然若删除后连通若删除后连通,则存在桥则存在桥uv=u,v.再删除再删除u或或v,即得知

39、结论成立即得知结论成立.本讲稿第七十一页，共九十一页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为弱连通图，简称有向为弱连通图，简称有向图连通图连通.本讲稿第七十二页，

40、共九十一页强强连通图连通图单向单向连通图连通图弱弱连通图连通图.但反过来均不成立但反过来均不成立!本讲稿第七十三页，共九十一页Theorem6-9设设G=(V,E)是是n阶阶(n2)有向图有向图,则则G强连通当且仅当强连通当且仅当G中存在一条回路中存在一条回路,它通过所有它通过所有节点节点.Def设设G=(V,E)是有向图是有向图,G的极大的强连通子的极大的强连通子图称为图称为G的的强连通分支.(i)子图子图;(ii)强连通强连通;(iii)极大极大.本讲稿第七十四页，共九十一页Theorem6-10设设G=(V,E)是有向图是有向图,则则G的任意的任意节点都位于且仅位于的一个强连通分支中节点

41、都位于且仅位于的一个强连通分支中.Hint任意节点任意节点v本身强连通本身强连通.本讲稿第七十五页，共九十一页Def设设G=(V,E)是有向图是有向图,G的极大的单向连的极大的单向连通子图称为通子图称为G的的单向连通分支.无向连通图的节点可以位于不同的单向连通分支中无向连通图的节点可以位于不同的单向连通分支中.Def设设G=(V,E)是有向图是有向图,G的极大的弱连通子图的极大的弱连通子图称为称为G的的弱连通分支.本讲稿第七十六页，共九十一页6.6 图的矩阵表示将一个图画出来是最直观的表示图的方式将一个图画出来是最直观的表示图的方式.为为了便于使用计算机存储和处理图了便于使用计算机存储和处理图

42、,更为了借助更为了借助于完善的矩阵理论于完善的矩阵理论(线性代数知识之一线性代数知识之一!)研究研究图的有关性质图的有关性质,有必要学习图的矩阵表示有必要学习图的矩阵表示.本节简单介绍图的常见的本节简单介绍图的常见的3种矩阵表示及一些种矩阵表示及一些简单结论简单结论,不涉及更多的有关图的矩阵方面的不涉及更多的有关图的矩阵方面的知识知识.本讲稿第七十七页，共九十一页1.图的邻接图的邻接(adjacency)矩阵矩阵第一种图的矩阵表示第一种图的矩阵表示邻接矩阵邻接矩阵,它表示的是图中它表示的是图中任意两个节点间的邻接关系任意两个节点间的邻接关系.Def6-29 G=(V,E),对节点编号对节点编号

43、V=v1,v2,vn.其中其中aij是是vi邻接到邻接到vj的边数的边数,i,j=1,2,n.本讲稿第七十八页，共九十一页本讲稿第七十九页，共九十一页显然显然,无向图的邻接矩阵是对称矩阵无向图的邻接矩阵是对称矩阵.一个图与其邻接矩阵是一一对应的一个图与其邻接矩阵是一一对应的.从一个图从一个图G的邻接矩阵的邻接矩阵A(G)容易得出每个节点的度容易得出每个节点的度数数.以有向图为例以有向图为例,A(G)中第中第i行元素之和为第行元素之和为第个个i节点的出度节点的出度vi,i=1,2,n,第第j列元素之和列元素之和为第个为第个j节点的入度节点的入度,j=1,2,n.本讲稿第八十页，共九十一页从图的邻

44、接矩阵可以得出从节点从图的邻接矩阵可以得出从节点vi到到vj长度为长度为l(l 1)的路的数目的路的数目.Theorem6-12设设A是图是图G的邻接矩阵的邻接矩阵,则则Al中中(i,j)位置元素为从节点位置元素为从节点vi到到vj长度为长度为l(l 1)的路的的路的数目数目.Proof对对l归纳归纳.l=1,显然显然.Al=Al-1A:本讲稿第八十一页，共九十一页例例6-7本讲稿第八十二页，共九十一页本讲稿第八十三页，共九十一页本讲稿第八十四页，共九十一页2.图的可达图的可达(accessible)矩阵矩阵第二种图的矩阵表示第二种图的矩阵表示可达矩阵可达矩阵,它表示的是图中任它表示的是图中任

45、意两个节点间的可达关系意两个节点间的可达关系.Def G=(V,E),对节点编号对节点编号V=v1,v2,vn.其中其中pij=1,若若vi可达可达vj,否则否则pij=0,i,j=1,2,n.本讲稿第八十五页，共九十一页例例6-7(continue)本讲稿第八十六页，共九十一页容易由图的邻接矩阵得出其可达矩阵容易由图的邻接矩阵得出其可达矩阵,一个非常有效一个非常有效的算法是的算法是Warshall算法算法.根据我们的可达矩阵的定义根据我们的可达矩阵的定义知知,中所有主对角线上的元素全为中所有主对角线上的元素全为1,这是由于任意这是由于任意节点可达自身所致节点可达自身所致.更容易从图的可达矩阵

46、得出图的连通性质更容易从图的可达矩阵得出图的连通性质.本讲稿第八十七页，共九十一页3.图的关联图的关联(incidence)矩阵矩阵第三种图的矩阵表示第三种图的矩阵表示关联矩阵关联矩阵,它表示的是图中它表示的是图中节点与边之间的关联关系节点与边之间的关联关系.(1)无向图无向图Def 无向图无向图G=(V,E),对节点编号对节点编号V=v1,v2,vn,对边编号对边编号E=e1,e2,em.其中其中mij是是vi与与ej的关联次数的关联次数,i,j.本讲稿第八十八页，共九十一页本讲稿第八十九页，共九十一页(2)有向图有向图Def 无自环无自环(loop)有向图有向图G=(V,E),对节点对节点

47、编号编号V=v1,v2,vn,对边编号对边编号E=e1,e2,em:例子例子?图与其关联矩阵是一一对应的图与其关联矩阵是一一对应的.本讲稿第九十页，共九十一页图还有其他矩阵表示图还有其他矩阵表示,如距离矩阵、圈矩阵以及如距离矩阵、圈矩阵以及割集矩阵等割集矩阵等,参考有关文献参考有关文献.前面已经谈到前面已经谈到,有了有了这些图的矩阵表示这些图的矩阵表示,可以用线性代数中的知识可以用线性代数中的知识,特特别是矩阵理论对图做更深入的研究别是矩阵理论对图做更深入的研究,由于篇幅所由于篇幅所限限,本书不涉及这些内容的进一步讨论本书不涉及这些内容的进一步讨论,可参见有可参见有关图论文献关图论文献.本讲稿第九十一页，共九十一页