离散数学第6章-图论课件.ppt

1、1Chapter 6 图论图论n图论是一个古老的数学分支图论是一个古老的数学分支,它以图为研究对象。它以图为研究对象。图论中的图是由若图论中的图是由若 干给定的点及连接两点的线所干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系的线表示相应两个事物间具有这种关系.n图论近年来发展十分迅速图论近年来发展十分迅速,应用相当广泛应用相当广泛,渗透到许渗透到许多学科多学科,诸如运筹学、信息论、控制论、网络理论、诸如运筹学、信息

2、论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语博弈论、化学、生物学、物理学、社会科学、语言学言学,特别是计算机科学等特别是计算机科学等,图论得到广泛的应用图论得到广泛的应用,同时图论本身也得到了充分的发展同时图论本身也得到了充分的发展.234567891011121314151617181920212223242526272829303132333435363738394041 图论最早处理的问题是哥尼斯堡城图论最早处理的问题是哥尼斯堡城PregelPregel河上的河上的七桥问题七桥问题：河中有两个岛屿：河中有两个岛屿,人们架设了七座桥把河人们架设了七座桥把河岸和两个小岛连

3、接起来岸和两个小岛连接起来,有人打算在每座桥上通过一有人打算在每座桥上通过一次然后返回出发点次然后返回出发点,但没有获得成功但没有获得成功.后来有人请教当时的大数学家后来有人请教当时的大数学家欧拉欧拉,欧拉用图论的方法证明这个欧拉用图论的方法证明这个问题无解问题无解,同时他提出并解决了更同时他提出并解决了更为一般的问题为一般的问题,从而奠定了图论的从而奠定了图论的基础基础,欧拉也被誉为欧拉也被誉为“图论之父图论之父”.”.ABCD42 后来后来,英国数学家哈密尔顿在英国数学家哈密尔顿在18561856年提出年提出“周游世界周游世界”的的问题：一个正十二面体问题：一个正十二面体,20,20个顶点

4、分别表示世界上个顶点分别表示世界上2020个大城市个大城市,要求从某个城市出发要求从某个城市出发,经过所有城市一次而不重复经过所有城市一次而不重复,最后回到出最后回到出发地发地.这也是图论中一个著名的问题这也是图论中一个著名的问题.“四色问题四色问题”也是图论中的著名问题：地图着色时也是图论中的著名问题：地图着色时,国境国境线相邻的国家需要着上不同的颜色线相邻的国家需要着上不同的颜色,最少需要几种颜色？最少需要几种颜色？19761976年年,美国人阿佩尔和哈肯用计算机运行美国人阿佩尔和哈肯用计算机运行12001200个小时个小时,证明证明4 4种颜种颜色就够了色就够了.但至今尚有争议但至今尚有

5、争议.436.1 图的基本概念图的基本概念n哥尼斯堡哥尼斯堡(Kningsberg)七桥问题七桥问题:n问题是问题是:是否可从某一个地方出发，经过七座桥，是否可从某一个地方出发，经过七座桥，每座桥只经过一次，然后又回到原出发点每座桥只经过一次，然后又回到原出发点.ABCDABCD44n程序调用的图论模型程序调用的图论模型:ne8:v3可调用可调用v2;e1:v2可调用可调用v1;e4:v5可调用可调用v5自身自身.1v2v3v4v5v1e2e3e4e5e6e7e8e9e451.图的定义图的定义n定义定义 图图G主要由主要由2部分组成部分组成:q(1)节点集合节点集合V,其中的元素称为其中的元素

6、称为节点节点q(2)边集合边集合E,其中的元素称为其中的元素称为边边n通常将图通常将图G记为记为G=(V,E).46 几点说明几点说明:q(a)节点又可以称为点、顶点或结点节点又可以称为点、顶点或结点,常用一个实心点或空心常用一个实心点或空心点表示点表示,为了方便可以在这些符号的旁边或内部写上表意名为了方便可以在这些符号的旁边或内部写上表意名称称.q(b)边及其表示边及其表示.n无向边无向边?b3=AB=BA=A,B(可重可重).n有向边有向边(弧弧)?n所有边都是无向边的图称为所有边都是无向边的图称为无向图无向图,所有边都是有向边的图称所有边都是有向边的图称为为有向图有向图.82323(,)

7、,.ev vv vABv2v3b3e8A和和B称为端点称为端点4747q(c)我们讨论的图不但与节点位置无关我们讨论的图不但与节点位置无关,而且与边的形状和长而且与边的形状和长短也无关短也无关.n有有n个节点的图称为个节点的图称为n阶阶图图,有有n个节点个节点m条边的图称为条边的图称为(n,m)图图.n在图在图G=(V,E)中中,称称V=的图为的图为空图空图,记为记为,若若 V 但但 E=的图称为的图称为零图零图,n 阶零图可记为阶零图可记为Nn,仅一个节点的零图称为仅一个节点的零图称为平凡图平凡图.482.邻接邻接n定义定义 设设G=(V,E)是图是图,对于任意对于任意u,v V,若从节若从

8、节点点 u 到节点到节点 v 有边有边,则称则称 u 邻接到邻接到 v 或称或称 u 和和 v 是是邻接的邻接的.n无向图无向图?n有向图有向图?n无向图的无向图的两条边邻接两条边邻接是指它们有公共端点是指它们有公共端点.euvuveeuv先驱元素先驱元素后继元素后继元素493.关联关联n定义定义 设设G=(V,E)是图是图,e E,e的两个端点分别为的两个端点分别为u和和v,则称边则称边e与节点与节点u以及边以及边e与节点与节点v是是关联关联的的.n显然显然,图的任意一条边都关联两个节点图的任意一条边都关联两个节点.n关联相同两个节点的边称为吊环关联相同两个节点的边称为吊环,可简称可简称环环

9、(loop).n关联的起点与终点都相同的边称为关联的起点与终点都相同的边称为多重边多重边或平行或平行边边,其边数称为边的其边数称为边的重数重数.u uvuv504.简单图简单图n(1)简单图简单图n定义定义 设设G=(V,E)是图是图,若若G中既无吊环又无多重中既无吊环又无多重边边,则称则称G是是简单图简单图.San FranciscoDenverLos AngelesNew YorkChicagoWashingtonDetroit51n(2)完全无向图完全无向图n定义定义 设设G=(V,E)是是n阶简单无向图阶简单无向图,若若G中任意中任意节点都与其余节点都与其余n-1个节点邻接个节点邻接,

10、则称则称G为为n阶阶完全完全无向图无向图,记为记为Kn.(1)|()|.2nn nE K K1K4K3K2K552n(3)补图补图n定义定义 设设G=(V,E)是是n阶简单无向图阶简单无向图,由由G的所有节的所有节点以及由能使点以及由能使G成为成为Kn需要添加的边构成的图称需要添加的边构成的图称为为G的的补图补图,记为记为n(u和和v在在G中不邻接中不邻接 u和和v在在 中邻接中邻接).GG5353n作业作业 P162 习题习题6.1 9546.2 节点的度数节点的度数n边与节点的边与节点的关联次数关联次数n定义定义 设设G=(V,E)是无向图是无向图,v V,称与节点称与节点v关联关联的所有

11、边的关联次数之和为节点的所有边的关联次数之和为节点 v 的的度数度数,记为记为deg(v).n在任意图中在任意图中,度数为度数为0的节点称为的节点称为孤立点孤立点,度数为度数为1的节点称为的节点称为悬挂点悬挂点.q一个环算一个环算2度度55deg(a)=2deg(b)=6deg(c)=4deg(d)=1deg(e)=0deg(f)=3deg(g)=4 a b g e c d f所有节点度数之和所有节点度数之和=2+4+3+4+6+1+0=20边数边数=10e为孤立点为孤立点.d为悬挂点为悬挂点.56n握手定理握手定理 在任何在任何(n,m)图图G=(V,E)中中,其所有节其所有节点度数之和等于

12、边数点度数之和等于边数m的的2倍倍,即即nCorollary 在任意图在任意图G=(V,E)中中,度数为奇数的节度数为奇数的节点个数必为偶数点个数必为偶数.nProof deg()2.v Vvm ，21 )deg()deg()deg(2eVvVuVvvuv偶数偶数偶数偶数偶数偶数是是奇奇数数度度数数节节点点集集合合是是偶偶数数度度数数节节点点集集合合，21 VV57n定义定义 设设G=(V,E)是有向图是有向图,v V,n以以v为起点的边的数目为节点的为起点的边的数目为节点的出度出度,记为记为deg+(v),n以以v为终点的边的数目为节点的为终点的边的数目为节点的入度入度,记为记为deg-(v

13、),ndeg+(v)+deg-(v)为节点为节点v的的度数度数,记为记为deg(v).q一个环算一个环算2度度58a c b e d fdeg(a)=2deg(b)=2deg(c)=3deg(d)=2deg(e)=3deg(f)=0Total=12deg+(a)=4deg+(b)=1deg+(c)=2deg+(d)=2deg+(e)=3deg+(f)=0Total=12边数边数:12evvVvVv )(deg)(degnTheorem 在任意有向图中在任意有向图中,所有节点的出度之和所有节点的出度之和等于入度之和等于入度之和.59n定义定义 若一个无向图若一个无向图G的每节点度数均为的每节点度

14、数均为k,则称则称G为为k-正则图正则图.n例例n例例 设无向图设无向图G是一个是一个3-正则正则(n,m)图图,且且 2n 3=m,求求 n 和和 m 各是多少各是多少?n解解 根据握手定理有根据握手定理有,3n=2m，n=6，m=9。60n定义定义 对于无向图对于无向图G=(V,E),V=v1,v2,vn,称称deg(v1),deg(v2),deg(vn)为为G的的度数序列度数序列.对于对于有向图有向图,还可以定义其出度序列和入度序列还可以定义其出度序列和入度序列.n例例 是否存在一个无向图是否存在一个无向图G,其度数序列分别为其度数序列分别为q(1)7,5,4,2,2,1.q(2)4,4

15、,3,3,2,2.n解解 q(1)由于序列由于序列7,5,4,2,2,1中中,奇数个数为奇数奇数个数为奇数,根据握手根据握手定理的推论知定理的推论知,不可能存在一个图其度数序列为不可能存在一个图其度数序列为7,5,4,2,2,1.q(2)因为序列因为序列4,4,3,3,2,2中中,奇数个数为偶数奇数个数为偶数,可以得到可以得到一个无向图一个无向图,其度数序列为其度数序列为4,4,3,3,2,2.n作业作业 P165 习题习题6.2 2,7616.3 子图、图的运算和图同构子图、图的运算和图同构1.子图子图n可以通过一个图的子图去考察原图的有关性质以可以通过一个图的子图去考察原图的有关性质以及原

16、图的局部结构及原图的局部结构.n定义定义 设设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)的的生成子图生成子图.62n例例 (一个图的子图较多一个图的子图较多)n常见的常见的4种产生种产生G=(V,E)的子图的方式如下的子图的方式如下:q(1)GW 设设W V,则以则以W为节点集合为节点集合,以两端点均属于以两端点均属于W的所有边为边集合构成的子图的所有边为边集合构成的子图,称为称为由由W导出的子图导出的子图,记为记为GW

17、.q(2)G W 设设W V,导出子图导出子图GV W记为记为G W,是在是在G中去掉所有中去掉所有W中的节点中的节点,同时也要去掉与同时也要去掉与W中节点关联中节点关联的所有边的所有边.通常将通常将G v记为记为G-v.ABe63q(3)GF 设设F E,则以则以F为边集合为边集合,以以F中边的所有端点中边的所有端点为节点集合构成的子图为节点集合构成的子图,称为称为由由F导出的子图导出的子图,记为记为GF.q(4)G F 设设F E,则从则从G中去掉中去掉F中的所有边得到的生中的所有边得到的生成子图记为成子图记为G F.1v2v3v4v5vabcdefg?,cbaG?,cbaG 1v2v3v

18、4v5v?,321vvvG?,321vvvG 2v3v1v4v5v3vabc2v4v1v3vdefg1v2v4v5v642.图的运算图的运算n定义定义 q(1)并并q(2)交交q(3)差差q(4)环和环和111222(,),(,).GV EGVE 12.GG 12.GG 12121(,),.GGV EEEE VV 121221()().GGGGGG V1V2E1E2V1 V2E1 E2V1V2E1 E2653.图同构图同构n由于图的拓扑性质由于图的拓扑性质,有可能两个表面上看起来不同有可能两个表面上看起来不同的图本质上是同一个图的图本质上是同一个图,这就是图同构的问题这就是图同构的问题.n定义

19、：定义：G1=(V1,E1)和和 G2=(V2,E2)，若存在双射若存在双射f：V1V2，使得使得G1 中有中有(a,b)当且仅当当且仅当G2中有中有(f(a),f(b)且重且重数相等数相等,则称则称G1 和和 G2 同构同构.n直观理解直观理解:G1 G2是指其中一个图仅经过下列两是指其中一个图仅经过下列两种变换可以变为另一个图种变换可以变为另一个图:q(a)挪动节点的位置；挪动节点的位置；q(b)伸缩边的长短伸缩边的长短.66 a b c d e a b c d e a b c d e f a b c d e f 66n无向图同构的例子无向图同构的例子:67n分子式为分子式为C4H10的同

20、分异构体：的同分异构体：n分子式为分子式为C2H6O的同分异构体：的同分异构体：CCCHHHHHCHHHHHCCHHCHCHHHHHHH二甲醚COHHHCHHHCHHHCOHHH应用实例应用实例:判断化合物是否结构相同。判断化合物是否结构相同。6768两个图同构的必要条件：两个图同构的必要条件：节点个数相同节点个数相同 边的个数相同边的个数相同 对应节点的度数相同对应节点的度数相同 一个是完全图，另一个也是，等等一个是完全图，另一个也是，等等.破坏这些必要条件中的任何一个，两个图就不会同构。破坏这些必要条件中的任何一个，两个图就不会同构。6869aedcGHbaedcbG和和H是否同构是否同构

21、?6970n有向图有向图:对于两个有向图同构的判断对于两个有向图同构的判断,特别要注意特别要注意边的方向的一致性边的方向的一致性.n作业作业 P168 习题习题6.3 1,5,61G2G3G716.4 路与回路路与回路n1.路路n定义定义 对于任意图对于任意图G=(V,E),n路的起点路的起点;终点终点;路的长度路的长度;n平凡路（一个节点长度为平凡路（一个节点长度为0）.0 1 1 221:.iiillL v e v e vve ve v 1u3452vu145v4323472n需要注意的是需要注意的是,有向图中的路须按边的方向走有向图中的路须按边的方向走,有有向图中的路可称为有向路向图中的

22、路可称为有向路.1v2v3v1e2e3e4e5e1v2v3v4v1e2e3e4e5e6e7e143322233vevevevev3321171vevevev73n定义定义 两种特殊的路两种特殊的路:n一种是节点不重复的路一种是节点不重复的路,称为称为路径路径.n一种是边不重复的路一种是边不重复的路,称为称为轨迹轨迹.nv3e3v2e2v2是一条从是一条从v3到到v2的轨迹的轨迹,但不是路径但不是路径.n显然显然,路径是轨迹路径是轨迹,但轨迹不一定是路径但轨迹不一定是路径.1v2v3v1e2e3e4e5ev3e3v2e2v2v1e5v3e3v274742.回路回路n定义定义 起点与终点相同的起点

23、与终点相同的(长度长度 1 1)路称为路称为回路回路,n除起点重复一次外除起点重复一次外,别的节点均不重复的回路称为别的节点均不重复的回路称为圈或环圈或环,n边不重复的回路称为边不重复的回路称为简单回路简单回路.n长度为长度为0的路不称为回路的路不称为回路.显然显然,节点节点v到到v的边是一的边是一个长度为个长度为1的圈的圈.1u3452v23432u14u75nTheorem 在在n阶图阶图G=(V,E)中中,若存在从节点若存在从节点v0到到vl的一条路的一条路,则必存在一条从则必存在一条从v0到到vl的长度的长度 n-1的的路径路径.nTheorem 在在n阶图阶图G=(V,E)中中,若存

24、在从节点若存在从节点v0到到v0的简单回路的简单回路,则存在一条从则存在一条从v0到到v0的长度的长度 n 的的圈圈.n定义定义qu到到v的的距离距离d(u,v):最短路径的长度最短路径的长度证明证明 如果该路不是路径如果该路不是路径,说明含有回路说明含有回路,删去所有回路删去所有回路(包包括吊环括吊环)即可得到路径即可得到路径.1u3452vd(u,3)=？76n有有n个节点的圈称为个节点的圈称为n阶圈阶圈,记为记为Cn.n在在n-1阶圈阶圈Cn-1的内部放置一个节点的内部放置一个节点,并使之与并使之与Cn-1的每个节点邻接的每个节点邻接,这样得到的图称为这样得到的图称为n阶轮图阶轮图,记为

25、记为Wn.C3C4C5C6W4W5W7W677nTheorem 在无向图在无向图G=(V,E)中中,若任意若任意v V有有deg(v)2,则则G中必存在圈中必存在圈.n证证 不妨设不妨设G是简单图是简单图.在在G中选取一条最长的路径中选取一条最长的路径L:v0v1vl,由于由于L是最长路径是最长路径,与与v0邻接的所有节点必在邻接的所有节点必在L上上.由于由于deg(v0)2,除了除了v1,存在存在vi(2 i l)与与v0邻接邻接,则则v0v1viv0是是G中的一个圈中的一个圈.n作业作业 P170 习题习题6.4 1,4(1)(2).786.5 图的连通性图的连通性n定义定义 在任何图在任

26、何图G=(V,E)中中,若从节点若从节点u到到v存在一存在一条路条路,则称则称u可达可达v.n备注备注 由于节点由于节点v到到v总存在一条长度为总存在一条长度为0的路的路,因因此任意节点此任意节点v可达可达v自身自身.791.无向图的连通性无向图的连通性n定义定义 设设 G=(V,E)是无向图是无向图,对于对于 G 中任意两个中任意两个节点节点 u 和和 v 均可达均可达,则称则称 G 是是连通图连通图.nTheorem 去掉简单回路上的边或度为去掉简单回路上的边或度为1的节点的节点,图的连通性不变图的连通性不变.a b c e a c e f W6d是是abcdef否否cabdegf是是80

27、n定义定义 设设G=(V,E)是无向图是无向图,G中极大的连通子图中极大的连通子图称为称为G的的连通分支连通分支,图图G的连通分支数记为的连通分支数记为w(G).n备注备注 图图G的连通分支满足的连通分支满足3 个条件个条件:q(1)连通分支是连通分支是G的子图；的子图；q(2)该子图本身是连通图；该子图本身是连通图；q(3)在该子图中再添加原图的任意边或节点都不连通在该子图中再添加原图的任意边或节点都不连通.abdcefgh3 个连通分支个连通分支.81nTheorem 设设G=(V,E)是无向图是无向图,则则G是连通图当是连通图当且仅当且仅当w(G)=1.qG是非连通图当且仅当是非连通图当

28、且仅当w(G)2.证证 只只要要证证明明G中中的的任任意意两两个个结结点点 vu,可可达达即即可可.如如果果u,v属属于于G的的同同一一个个分分支支,由于由于G不连通不连通,必必有另一个分支有另一个分支,内有结点内有结点w,则则u,w在在G中不可达中不可达,即在即在G中可达中可达,同同理理,v,w也也在在G中中可可达达,由可达的传递由可达的传递性性,u,v在在G中可达中可达.由由u,v的的任任意意性性可可知知,G连连通通.82例例 设设G是是n阶简单无向图阶简单无向图,如果如果G中每两个结点度数中每两个结点度数之和都不少于之和都不少于)1(n,那么那么G必为连通图必为连通图.证证 假假设设G不

29、不连连通通,则则至至少少有有两两个个连连通通分分支支 ),(111mnG,),(222mnG,各各取取一一个个结结点点vu,则则 与与已已知知条条件件 1)deg()deg(nvu 矛矛盾盾.11)deg()deg(21 nnvu，2221 nnnuv.1deg()1,un2deg()1vn833.有向图的连通性有向图的连通性n有向图的连通性分下述有向图的连通性分下述3种情形分别讨论种情形分别讨论.n定义定义 设设G=(V,E)是有向图是有向图,u,v V 均均相互相互可达可达,则称则称G为为强连通图强连通图.n定义定义 设设G=(V,E)是有向图是有向图,对于任意对于任意u,v V,从从u可

30、达可达v或者或者从从v可达可达u,则称则称G为为单向连通图单向连通图.n定义定义 设设G=(V,E)是有向图是有向图,若不考虑边的方向是一个无向连通图若不考虑边的方向是一个无向连通图,则称有向图则称有向图G为为弱连通图弱连通图,简称有向图简称有向图G连通连通.84n强连通图强连通图 单向单向连通图连通图 弱连通图弱连通图.n但反过来均不成立但反过来均不成立!n特别地，平凡图是强连通图。特别地，平凡图是强连通图。)(a)(b)(c85nTheorem 设设G=(V,E)是有向图是有向图,则则G强连通当且强连通当且仅当仅当G中存在一条回路中存在一条回路,它通过所有节点它通过所有节点.nTheore

31、m 设设G=(V,E)是有向图是有向图,则则G单向连通当单向连通当且仅当且仅当G中存在一条路中存在一条路,它通过所有节点它通过所有节点.n作业作业 P175 习题习题6.5 3.866.6 图的矩阵表示图的矩阵表示n将一个图画出来是最直观的表示图的方式将一个图画出来是最直观的表示图的方式.n学习图的矩阵表示的必要性：学习图的矩阵表示的必要性：便于使用计算机存储和处理图便于使用计算机存储和处理图,借助于完善的矩阵理论借助于完善的矩阵理论(线性代数知识之一线性代数知识之一!)研究研究图的有关性质。图的有关性质。87 图的邻接矩阵图的邻接矩阵n邻接矩阵：表示的是图中任意两个节点间的邻接邻接矩阵：表示

32、的是图中任意两个节点间的邻接关系关系.n定义定义 G=(V,E),对节点编号对节点编号V=v1,v2,vn.其中其中aij是是vi邻接到邻接到vj的边数的边数,i,j=1,2,n.111212122112.().nnnnnnaaaaaaA Gaaa 88a b c d e f abcdefFromToW6dbacefv1,v2行行 列列0 1 0 0 1 11 0 1 0 0 10 1 0 1 0 10 0 1 0 1 11 0 0 1 0 11 1 1 1 1 0890 1 1 0 1 0 1 0 0 0 1 1 0 0 1 0v1v4v3v2v1v4v3v20 2 0 1 2 0 2 1

33、0 2 0 1 1 1 1 1A=A=90n备注备注q无向图的邻接矩阵是对称矩阵无向图的邻接矩阵是对称矩阵.q一个图与其邻接矩阵是一一对应的一个图与其邻接矩阵是一一对应的.q从一个图从一个图G的邻接矩阵的邻接矩阵A(G)容易得出每个节点的度数容易得出每个节点的度数.niaaviinjiji,1,)deg(1niavavnjjiinjiji,1,)(deg,)(deg11G为无向图：为无向图：G为有向图：为有向图：91v1v2v3v4A2=1 2 3 10 0 0 10 0 1 00 0 0 1A3=1 2 4 30 0 1 00 0 0 10 0 1 0(1)v1v1v1v2v3 (2)v1v

34、1v1v2v3(3)v1v2v3v4v3 (4)v1v2v3v4v3(5)v1v1v3v4v3 (6)v1v1v1v1v3 A4=1 2 6 40 0 1 00 0 0 10 0 1 0A=1 2 1 00 0 1 00 0 0 10 0 1 0从从 v1 到到 v3 长度为长度为4 4的路有多少条的路有多少条?例例919292n从图的邻接矩阵可以得出从节点从图的邻接矩阵可以得出从节点vi到到vj长度为长度为l(l 1)的路的数目的路的数目.nTheorem 设设A是图是图G的邻接矩阵的邻接矩阵,则则Al中中(i,j)位置位置元素为从节点元素为从节点vi到到vj长度为长度为l(l 1)的路的数

35、目的路的数目.n证证 对对 l 归纳归纳.l=1,显然显然.nAl=Al-1A:()(1)(1)(1)(1)11221.nlllllijikkjijijinnjkaaaaaaaaa jviv1v2vnv93n例例 如图如图q(1)v2到到v5的长度为的长度为1,2,3,4的路各有多少条的路各有多少条?q(2)G 中长度为中长度为3的路有多少条的路有多少条,其中有多少回路其中有多少回路?q(3)G 是哪类连通图是哪类连通图?0101000001010100000110100A 20000210100000021010002020A 32020002020202000202000004A 40404000004040400000440400A 1v2v3v4v5v路：路：20强连通图强连通图9494n作业作业 P179 习题习题6.6 2,6