第6章图论优秀课件.ppt

第第6章图论章图论第1页，本讲稿共91页转化 Euler1736年 图论中讨论的图 问题：是否能从四块陆地中问题：是否能从四块陆地中的任一块开始，通过每座桥的任一块开始，通过每座桥恰好一次再回到起点？恰好一次再回到起点？是否能从任意一个顶点开始，通过每条边恰好一次再回到起点？包含两个要素：对象（陆地）及对象间的二元关系（是否有桥连接）问题一问题一:哥尼斯哥尼斯堡堡七桥问題七桥问題第2页，本讲稿共91页Leonhard Euler(公元1707-1783年)1707年出生在瑞士的巴塞尔城，13岁就进巴塞尔大学读书，师从著名的数学家约翰.伯努利。他从19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。第3页，本讲稿共91页问题二：四色问题四四色色问问题题是是世世界界近近代代三三大大数数学学难难题之一。题之一。四四色色问问题题的的内内容容是是：任任何何一一张张地地图图只只用用四四种种颜颜色色就就能能使使具具有有共共同同边边界界的的国国家着上不同的颜色。家着上不同的颜色。它它的的提提出出来来自自英英国国。1852年年，毕毕业业于于伦伦敦敦大大学学的的弗弗南南西西斯斯格格思思里里发发现现了了一一种种有有趣趣的的现现象象：“看看来来，每每幅幅地地图图都都可可以以用用四四种种颜颜色色着着色色，使使得得有有共共同同边边界界的的国国家家都都被被着着上上不不同同的的颜颜色色。”这这个个现现象象能能不不能能从从数数学学上上加加以以严严格格证明呢？证明呢？第4页，本讲稿共91页进进入入20世世纪纪以以来来，科科学学家家们们对对四四色色猜猜想想的的证证明明基基本本上上是是按按照照肯肯肯肯普普普普的的想想法法在在进进行行。后后来来美美国国数数学学家家富富富富兰兰兰兰克克克克林林林林于于1939年年证证明明了了22国国以以下下的的地地图图都都可可以以用用四四色色着着色色。1950年年，有有人人从从22国国推推进进到到35国国。1960年年，有有人人又又证证明明了了39国国以以下下的的地地图图可可以以只只用用四四种种颜色着色；随后又推进到了颜色着色；随后又推进到了50国。国。1976年年6月月，美美国国伊伊利利诺诺大大学学哈哈哈哈肯肯肯肯与与阿阿阿阿佩佩佩佩尔尔尔尔在在两两台台不不同同的的电电子子计计算算机机上上，用用了了1200个个小小时时，作作了了100亿亿判判断断，终终于于完完成成了了四四色色定定理理的证明，轰动了世界。的证明，轰动了世界。然而，真正数学上的严格证明仍然没有得到！数学家然而，真正数学上的严格证明仍然没有得到！数学家仍为此努力，并由此产生了多个不同的图论分支。仍为此努力，并由此产生了多个不同的图论分支。问题二：四色问题第5页，本讲稿共91页问题三：Hamilton问题 Hamilton问题源于1856年，英国数学家Hamilton设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。反映到图论上就是判断一个给定的图是否存在一条含所有顶点的回路。Hamilton至今尚无有效方法來解決！第6页，本讲稿共91页问题四问题四:校园网络校园网络第7页，本讲稿共91页一直往前走碰壁就回头換条路找沿途要记录下走过的路线问题五问题五:游戏游戏第8页，本讲稿共91页程序调用的图论模型程序调用的图论模型第9页，本讲稿共91页设备更新问题设备更新问题。第i年初1234购置费（万元）2.52.62.83.1使用年限1234每年的维修与运行费（万元）11.524某工厂的某台机器可连续工作4年，决策者每年年初都要决定机器是否需要更新。若购置新的，就要支付一定的购置费用；若继续使用，则要支付一定的维修与运行费用，而且随着机器使用年限的增加费用逐年增多。计划期（4 年）中每年年初的购置价格及各个年限内维修与运行费用由下表给出，试制订今后4年的机器更新计划，使总的支付费用最少。第10页，本讲稿共91页解解：把把该该问问题题看看成成一一个个最最短短路路问问题题。设设v1和和v5分分别别表表示示计计划划期期的的始始点点和和终终点点（x5可可理理解解为为第第4年年年年末末）。图图中中各各边边(vi,vj)表表示示在在第第i 年年初初购购进进的的机机器器使使用用到到第第j 年年初初（即即第第j 1年底），边旁的数字由表中的数据得到。年底），边旁的数字由表中的数据得到。第11页，本讲稿共91页又又如如果果已已知知不不同同役役龄龄机机器器年年末末的的处处理理价价格格如如下下表表所所示示，那那末末在在这这计计划划期期内内机机器器的的最最优优更更新新计计划又会怎样？划又会怎样？年度第1年末第2年末第3年末第4年末机器处理价（万元）2.01.61.31.1第12页，本讲稿共91页 关于第二问，类似于第一问，可转化为求下图中从 v1 到 v5 的最短路问题。按照最短路算法可得最短路 v1,v2,v3,v5，即计划期内机器更新最优计划为第 1 年、第 3 年初各购进一台新机器，4 年总的支付费用为 6.8万元。第13页，本讲稿共91页1.图的定义图的定义图G(graph)主要由2部分组成:(1)节点集合V,其中的元素称为节点.(2)边集合E,其中的元素称为边.通常将图G记为G=(V,E).第14页，本讲稿共91页(a)节点又可以称为点、顶点或结点节点又可以称为点、顶点或结点,常用一个实心点或空心点常用一个实心点或空心点表示表示,但在实际应用中还可以用诸如方形、圆形、菱形等符但在实际应用中还可以用诸如方形、圆形、菱形等符号号.(b)边及其的表示边及其的表示.无向边?b3=AB=BA=A,B(可重).有向边(弧)?几点说明:所有边都是无向边的图称为无向图；所有边都是无向边的图称为无向图；所有边都是有向边的图称为有向图所有边都是有向边的图称为有向图.第15页，本讲稿共91页(c)图的拓扑不变性质图的拓扑不变性质.需要注意的是需要注意的是,我们讨论我们讨论的图不但与节点位置无关的图不但与节点位置无关,而且与边的形状和而且与边的形状和长短也无关长短也无关.有n个节点的图称为n阶图,有n个节点m条边的图称为(n,m)图.在图G=(V,E)中,称V=的图为空图,记为.几点说明:第16页，本讲稿共91页若 V 但E=的图称为零图,n阶零图可记为Nn.仅一个节点的零图称为平凡图.第17页，本讲稿共91页定义：设G=(V,E)是图,对于任意u,v V,若从节点u到节点v有边,则称u邻接到v或称u和v是邻接的.2.邻接无向图?有向图?第18页，本讲稿共91页(无向图的两条边邻接是指它们有公共端点.)(平面图的面相邻?)第19页，本讲稿共91页3.关联定义：设G=(V,E)是图,e E,e的两个端点分别为u和v,则称边e与节点u以及边e与节点v是关联的.图的任意一条边都关联两个节点.关联相同两个节点的边称为吊环,可简称环.关联的起点相同与终点也相同的边称为多重边或平行边,其边数称为边的重数.第20页，本讲稿共91页4.简单图(1)简单图定义：设G=(V,E)是图,若G中既无吊环又无多重边,则称G是简单图.彼得森(Petersen,18311910)图,是一种妖怪图.第21页，本讲稿共91页第22页，本讲稿共91页妖怪图妖怪图?Petersen图称为图称为单星妖怪单星妖怪.下面的图称为下面的图称为双星双星妖怪妖怪.第23页，本讲稿共91页(2)完全无向图完全无向图Def设设G=(V,E)是是n阶简单无向图阶简单无向图,若若G中任中任意节点都与其余意节点都与其余n-1个节点邻接个节点邻接,则称则称G为为n阶阶完全无向图，记为，记为Kn.K5:第24页，本讲稿共91页将将n阶完全无向图阶完全无向图Kn的边任意加一个方向所得到的的边任意加一个方向所得到的有向图称为有向图称为n阶阶竞赛图竞赛图.设设G=(V,E)是是n阶简单有向图阶简单有向图,若若G中任意节点都与中任意节点都与其余其余n-1个节点邻接个节点邻接,则称则称G为为n阶阶完全有向图。完全有向图。第25页，本讲稿共91页(3)补图补图Def设设G=(V,E)是是n阶简单无向图阶简单无向图,由由G的所有的所有节点以及由能使节点以及由能使G成为成为Kn需要添加的边构成的需要添加的边构成的图称为图称为G的的补图,记为记为(u和和v在在G中不邻接中不邻接u和和v在在中邻接中邻接)第26页，本讲稿共91页6.2 节点的度数“七桥七桥”中从一个地方出发的桥的数目就是对中从一个地方出发的桥的数目就是对应节点的度数应节点的度数.边与节点的边与节点的关联次数关联次数?第27页，本讲稿共91页Def设设G=(V,E)是无向图是无向图,v V,称与节点称与节点v关联的所有边的关联次数之和为节点关联的所有边的关联次数之和为节点v的的度数(degree),记为记为deg(v).一个环算一个环算2度度?第28页，本讲稿共91页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页图论第一定理图论第一定理,常称为常称为“握手握手(?)定理定理”.Theorem6-1在任何在任何(n,m)图图G=(V,E)中中,其所其所有节点度数之和等于边数有节点度数之和等于边数m的的2倍倍,即即Corollary 在任意图在任意图G=(V,E)中中,度数为奇数的度数为奇数的节点个数必为偶数节点个数必为偶数.Proof第30页，本讲稿共91页由定理及其推论很容易知道由定理及其推论很容易知道,在任何一次聚会在任何一次聚会上上,所有人握手次数之和必为偶数并且握了奇所有人握手次数之和必为偶数并且握了奇数次手的人数必为偶数数次手的人数必为偶数.(环的解释环的解释?)Theorem6-2在任意有向图中在任意有向图中,所有节点的出度所有节点的出度之和等于入度之和之和等于入度之和.在任意图中在任意图中,度数为度数为0的节点称为的节点称为孤立点。度数。度数为为1的节点称为的节点称为悬挂点。第31页，本讲稿共91页例例6-1 6-1 证明证明:对于任意对于任意n(n 2)个人的组里个人的组里,必必有两个人有相同个数的朋友有两个人有相同个数的朋友.Proof将组里的每个人看作节点将组里的每个人看作节点,两个人是朋两个人是朋友当且仅当对应的节点邻接友当且仅当对应的节点邻接,于是得到一个于是得到一个n阶简单无向图阶简单无向图G,进而进而G中每节点的度数可中每节点的度数可能为能为0,1,2,n-1中一个中一个.第32页，本讲稿共91页当当G中无孤立点时中无孤立点时,于是每节点的度数可能为于是每节点的度数可能为1,2,n-1.由于共有由于共有n个节点个节点,于是必有两于是必有两节点度数相同节点度数相同.当当G中有孤立点时中有孤立点时,这时每节点的度数只可能这时每节点的度数只可能为为0,1,2,n-2.同样由于共同样由于共n有个节点有个节点,因因此必有两节点度数相同此必有两节点度数相同.第33页，本讲稿共91页若一个若一个Simple无向图无向图G的每节点度数均为的每节点度数均为k,则则称称G为为k-正则图(k-regulargraph).例例6-2设无向图设无向图G是一个是一个3-正则正则(n,m)图图,且且2n3=m,求求n和和m各是多少各是多少?Hint 根据握手定理有根据握手定理有:第34页，本讲稿共91页Def最大度、最小度；最小出度、最小入度最大度、最小度；最小出度、最小入度任意图任意图G=(V,E):有向图有向图G=(V,E):第35页，本讲稿共91页对于无向图对于无向图G=(V,E),V=v1,v2,vn,称称deg(v1),deg(v2),deg(vn)为的为的度数序列.对于对于有向图有向图,还可以定义其出度序列和入度序列还可以定义其出度序列和入度序列.例例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页6.3 子图、图的运算和图同构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页例子图子图第38页，本讲稿共91页第39页，本讲稿共91页第40页，本讲稿共91页常见的常见的4种产生种产生G=(V,E)的子图的方式如下的子图的方式如下:(1)GW设设W V,则以则以W为节点集合为节点集合,以两端以两端点均属于点均属于W的所有边为边集合构成的子图的所有边为边集合构成的子图,称为称为由W导出的子图(inducedsubgraphbyW),记为记为GW.第41页，本讲稿共91页(2)GW设设W V,导出子图导出子图GVW记记为为GW,是在是在G中去掉所有中去掉所有W中的节点中的节点,同同时也要去掉与时也要去掉与W中节点关联的所有边中节点关联的所有边.通常通常将将Gv记为记为G-v.(3)GF设设F E,则以则以F为边集合为边集合,以以F中边中边的所有端点为节点集合构成的子图的所有端点为节点集合构成的子图,称为称为由F导出的子图(inducedsubgraphbyF),记为记为GF.第42页，本讲稿共91页(4)GF设设F E,则从则从G中去掉中去掉F中的所有中的所有边得到的生成子图记为边得到的生成子图记为GF.第43页，本讲稿共91页简单图简单图G=(V,E)的补图的补图G+U:(与子图无关与子图无关)第44页，本讲稿共91页2.*图的运算图的运算图的运算就是通过一定的操作图的运算就是通过一定的操作,产生产生“新新”的的图图.前面的子图的产生实际上就是图的运算前面的子图的产生实际上就是图的运算,但它们都是在一个图中进行讨论的但它们都是在一个图中进行讨论的.也便于用也便于用代数方法讨论图代数方法讨论图.Def(1)第45页，本讲稿共91页(2)(3)(4)思考 图的每种运算的性质有哪些图的每种运算的性质有哪些?它与集合它与集合的并、交、差、的并、交、差、(补补)及环和及环和(对称差对称差)运算的运算的性质有什么不同性质有什么不同?第46页，本讲稿共91页3.图同构图同构由于图的拓扑性质由于图的拓扑性质,有可能两个表面上看起来不有可能两个表面上看起来不同的图本质上是同一个图同的图本质上是同一个图,这就是图同构的问题这就是图同构的问题.Def设设G1=(V1,E1)和和G2=(V2,E2)是无向图，若存是无向图，若存在一个双射在一个双射:V1V2使得对于任意使得对于任意u,vV1，(u,v)E1当且仅当且当且仅当且(u)(v)E2且边的重数且边的重数相同，则称相同，则称G1与与G2同构，记为同构，记为G1 G2.直观理解直观理解:G1 G2是指其中一个图仅经过下列两是指其中一个图仅经过下列两种变换可以变为另一个图种变换可以变为另一个图:(a)挪动节点的位置；挪动节点的位置；(b)伸缩边的长短伸缩边的长短.第47页，本讲稿共91页无向图无向图:第48页，本讲稿共91页有向图有向图:对于两个有向图同构的判断对于两个有向图同构的判断,特别要特别要注意边的方向的一致性注意边的方向的一致性.思考 给出至少给出至少4个两个图同构的必要条件个两个图同构的必要条件.第49页，本讲稿共91页Ulam猜想猜想?Simplegraphs:第50页，本讲稿共91页6.4 路与回路在图在图G=(V,E)中中,经常考虑从一个节点出发经常考虑从一个节点出发,沿着一些边连续移动到另一个节点的问题沿着一些边连续移动到另一个节点的问题,这这就是路的概念就是路的概念.1.路路(walk,way)Def对于任意图对于任意图G=(V,E)中，称中，称G中节点与中节点与边交替出现的序列为一条路。边交替出现的序列为一条路。第51页，本讲稿共91页路的起点路的起点;终点终点;路的长度路的长度;平凡路平凡路.需要注意的是需要注意的是,有向图中的路须按边的方向走有向图中的路须按边的方向走,有向图中的路可称为有向路有向图中的路可称为有向路.第52页，本讲稿共91页有两种特殊的路有两种特殊的路:一种是节点不重复的路一种是节点不重复的路,称为称为路径.一种是边不重复的路一种是边不重复的路,称为称为轨迹.显然显然,路径是轨迹路径是轨迹,但轨迹不一定是路径但轨迹不一定是路径.说明由于图论应用的广泛性由于图论应用的广泛性,很多概念存在很多概念存在意义上的差别意义上的差别.之所以选择之所以选择“路径路径”,它有捷它有捷径之意；径之意；“轨迹轨迹”强调边不重复强调边不重复,它是它是(可能可能多次多次)走过后留下的痕迹走过后留下的痕迹.第53页，本讲稿共91页在在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)为图为图G的的直径直径，记为，记为diam(G).第54页，本讲稿共91页2.回路回路Def起点与终点相同的起点与终点相同的(长度长度 1)路称为路称为回路回路.边不重复的回路称为边不重复的回路称为简单回路简单回路（闭迹（闭迹).除起点重复一次外除起点重复一次外,别的节点均不重复的简单别的节点均不重复的简单回路称为回路称为圈或环圈或环,第55页，本讲稿共91页显然显然,圈圈简单回路简单回路,但反过来不成立但反过来不成立.有有n个节点的圈称为个节点的圈称为n阶圈阶圈,记为记为Cn.在在n-1阶圈阶圈Cn-1的内部放置一个节点的内部放置一个节点,并使之与并使之与Cn-1的每个节点邻接的每个节点邻接,这样得到的图称为这样得到的图称为n阶轮阶轮图图,记为记为Wn.第56页，本讲稿共91页在在n阶图阶图G=(V,E)中中,若存在从节点若存在从节点v0到到v0一条一条简单简单回路回路,则存在一条从则存在一条从v0到到v0一条长度一条长度 n的的圈圈.第57页，本讲稿共91页采用采用“最长路径法最长路径法”技巧技巧.Theorem在无向图在无向图G=(V,E)中中,若任意若任意v V有有deg(v)2,则则G中存在圈中存在圈.Proof不妨设不妨设G是简单图是简单图.在在G中选取一条最长的路径中选取一条最长的路径L:v0v1vl.第58页，本讲稿共91页6.5 图的连通性图的基本性质之一是其连通性图的基本性质之一是其连通性,它与图中从节它与图中从节点到节点的路密切相关点到节点的路密切相关.为了讨论方便为了讨论方便,先给先给出出Def在任何图在任何图G=(V,E)中中,若从节点若从节点u到到v存存在一条路在一条路,则称则称u可达可达v(accessible).由于节点由于节点v到到v总存在一条长度为总存在一条长度为0的路的路,因此因此任意节点任意节点v可达可达v自身自身.第59页，本讲稿共91页先讨论无向图的连通性先讨论无向图的连通性.1.无向图的连通性无向图的连通性Def6-17设设G=(V,E)是无向图是无向图,对于对于G中任意中任意两个节点两个节点u和和v均可达均可达,则称则称G是是连通图.第60页，本讲稿共91页Def设设G=(V,E)是无向图是无向图,G中极大的连通子中极大的连通子图称为图称为G的的连通分支(connectedcomponent),图图G的连通分支数记为的连通分支数记为w(G).由定义知由定义知,图图G的连通分支满足的连通分支满足3个条件个条件:(1)连连通分支是通分支是G的子图；的子图；(2)该子图本身是连通图；该子图本身是连通图；(3)在该子图中再添加原图的任意边或节点都在该子图中再添加原图的任意边或节点都不连通不连通.第61页，本讲稿共91页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页例例6-6 设设G=(V,E)是是n阶简单无向图阶简单无向图,若若对对于任意的于任意的G中不相邻的节点中不相邻的节点u和和v有有deg(u)+deg(v)n-1,则则G是连通图是连通图.Hint(反证反证)Theorem6-7去掉简单回路上的去掉简单回路上的一条一条边或度为边或度为1的节点的节点,图的连通性不变图的连通性不变.第二种方法:反证法!第63页，本讲稿共91页2.无向连通图的点连通度与边连通度无向连通图的点连通度与边连通度对于无向连通图对于无向连通图,其连通的程度是不同的其连通的程度是不同的,有些有些很很“脆弱脆弱”,有的则相反有的则相反.(1)点割集与点连通度点割集与点连通度(G).Def设设G=(V,E)是是连通连通无向图无向图,W V,(i)GW不连通或是不连通或是1阶图阶图;(ii)删除删除W的任意真子的任意真子集均连通集均连通,则称则称W为为G的点割集的点割集.“割”是分割、分离、分开的意思,恰使得G不连通或是1阶图所要去掉的节点集合称为的点割集.若点割集W=v,则称v为的割点或关节点.第64页，本讲稿共91页点割集点割集:a,b;c,d.(G)=2.边割集边割集:e1,e2,e3.(G)=3.第65页，本讲稿共91页割点割点:A;B.(G)=1.割边割边:e.(G)=1.第66页，本讲稿共91页Def根据定义根据定义,一个连通无向图的点连通度是使得一个连通无向图的点连通度是使得G不连通或为不连通或为1阶图所要删去的最少的节点个数阶图所要删去的最少的节点个数.于是于是,1阶图的点连通度为阶图的点连通度为0,而完全无向图而完全无向图Kn的的点连通度为点连通度为n-1.第67页，本讲稿共91页点连通度为点连通度为2的图的图G称为称为2-连通或连通或重连通图.确定一个无向图是否重连通具有重要的意义确定一个无向图是否重连通具有重要的意义.假定无向图的节点表示电话交换站假定无向图的节点表示电话交换站,边表示电话边表示电话线线,则在点连通度为则在点连通度为2的通讯网络系统中的通讯网络系统中,一个站一个站发生故障系统仍可正常工作发生故障系统仍可正常工作.第68页，本讲稿共91页(2)边割集与边连通度边割集与边连通度(G).Def设设G=(V,E)是连通无向图且是连通无向图且F E,若从若从G中删除中删除F的所有边所得到的子图不连通或是平凡的所有边所得到的子图不连通或是平凡图图,而删除而删除F的任意真子集都连通的任意真子集都连通,则称则称F为为G的的边割集.恰使得恰使得G不连通或是平凡图所要去掉的边的集合不连通或是平凡图所要去掉的边的集合称为称为G的边割集的边割集.若边割集若边割集F=e,则称则称e为的割为的割边或桥边或桥.第69页，本讲稿共91页Def根据定义根据定义,一个连通无向图一个连通无向图G的边连通度是使的边连通度是使得得G不连通或为平凡图所要删去的最少的边的不连通或为平凡图所要删去的最少的边的数目数目.H.Whitney在在1932年给出的关于点连通度、年给出的关于点连通度、边连通度及最小度之间的联系的一个结论边连通度及最小度之间的联系的一个结论.Theorem6-8设设G=(V,E)是连通是连通无向图无向图,则则第70页，本讲稿共91页Proof(1)由于将任意一个节点所关联的边全去由于将任意一个节点所关联的边全去掉后都不连通掉后都不连通,所以有所以有(2)设设F是是G的恰具有的恰具有条边的边割集条边的边割集.考虑删考虑删除除F中中条边条边.删除后不连通删除后不连通,显然显然若删除后连通若删除后连通,则存在桥则存在桥uv=u,v.再删除再删除u或或v,即得知结论成立即得知结论成立.第71页，本讲稿共91页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页强强连通图连通图单向单向连通图连通图弱弱连通图连通图.但反过来均不成立但反过来均不成立!第73页，本讲稿共91页Theorem6-9设设G=(V,E)是是n阶阶(n2)有向图有向图,则则G强连通当且仅当强连通当且仅当G中存在一条回路中存在一条回路,它通它通过所有节点过所有节点.Def设设G=(V,E)是有向图是有向图,G的极大的强连通的极大的强连通子图称为子图称为G的的强连通分支.(i)子图子图;(ii)强连通强连通;(iii)极大极大.第74页，本讲稿共91页Theorem6-10设设G=(V,E)是有向图是有向图,则则G的的任意节点都位于且仅位于的一个强连通分支任意节点都位于且仅位于的一个强连通分支中中.Hint任意节点任意节点v本身强连通本身强连通.第75页，本讲稿共91页Def设设G=(V,E)是有向图是有向图,G的极大的单向连的极大的单向连通子图称为通子图称为G的的单向连通分支.无向连通图的节点可以位于不同的单向连通无向连通图的节点可以位于不同的单向连通分支中分支中.Def 设G=(V,E)是有向图,G的极大的弱连通子图称为G的弱连通分支.第76页，本讲稿共91页6.6 图的矩阵表示将一个图画出来是最直观的表示图的方式将一个图画出来是最直观的表示图的方式.为为了便于使用计算机存储和处理图了便于使用计算机存储和处理图,更为了借助更为了借助于完善的矩阵理论于完善的矩阵理论(线性代数知识之一线性代数知识之一!)研究研究图的有关性质图的有关性质,有必要学习图的矩阵表示有必要学习图的矩阵表示.本节简单介绍图的常见的本节简单介绍图的常见的3种矩阵表示及一些种矩阵表示及一些简单结论简单结论,不涉及更多的有关图的矩阵方面的不涉及更多的有关图的矩阵方面的知识知识.第77页，本讲稿共91页1.图的邻接图的邻接(adjacency)矩阵矩阵第一种图的矩阵表示第一种图的矩阵表示邻接矩阵邻接矩阵,它表示的是它表示的是图中任意两个节点间的邻接关系图中任意两个节点间的邻接关系.Def6-29 G=(V,E),对节点编号对节点编号V=v1,v2,vn.其中其中aij是是vi邻接到邻接到vj的边数的边数,i,j=1,2,n.第78页，本讲稿共91页第79页，本讲稿共91页显然显然,无向图的邻接矩阵是对称矩阵无向图的邻接矩阵是对称矩阵.一个图与其邻接矩阵是一一对应的一个图与其邻接矩阵是一一对应的.从一个图从一个图G的邻接矩阵的邻接矩阵A(G)容易得出每个节点容易得出每个节点的度数的度数.以有向图为例以有向图为例,A(G)中第中第i行元素之行元素之和为第个和为第个i节点的出度节点的出度vi,i=1,2,n,第第j列列元素之和为第个元素之和为第个j节点的入度节点的入度,j=1,2,n.第80页，本讲稿共91页从图的邻接矩阵可以得出从节点从图的邻接矩阵可以得出从节点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页例例6-7第82页，本讲稿共91页第83页，本讲稿共91页第84页，本讲稿共91页2.图的可达图的可达(accessible)矩阵矩阵第二种图的矩阵表示第二种图的矩阵表示可达矩阵可达矩阵,它表示的是它表示的是图中任意两个节点间的可达关系图中任意两个节点间的可达关系.Def G=(V,E),对节点编号对节点编号V=v1,v2,vn.其中其中pij=1,若若vi可达可达vj,否则否则pij=0,i,j=1,2,n.第85页，本讲稿共91页例例6-7(continue)第86页，本讲稿共91页容易由图的邻接矩阵得出其可达矩阵容易由图的邻接矩阵得出其可达矩阵,一个非一个非常有效的算法是常有效的算法是Warshall算法算法.根据我们的可根据我们的可达矩阵的定义知达矩阵的定义知,中所有主对角线上的元素全中所有主对角线上的元素全为为1,这是由于任意节点可达自身所致这是由于任意节点可达自身所致.更容易从图的可达矩阵得出图的连通性质更容易从图的可达矩阵得出图的连通性质.第87页，本讲稿共91页3.图的关联图的关联(incidence)矩阵矩阵第三种图的矩阵表示第三种图的矩阵表示关联矩阵关联矩阵,它表示的是它表示的是图中节点与边之间的关联关系图中节点与边之间的关联关系.(1)无向图无向图Def 无向图无向图G=(V,E),对节点编号对节点编号V=v1,v2,vn,对边编号对边编号E=e1,e2,em.其中其中mij是是vi与与ej的关联次数的关联次数,i,j.第88页，本讲稿共91页第89页，本讲稿共91页(2)有向图有向图Def 无自环无自环(loop)有向图有向图G=(V,E),对节点对节点编号编号V=v1,v2,vn,对边编号对边编号E=e1,e2,em:例子例子?图与其关联矩阵是一一对应的图与其关联矩阵是一一对应的.第90页，本讲稿共91页图还有其他矩阵表示图还有其他矩阵表示,如距离矩阵、圈矩阵以如距离矩阵、圈矩阵以及割集矩阵等及割集矩阵等,参考有关文献参考有关文献.前面已经谈到前面已经谈到,有了这些图的矩阵表示有了这些图的矩阵表示,可以用线性代数中的可以用线性代数中的知识知识,特别是矩阵理论对图做更深入的研究特别是矩阵理论对图做更深入的研究,由于篇幅所限由于篇幅所限,本书不涉及这些内容的进一步本书不涉及这些内容的进一步讨论讨论,可参见有关图论文献可参见有关图论文献.第91页，本讲稿共91页