离散数学课件图论(3).ppt

《离散数学课件图论(3).ppt》由会员分享，可在线阅读，更多相关《离散数学课件图论(3).ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四部分第四部分第四部分第四部分图论图论图论图论 School of Information Science and Engineering图图 论论实例实例1 1：多用户操作系统中的进程状态变换 School of Information Science and Engineering实例实例2：“七桥问题”哥尼斯堡城的普雷格尔河图图 论论ABCDABCDe1e5e7e6e3e4e2V=A,B,C,D E=e1,e2,e3,e4,e5,e6,e7后来欧拉证明这样的路径根本不存在。后来欧拉证明这样的路径根本不存在。School of Information Science and Engine

2、ering图图 论论实例实例3：在机械加工中，经常需要在一块金属薄板上钻若干孔（或者是机械手在印刷电路板上安装电子元件）问如何确定钻孔的次序,使之加工的时间最短？类似的问题：旅行最优问题,工程最优问题,成本最低.School of Information Science and Engineering第十四章第十四章 图的基本概念图的基本概念v主要内容主要内容图通路与回路图的连通性图的矩阵表示 School of Information Science and Engineering14-1 14-1 图图定义定义一个图表示为一个图表示为 G=,其中其中 V(G):G的结点的非空集合，简记成的

3、结点的非空集合，简记成V。E(G):是是G的边的集合，的边的集合，有时简记成有时简记成E。v结点结点(Vertices)：用用 表示表示,旁边标上该结点的名称。旁边标上该结点的名称。v边边(Edges)有向边有向边:带箭头的弧线。带箭头的弧线。从从u到到v的边的边表示成表示成 无向边无向边:不带箭头的弧线。不带箭头的弧线。u和和v间的边间的边表示成表示成(u,v)School of Information Science and Engineering14-1 14-1 图图实例实例 1.设设 V1=v1,v2,v5,E1=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2

4、,v5),(v1,v5),(v4,v5)则则 G1=为一无向图为一无向图2.设设 V2=a,b,c,d,E2=,则则 G2=为一有向图为一有向图 School of Information Science and Engineering14-1 14-1 图图相关概念相关概念：1.图图 可用可用G泛指图（无向的泛指图（无向的G或有向的或有向的D）V(G),E(G),V(D),E(D)n阶图阶图2.n 阶零图与平凡图（阶零图与平凡图（n 为顶点个数）为顶点个数）3.用用 ek 表示无向边或有向边表示无向边或有向边4.顶点与边的关联关系顶点与边的关联关系 关联、关联次数关联、关联次数 环环 孤立点

5、孤立点5.顶点之间的相邻与邻接关系顶点之间的相邻与邻接关系 School of Information Science and Engineering14-1 14-1 图图6.邻域与关联集邻域与关联集 v V(G)(G为无向图为无向图)v 的关联集的关联集 v V(D)(D为有向图为有向图)7.标定图与非标定图标定图与非标定图8.基图基图 School of Information Science and Engineering14-1 14-1 图图v多重图与简单图多重图与简单图 简单图简单图：不含有环和平行边的图。：不含有环和平行边的图。多重图多重图：含有平行边的图。：含有平行边的图。S

6、chool of Information Science and Engineering14-1 14-1 图图定定义义 (1)设设G=为无向图为无向图,v V,d(v)v的度数的度数,简称度简称度 (2)设设D=为有向图为有向图,v V,d+(v)v的出度的出度 d(v)v的入度的入度 d(v)v的度或度数的度或度数 (3)(G),(G)(4)+(D),+(D),(D),(D),(D),(D)(5)奇度顶点与偶度顶点奇度顶点与偶度顶点 School of Information Science and Engineering14-1 14-1 图图握手定理握手定理 定理定理14-1.1 设设

7、G=为为任意无向任意无向图图，V=v1,v2,vn,|E|=m,则则证明：证明：G中每条边中每条边(包括环包括环)均有两个端点，所以在计算均有两个端点，所以在计算G中各中各顶点度数之和时，每条边均提供顶点度数之和时，每条边均提供2度，度，m 条边共提供条边共提供 2m 度。度。定理定理14-1.2 设设D=为为任意有向任意有向图图，V=v1,v2,vn,|E|=m,则则推推论论 任何任何图图(无向或有向无向或有向)中，奇度中，奇度顶顶点的个数是偶数。点的个数是偶数。School of Information Science and Engineering14-1 14-1 图图无向图的结点度序

8、列无向图的结点度序列 V=v1,v2,vn为无向图为无向图G的顶点集，称的顶点集，称d(v1),d(v2),d(vn)为为G的的度数序列度数序列。非负整数列非负整数列d=(d1,d2,dn)是是可图化可图化的，是的，是可简单图化可简单图化的。的。n阶阶k正则图正则图 一个无向简单图一个无向简单图G中中,如果如果(G)=(G)=k，则称，则称G为为k-正则图正则图。Kn是是 n 1正则图正则图 School of Information Science and Engineering14-1 14-1 图图练习练习:1.下面哪些数的序列下面哪些数的序列，可能是一个图度数序列可能是一个图度数序列?

9、如果如果是，是，试画试画出它的图出它的图。哪些是哪些是可可简单图简单图化的化的?a)(1,2,3,4,5)b)(2,2,2,2,2)c)(1,2,3,2,4)2.已知无向简单图已知无向简单图G中中,有有10条边条边，4个个3度结点度结点,其余结点的度其余结点的度均小于或等于均小于或等于2，问问G中至少有多少个结点中至少有多少个结点？为什么为什么？School of Information Science and Engineering14-1 14-1 图图图的同构图的同构 设设G1=,G2=为两个无向图为两个无向图(两个有两个有向向图图)，若存在双射函数，若存在双射函数f:V1V2,对于对于

10、vi,vj V1,(vi,vj)E1 当且仅当当且仅当(f(vi),f(vj)E2 （E1 当且仅当当且仅当 E2)并且并且,(vi,vj)（）与）与(f(vi),f(vj)（）的重数相）的重数相同，则称同，则称G1与与G2是是同构同构的，记作的，记作G1 G2。v图之间的同构关系具有自反性、对称性和传递性图之间的同构关系具有自反性、对称性和传递性v能找到同构的必要条件，但它们全不是充分条件：能找到同构的必要条件，但它们全不是充分条件：边数相同，顶点数相同边数相同，顶点数相同;度数序列相同度数序列相同;对应顶点的关联集及邻域的元素个数相同，等等对应顶点的关联集及邻域的元素个数相同，等等v若破坏

11、必要条件，则两图不同构若破坏必要条件，则两图不同构v判断两个图同构是个难题判断两个图同构是个难题 School of Information Science and Engineering14-1 14-1 图图图同构实例图同构实例 (1)(2)(3)(4)图中，图中，(1)(1)与与(2)(2)不同构（度数列不同），不同构（度数列不同），(3)(3)与与(4)(4)也不同构也不同构.(1)(2)问：问：图中图中(1)(1)与与(2)(2)的度数序列相同，的度数序列相同，它们同构吗？为什它们同构吗？为什么？么？School of Information Science and Engineer

12、ing14-1 14-1 图图完全图完全图无向完全图无向完全图G是个简单图是个简单图，如果每对不同如果每对不同顶点顶点都都相邻，相邻，则则称称G是个无向完全图。如果是个无向完全图。如果G有有n个结点个结点,则记作则记作Kn。简单性质：简单性质：边数边数有向完全图有向完全图G是个有向简单图，如果任意两个不同顶点之是个有向简单图，如果任意两个不同顶点之间都有方向相反的边间都有方向相反的边,则称它是有向完全图。则称它是有向完全图。简单性质：边数简单性质：边数竞赛图竞赛图基图为基图为Kn的有向简单图。的有向简单图。School of Information Science and Engineerin

13、g14-1 14-1 图图子图子图定义：定义：G=,G=(1)GG G 为为G的的子图子图，G为为G 的的母图母图(2)若若GG且且V=V，则称，则称G 为为G的的生成子图生成子图(3)若若VV或或EE，称，称G 为为G的的真子图真子图(4)V（VV且且V）的）的导出子图导出子图，记作，记作GV(5)E（EE且且E）的）的导出子图导出子图，记作，记作GE School of Information Science and Engineering14-1 14-1 图图例例 画出画出K4的所有非同构的生成子图。的所有非同构的生成子图。School of Information Science a

14、nd Engineering14-1 14-1 图图补图补图定义：定义：设设G=为为n阶无向简单图，以阶无向简单图，以V为顶点集，以所有使为顶点集，以所有使G成为完全图成为完全图Kn的添加边组成的集合为边集的图，称为的添加边组成的集合为边集的图，称为G的的补图补图，记作，记作 。若若G ,则称则称G是是自补图自补图。相对于相对于K4,求上面图中所有图的补图，并指出哪些是自补图。求上面图中所有图的补图，并指出哪些是自补图。问：互为自补图的两个图的边数有何关系？问：互为自补图的两个图的边数有何关系？School of Information Science and Engineering14-2

15、14-2 通路与回路通路与回路定义定义 给定图给定图G=（无向或有向的），（无向或有向的），G中中顶点与顶点与边的交替序列边的交替序列 =v0e1v1e2elvl，vi 1,vi 是是 ei 的端点。的端点。(1)通路与回路：通路与回路：为为通路通路；若；若 v0=vl，为为回路回路，l 为为回路长回路长 度度。(2)简单通路与回路：所有边各异，简单通路与回路：所有边各异，为为简单通路简单通路，又若，又若v0=vl，为为简单回路。简单回路。(3)初级通路初级通路(路径路径)与初级回路与初级回路(圈圈)：中所有顶点各异，则中所有顶点各异，则称称 为为初级通路初级通路(路径路径)，又若除，又若除v

16、0=vl，所有的顶点各不相，所有的顶点各不相同且所有的边各异，则称同且所有的边各异，则称 为为初级回路初级回路(圈圈)。(4)复杂通路与回路：有边重复出现。复杂通路与回路：有边重复出现。School of Information Science and Engineering14-2 14-2 通路与回路通路与回路表示法表示法 定义表示法定义表示法 只用边表示法只用边表示法 只用顶点表示法（在简单图中）只用顶点表示法（在简单图中）混合表示法混合表示法环环（长为（长为1的圈）的长度为的圈）的长度为1，两条平行边构成的圈长度为，两条平行边构成的圈长度为 2，无向简单图中，圈长，无向简单图中，圈长

17、3，有向简单图中圈的长度，有向简单图中圈的长度 2.不同的圈不同的圈（以长度（以长度 3的为例）的为例）定义意义下定义意义下 无向图：图中长度为无向图：图中长度为l（l 3）的圈，定义意义下为）的圈，定义意义下为2l个个 有向图：图中长度为有向图：图中长度为l（l 3）的圈，定义意义下为）的圈，定义意义下为l个个 同构意义下：长度相同的圈均为同构意义下：长度相同的圈均为1个个 School of Information Science and Engineering14-2 14-2 通路与回路通路与回路定理定理14-2.1 在在n 阶图阶图G中，若从顶点中，若从顶点vi 到到vj（vi vj

18、）存在通路，）存在通路，则从则从vi 到到 vj 存在长度小于或等于存在长度小于或等于n 1 的通路的通路.推论推论 在在 n 阶图阶图G中，若从顶点中，若从顶点vi 到到 vj（vi vj）存在通路，则）存在通路，则从从vi 到到vj 存在长度小于或等于存在长度小于或等于n 1的初级通路（路径）的初级通路（路径）.定理定理14-2.2 在一个在一个n 阶图阶图G中，若存在中，若存在 vi 到自身的回路，则到自身的回路，则一定存在一定存在vi 到自身长度小于或等于到自身长度小于或等于 n 的回路的回路.推论推论 在一个在一个n 阶图阶图G中，若存在中，若存在 vi 到自身的简单回路，则一到自身

19、的简单回路，则一定存在长度小于或等于定存在长度小于或等于n 的初级回路的初级回路.School of Information Science and Engineering14-3 14-3 图的连通性图的连通性1.无向图的连通性无向图的连通性两个结点连通两个结点连通在无向图中，结点在无向图中，结点u和和v之间如果存在一条之间如果存在一条通通路路，则称则称u与与v是连通的是连通的。记作。记作 u v 规定规定:对任何结点对任何结点u，u u。结点之间的连通关系是个等价关系结点之间的连通关系是个等价关系 令令G=是无向图，是无向图，R是是V上连通关系，即上连通关系，即 R=|u,v V且且u v

20、 显然显然R具有自反、对称和传递性。具有自反、对称和传递性。于是可以求商集于是可以求商集V/R。例例：给定右图所示给定右图所示 V/R=a,b,g，c,d,e,f，h School of Information Science and Engineering14-3 14-3 图的连通性图的连通性G的连通性与连通分支的连通性与连通分支 若若 u,v V，u v，则称，则称G是连通的是连通的 V/R=V1,V2,Vk，称，称等价类构成的子图等价类构成的子图GV1,GV2,GVk为为G的连通分支的连通分支，其个数，其个数 p(G)=k (k 1)；k=1，G是连通的。是连通的。下面实例中下面实例中

21、 p(G1)=3 p(G2)=2 p(G3)=1 School of Information Science and Engineering14-3 14-3 图的连通性图的连通性距离距离 u与与v之间的之间的距离距离：d(u,v)u与与v之间长度最短的通路。之间长度最短的通路。d(u,v)的性质：的性质：d(u,v)0,u v时时d(u,v)=d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)删除顶点及删除边删除顶点及删除边 G v 从从G中将中将v及关联的边去掉及关联的边去掉 G V 从从G中删除中删除V 中所有的顶点中所有的顶点 G e 将将e从从G中去掉中去掉 G E 删

22、除删除E 中所有边中所有边 School of Information Science and Engineering14-3 14-3 图的连通性图的连通性点割集与边割集点割集与边割集定义：定义：G=,VV V 为为点割集点割集p(G V)p(G)且有极小性且有极小性 v为为割点割点v为点割集为点割集定义：定义：G=,EE E 是是边割集边割集p(G E)p(G)且有极小性且有极小性 e是是割边割边（桥）（桥）e为边割集为边割集v上例中上例中v2,v5是点割集吗？是点割集吗？e7,e9,e5,e6 是边割集吗？是边割集吗？例：例：v1,v4，v6是点割集，是点割集，v6是割点。是割点。e1,

23、e2，e1,e3,e5,e6，e8等等是边割集，是边割集，e8是桥。是桥。School of Information Science and Engineering14-3 14-3 图的连通性图的连通性说明说明vKn中无点割集，中无点割集，Nn中既无点割集，也无边割集，其中中既无点割集，也无边割集，其中Nn为为 n 阶零图阶零图.v若若G 连通，连通，E 为边割集，则为边割集，则 p(G E)=2，V 为点割集，为点割集，则则 p(G V)2 点连通度点连通度 G为连通非完全图，为连通非完全图，(G)=min|V|V 为点割为点割集集 规定规定 (Kn)=n 1 若若G非连通，非连通，(G)

24、=0;若若 (G)=k，则称，则称G为为 k-连通图连通图 边连通度边连通度G为连通图，为连通图，(G)=min|E|E 为边割集为边割集 若若G非连通，则非连通，则(G)=0 若若(G)=r，则称，则称G是是 r-边连通图边连通图问题：问题：求上例中的点连通度和边连通度。求上例中的点连通度和边连通度。School of Information Science and Engineering14-3 14-3 图的连通性图的连通性说明说明v(Kn)=(Kn)=n 1vG非连通，则非连通，则 =0v若若G中有割点，则中有割点，则=1，若有桥，则，若有桥，则=1v若若(G)=k,则则G是是1-连通

25、图，连通图，2-连通图，连通图，k-连通图，但连通图，但不是不是(k+s)-连通图，连通图，s 1v若若(G)=r,则则G是是1-边连通图，边连通图，2-边连通图，边连通图，r-边连通边连通图，但不是图，但不是(r+s)-边连通图，边连通图，s 1v,之间的关系之间的关系.定理定理14-3.1 (G)(G)(G)问题：问题：请画出一个请画出一个 的无向简单图。的无向简单图。School of Information Science and Engineering14-3 14-3 图的连通性图的连通性2.有向图的连通性有向图的连通性定义定义 D=为有向图为有向图 vi vj（vi 可达可达 v

26、j）vi 到到vj 有通路有通路 vi vj（vi 与与vj 相互可达）相互可达）性质性质 具有自反性具有自反性(vi vi)、传递性、传递性 具有自反性、对称性、传递性具有自反性、对称性、传递性 vi 到到vj 的距离的距离类似于无向图中，只需注意距离表示法的不同类似于无向图中，只需注意距离表示法的不同(无向图中无向图中d(vi,vj)，有向图中，有向图中d)及及 d无对称性无对称性 School of Information Science and Engineering14-3 14-3 图的连通性图的连通性定义定义 D=为有向图为有向图 D弱连通弱连通(连通连通)基图为无向连通图基图为

27、无向连通图 D单向连通单向连通 vi,vj V，vivj 或或 vjvi D强连通强连通 vi,vj V，vivj易知，强连通易知，强连通单向连通单向连通弱连通弱连通定理定理14-3.1 D强连通当且仅当强连通当且仅当D中存在经过每个顶点至少一次中存在经过每个顶点至少一次的回路。的回路。例例 判断下面图的连通性。判断下面图的连通性。School of Information Science and Engineering14-4 14-4 图的矩阵表示图的矩阵表示 1.邻接矩阵邻接矩阵 以结点与结点之间的邻接关系确定的矩阵。以结点与结点之间的邻接关系确定的矩阵。定义定义设设D=是个有向图，是个

28、有向图，V=v1,v2,v3,vn,一个一个nn阶矩阵阶矩阵A=(aij)称为称为D的邻接矩阵。的邻接矩阵。其中其中：aij为为顶点顶点vi邻接到顶点邻接到顶点vj边的条数。边的条数。School of Information Science and Engineering14-4 14-4 图的矩阵表示图的矩阵表示 例：例：给定无向图给定无向图G1和有向图和有向图G2如图所示，求邻接矩阵。如图所示，求邻接矩阵。性质性质 School of Information Science and Engineering邻接矩阵的乘积邻接矩阵的乘积14-4 14-4 图的矩阵表示图的矩阵表示 Schoo

29、l of Information Science and Engineering在在(A(G1)2 中中a342=2 表示从表示从v3到到v4有长度为有长度为2的路有的路有2条。条。在在(A(G1)3中中a233=6 表示从表示从v2到到v3有长度为有长度为3的路有的路有6条。条。邻接矩阵的乘积邻接矩阵的乘积14-4 14-4 图的矩阵表示图的矩阵表示为D中长度为 l 的通路总数，定理定理14-4.1 设设 A为有向图为有向图 D 的邻接矩阵，的邻接矩阵，V=v1,v2,vn为为顶点集，则顶点集，则 A 的的 l 次幂次幂 Al（l 1）中元素）中元素为D中vi 到vj长度为 l 的通路数，其

30、中为vi到自身长度为 l 的回路数，而为为D 中长度为中长度为 l 的回路总数的回路总数.School of Information Science and Engineering例：例：有向图有向图D如图所示，求如图所示，求 A,A2,A3,A4，并回答诸问题：，并回答诸问题：(1)D 中长度为中长度为1,2,3,4的通路各有多少条？其中回路分别为的通路各有多少条？其中回路分别为多少条？多少条？(2)D 中长度小于或等于中长度小于或等于4的通路为多少条？其中有多少条回的通路为多少条？其中有多少条回路？路？实例实例 School of Information Science and Engin

31、eering(1)D中长度为中长度为1的通路为的通路为8条，其中有条，其中有1条是回路。条是回路。D中长度为中长度为2的通路为的通路为11条，其中有条，其中有3条是回路。条是回路。D中长度为中长度为3和和4的通路分别为的通路分别为14和和17条，回路分别为条，回路分别为1与与3条。条。(2)D中长度小于等于中长度小于等于4的通路为的通路为50条，其中有条，其中有8条是回路。条是回路。求解求解 School of Information Science and Engineering2.可达矩阵可达矩阵定义定义设设D=是个有向图是个有向图,V=v1,v2,v3,vn,一个一个nn阶矩阵阶矩阵P=

32、(pij)称为称为D的可达性矩阵。的可达性矩阵。其中其中:v vi i到到v vj j可达（至少有一条可达（至少有一条通通路）路）否则否则求可达矩阵求可达矩阵两种方法求两种方法求可达性矩阵可达性矩阵P：方法方法1.按照矩阵相乘分别求出按照矩阵相乘分别求出A(k)(k2),然后再然后再。方法方法2.用求传递闭包的用求传递闭包的Warshall算法算法。由定义不难看出由定义不难看出,G 强连通当且仅当强连通当且仅当 P(G)为全为全1矩阵矩阵.14-4 14-4 图的矩阵表示图的矩阵表示 School of Information Science and Engineering例：例：G2如图所示

33、如图所示,求它的求它的可达矩阵可达矩阵P。P=AA(2)A(3)A(4)A(5)14-4 14-4 图的矩阵表示图的矩阵表示补充知识补充知识:强分图、单侧分图和弱分图强分图、单侧分图和弱分图在简单有向图中在简单有向图中,具有强连通的最大子图具有强连通的最大子图,称为称为强分图强分图.具具有单侧连通的最大子图有单侧连通的最大子图,称为称为单侧分图单侧分图.具有弱连通的最具有弱连通的最大子图大子图,称为称为弱分图弱分图.这些这些分图用结点的集合表示分图用结点的集合表示.例如例如,给定有向图给定有向图G,如图所示如图所示:求它的强分图、单侧分图和求它的强分图、单侧分图和弱分图弱分图.解解:强分图强分

34、图:由由a,g,hbc def导出的子图导出的子图.单侧分图单侧分图:由由a,g,h,b,f,d,eb,c,f,d,e导出的子图导出的子图.弱分图弱分图:G本身是弱分图本身是弱分图.在有向图中在有向图中,每个结点必位于一个且只位于一个强分图中每个结点必位于一个且只位于一个强分图中 ef c d gh a b School of Information Science and Engineering14-4 14-4 图的矩阵表示图的矩阵表示用可达矩阵求强分图用可达矩阵求强分图下面看怎样用下面看怎样用P求强分图求强分图先将先将P转置得转置得PT,如果如果vi与与vj相互可达相互可达,则则pij=

35、pTij=1以以G2为例说明。为例说明。1111101011111110101101011P=1010011111101001111111111PT=PPT=10100010111010001011010111100011000001110011100111初等初等变换变换得得v1v3v2v4v5 对对PPT进行初等变换进行初等变换,第第2行与第行与第3行交换行交换,再第再第2列与第列与第3列交换列交换,最后得两个强分图：最后得两个强分图：v1,v3和和v2,v4,v5 School of Information Science and Engineering14-4 14-4 图的矩阵表示图

36、的矩阵表示3.关联矩阵关联矩阵 无向图的完全关联矩阵无向图的完全关联矩阵定义定义设设G=是个无向图，是个无向图，V=v1,v2,v3,vm,E=e1,e2,e3,en,一个一个mn阶矩阵阶矩阵M=(mij)称为称为G的关联矩阵的关联矩阵。其中其中:mij为为顶点顶点vi与边与边ej的关联次数的关联次数性质性质 School of Information Science and Engineering14-4 14-4 图的矩阵表示图的矩阵表示有向图的完全关联矩阵有向图的完全关联矩阵定义定义设设G=是个有向图，且无环是个有向图，且无环,V=v1,v2,v3,vm,E=e1,e2,e3,en,一个

37、一个mn阶矩阵阶矩阵M=(mij)称为称为G的完全的完全关联矩阵。关联矩阵。其中其中:v vi i是是e ej j的起点的起点 v vi i是是e ej j的终点的终点 v vi i与与e ej j不关联不关联性质性质 (4)平行平行边对应边对应的列相同的列相同 School of Information Science and Engineering主要内容主要内容v无向图、有向图、关联与相邻、简单图、完全图、正则无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构图、子图、补图；握手定理与推论；图的同构v通路与回路及其分类通路与回路及其分类v无向图的连通

38、性与连通度无向图的连通性与连通度v有向图的连通性及其分类有向图的连通性及其分类v图的矩阵表示图的矩阵表示主要内容主要内容 School of Information Science and Engineering练习练习19阶无向图阶无向图G中，每个顶点的度数不是中，每个顶点的度数不是5就是就是6.证明证明G中至中至少有少有5个个6度顶点或至少有度顶点或至少有6个个5度顶点度顶点.2数组数组2,2,2,2,3,3能简单图化吗？若能，画出尽可能多的能简单图化吗？若能，画出尽可能多的非同构的图来非同构的图来.School of Information Science and Engineering

39、练习练习3有向图有向图D如图所示，回答下列问题：如图所示，回答下列问题：(1)D中有几种非同构的圈？中有几种非同构的圈？(2)D中有几种非圈非同构的简单回路？中有几种非圈非同构的简单回路？(3)D是哪类连通图是哪类连通图?(4)D中中v1到到v4长度为长度为1,2,3,4的通路各多少的通路各多少 条？其中几条是非初级的简单通路？条？其中几条是非初级的简单通路？(5)D中中v1到到v1长度为长度为1,2,3,4的回路各多少的回路各多少 条？讨论它们的类型条？讨论它们的类型.(6)D中长度为中长度为4的通路（不含回路）有多少条？的通路（不含回路）有多少条？(7)D中长度为中长度为4的回路有多少条？的回路有多少条？(8)D中长度中长度 4的通路有多少条？其中有几条是回路？的通路有多少条？其中有几条是回路？(9)写出写出D的可达矩阵的可达矩阵.