第三部分 图论 本部分主要内容 图的基本概念 树 欧拉图与哈密顿图 二部图与匹配 平面图 着色.

Presentation on theme: "第三部分 图论 本部分主要内容 图的基本概念 树 欧拉图与哈密顿图 二部图与匹配 平面图 着色."— Presentation transcript:

1 第三部分 图论 本部分主要内容 图的基本概念 树 欧拉图与哈密顿图 二部图与匹配 平面图 着色

2 第十一章 图的基本概念 主要内容 图 通路与回路 图的连通性 图的矩阵表示 预备知识 多重集合——元素可以重复出现的集合
无序集——AB={(x,y) | xAyB}

3 11.1 图 定义11.1 无向图G = <V,E>, 其中 (1) V为非空有穷集, 称为顶点集，其元素称为顶点
(2) E为VV 的多重有穷集, 称为边集, 其元素称为无向边, 简称边 例 无向图G = <V,E>, 其中 V = {v1, v2, v3, v4, v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}

4 有向图 定义11.2 有向图D=<V,E>,其中 (1) V 为非空有穷集, 称为顶点集，其元素称为顶点
(2) E为VV 的多重有穷集, 称为边集, 其元素称为有向边, 简称边 例 有向图D=<V,E>, 其中 V={a,b,c,d} E={<a,a>,<a,b>,<a,b>,<a,d>, <d,c>,<c,d>,<c,b>} 注意：图的集合表示与图形表示之间的对应

5 相关概念 1. 无向图和有向图通称图. 记顶点集V(G), 边集E(G). 2. 图的阶, n阶图. 3. n 阶零图Nn, 平凡图N1.
4. 空图. 5. 标定图与非标定图. 6. 有向图的基图. 7. 无向图中顶点与边的关联及关联次数, 顶点与顶点、边与 边的相邻关系. 8. 有向图中顶点与边的关联, 顶点与顶点、边与边的相邻关 系. 9. 环, 孤立点.

6 多重图与简单图 定义11.3 无向图中关联同一对顶点的2条和2条以上的边称为 平行边. 有向图中2条和2条以上始点、终点相同的边称为平
定义11.3 无向图中关联同一对顶点的2条和2条以上的边称为 平行边. 有向图中2条和2条以上始点、终点相同的边称为平 行边. 平行边的条数称为重数. 含平行边的图称为多重图, 不含平行边和环的图称为简单图. 定义11.4 设G=<V,E>为无向图, vV, 称v作为边的端点的次 数之和为v的度数, 简称度, 记作d(v). 设D=<V,E>为有向图, vV, 称v作为边的始点的次数之和 为v的出度, 记作d+(v); 称v作为边的终点的次数之和为v的入 度, 记作d(v); 称d+(v)+d(v)为v的度数, 记作d(v).

7 顶点的度数 设G=<V,E>为无向图, G的最大度(G)=max{d(v) | vV}
G的最小度 (G)=min{d(v) | vV} 设D=<V,E>为无向图, D的最大度(D)=max{d(v) | vV} D的最小度 (D)=min{d(v) | vV} D的最大出度+(D)=max{d+(v) | vV} D的最小出度  +(D)=min{d+(v) | vV} D的最大入度(D)=max{d(v) | vV} D的最小入度  (D)=min{d(v) | vV} 悬挂顶点: 度数为1的顶点, 悬挂边: 与悬挂顶点关联的边. 偶度(奇度)顶点: 度数为偶数(奇数)的顶点

8 实例 d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3. =4, =1.
=4, =1. v4是悬挂点, e7是悬挂边. d+(a)=4, d(a)=1, d(a)=5, d+(b)=0, d(b)=3, d(b)=3, d+(c)=2, d(c)=1, d(c)=3, d+(d)=1, d(d)=2, d(d)=3, +=4,  +=0, =3, =1, =5, =3.

9 握手定理 定理11.1 在任何无向图中, 所有顶点的度数之和等于边数的2倍.
证 G中每条边 (包括环) 均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m 条边共提供 2m 度. 定理11.2 在任何有向图中，所有顶点的度数之和等于边数的2倍; 所有顶点的入度之和等于所有顶点的出度之和, 都等于边数. 推论 任何图 (无向或有向) 中，奇度顶点的个数是偶数. 证 由握手定理, 所有顶点的度数之和是偶数, 而偶度顶点的度 数之和是偶数, 故奇度顶点的度数之和也是偶数. 所以奇度顶 点的个数必是偶数．

10 握手定理应用 例1 无向图G有16条边，3个4度顶点，4个3度顶点，其余均为2度顶点度，问G的阶数n为几？ 解 本题的关键是应用握手定理.
解 本题的关键是应用握手定理. 设除3度与4度顶点外，还有x个顶点, 由握手定理, 162=32 = 34+43+2x 解得 x = 4, 阶数 n = 4+4+3=11. 例2 在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？ 解：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度为奇数的图，这是不可能的。 定理11.3 设G为任意n阶无向简单图，则(G)n1．

11 图的同构 定义11.5 设G1=<V1,E1>, G2=<V2,E2>为两个无向图(两个有向
图)，若存在双射函数f:V1V2, 使得vi,vjV1, (vi,vj)E1 当且仅当 (f(vi),f(vj))E2 （<vi,vj>E1 当且仅当 <f(vi),f(vj)>E2 ) 并且, (vi,vj)（<vi,vj>）与 (f(vi),f(vj))（<f(vi),f(vj)>）的重数相 同，则称G1与G2是同构的，记作G1G2. 例

12 图同构的实例 (1)与(2), (3)与(4), (5)与(6)均不同构. (1) (2) (3) (4) (5) (6)
(1)与(2), (3)与(4), (5)与(6)均不同构. (1) (2) (3) (4) (5) (6) 说明: 1. 图的同构关系具有自反性、对称性和传递性. 2. 判断两个图同构是个难题

13 图同构的实例 所有4阶3条边非同构的简单无向图 所有3阶2条边非同构的简单有向图

14 补图与自补图 定义11.6 设G=<V,E>为n阶无向简单图，令 ={(u,v) | uVvVuv(u,v)E},
称 =<V, >为G的补图． 若G  则称G是自补图． 例 (b)与(c)互为补图，(a)是自补图．

15 完全图与竞赛图 定义11.7 (1) n (n1) 阶无向完全图——每个顶点与其余顶点均相邻的无向简单图，记作 Kn.
简单性质：m=n(n-1)/2, ==n-1 (2) n (n1)阶有向完全图——每对顶点之间均有两条方向相反的有向边的有向简单图. 简单性质： m=n(n-1), ==2(n-1) +=+===n-1 (3) n (n1) 阶竞赛图——基图为Kn的有向简单图. 简单性质： m=n(n-1)/2, ==n-1

16 正则图 K5 3阶有向完全图 4阶竞赛图 定义11.8 k-正则图——==k 的无向简单图
简单性质：m=kn/2, 当k是奇数时, n必为偶数. 例 Kn是 (n1)-正则图 彼得松图是3-正则图

17 子图 定义11.9 设两个图G=<V,E>, G =<V,E >（同为无向图或同为有向图）, 若VV且EE，则称G是G的子图，G为G 母图，记作G G. 又若VV或EE，则称G 为G的真子图. 若G G且V=V，则称G 为G的生成子图． 设V1V且V1, 称以V1为顶点集, 以G中两个端点都在V1中的边组成边集的图为G中V1的导出子图, 记作G[V1]. 设E1E且E1, 称以E1为边集, 以E1中边关联的顶点为顶点集的图为G中E1的导出子图, 记作G[E1]． 例 G G[{a,b,c}] G[{e1,e3}]

18 删除, 收缩与加新边 定义11.10 设G=<V,E>为无向图．
(1) 设eE，用Ge表示从G中去掉边e，称为删除边e．又设EE，用 GE 表示从G中删除E 中的所有边，称为删除E． (2) 设vV，用Gv表示从G中去掉v及所关联的所有边，称为删除顶点v．又设V V，用GV 表示从G中删除V 中所有的顶点，称为删除V． (3) 设e=(u,v)E，用G＼e表示从G中删除e后，将e的两个端点u,v用一个新的顶点w（可以用u或v充当w）代替，并使w关联除e以外u,v关联的所有边，称为收缩边e ． (4) 设u,vV（u,v可能相邻，也可能不相邻），用G(u,v)（或G+(u,v)）表示在u,v之间加一条边(u,v)，称为加新边． 在收缩边和加新边过程中可能产生环和平行边．

19 实例 G G-e5 G-{e1,e4} G-{v4,v5} G-v5 G＼e5 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5

20 11.2 通路与回路 定义11.11 设图G=<V,E> (无向或有向的), G中顶点与边的交
替序列  = v0e1v1e2…elvl，如果vi1, vi 是 ei 的端点(始点和终 点), 1il, 则称 为v0到vl的通路. v0,vl分别称作 的始点和终 点.  中的边数l称作它的长度. 又若 v0=vl, 则称 为回路. 若 所有的边各异, 则称 为简单通路. 又若v0=vl, 则称 为简单回 路. 若 中所有顶点各异(除v0和vl可能相同外)且所有边也各 异, 则称 为初级通路或路径. 若又有v0=vl, 则称 为初级回 路或圈. 长度为奇数的圈称为奇圈, 长度为偶数的圈称为偶圈. 若 中有边重复出现, 则 称为复杂通路. 若又有v0=vl, 则称  为复杂回路.

21 通路与回路 定理11.4 在n 阶图G中，若从顶点u 到v（uv）存在通路，则 从u 到 v 存在长度小于或等于n1 的通路.
定理11.5 在n 阶图G中，若存在 v 到自身的回路，则一定存在 v 到自身长度小于或等于 n 的回路. 推论 在n 阶图G中，若存在 v 到自身的简单回路，则一定存 在v 到自身的长度小于或等于n 的初级回路.

22 同构意义下和定义意义下的圈 例2 无向完全图Kn（n3）中有几种非同构的圈？
解 长度相同的圈都是同构的. 易知Kn(n3)中含长度3,4,…,n 的圈，共有n2种非同构的圈． 长度相同的圈都是同构的, 因此在同构意义下给定长度的圈 只有一个. 在标定图中, 圈表示成顶点和边的标记序列. 如果 只要两个圈的标记序列不同, 称这两个圈在定义意义下不同. 例3 无向完全图K3的顶点依次标定为a,b,c．在定义意义下K3中有多少个不同的长度为3的圈？ 解 在定义意义下, 不同起点(终点)的圈是不同的, 顶点间排列顺序不同的圈也是不同的, 因而K3中有3!=6个不同的长为3的圈：abca，acba，bacb，bcab，cabc，cbac．

23 带权图与最短路径 定义11.12 设图G=<V,E> (无向图或有向图), 对G的每一条边e,
给定一个数W(e),称作边e的权. 把这样的图称为带权图, 记作 G=<V,E,W>. 当e=(u,v)(<u,v>)时, 把W(e)记作W(u,v). 设P是G中的一条通路, P中所有边的权之和称为P的长度, 记作W(P). 类似地, 可定义回路C的长度W(C). 设带权图G=<V,E,W> (无向图或有向图), 其中每一条边e的 权W(e)为非负实数. u,vV, 当u和v连通(u可达v)时, 称从u到 v长度最短的路径为从u到v的最短路径, 称其长度为从u到v的 距离, 记作d(u,v). 约定: d(u,u)=0; 当u和v不连通(u不可达v)时, d(u,v)=+.

24 最短路问题 最短路问题: 给定带权图G=<V,E,W>及顶点u和v, 其中每一条
边e的权W(e)为非负实数, 求从u到v的最短路径. Dijkstra标号法 (求从s到其余各点的最短路径和距离) 1. 令l(s)(s,0), l(v)(s,+) (vV-{s}), i1, l(s)是永久标号, 其余标号均为临时标号, us 2. for 与u关联的临时标号的顶点v if l2(u)+W(u,v)< l2(v) then 令l(v)(u,l2(u)+W(u,v)) 4. 计算l2(t)=min{ l2(v) | vV且有临时标号}, l(t)改为永久标号 5. if i<n then 令ut, ii+1, 转2 对每一个u, d(s,u)= l2(u),根据l1(v)回溯找到s到u的最短路径.

25 实例 总部 例11.5 一个总部和6个工地, 求从总部到各工地的最短路径 17 7 2 15 1 4 解 6 10 3 5 17
例11.5 一个总部和6个工地, 求从总部到各工地的最短路径 解 1 2 3 4 5 6 7 15 10 17 总部 1 2 3 4 5 6 7 15 10 17 (0,S) (+,S)

26 实例 u=1 u=3 17 (15,1) 7 2 15 (0,S) 1 4 (+,S) 6 10 3 5 (10,1) 17 (13,3)
(14,3) u=3

27 实例 1 2 3 4 5 6 7 15 10 17 (0,S) (13,3) (10,1) (19,2) (14,3) (30,2) (+,S) u=2 1 2 3 4 5 6 7 15 10 17 (0,S) (13,3) (10,1) (18,5) (14,3) (30,2) (16,5) u=5

28 实例 1 2 3 4 5 6 7 15 10 17 (0,S) (13,3) (10,1) (18,5) (14,3) (22,6) (16,5) u=6 1 2 3 4 5 6 7 15 10 17 (0,S) (13,3) (10,1) (18,5) (14,3) (22,6) (16,5) u=4

29 实例 1 2 3 4 5 6 7 15 10 17 (0,S) (13,3) (10,1) (18,5) (14,3) (22,6) (16,5) u=7 v1v3v2, d(v1,v2)= v1v3, d(v1,v3)=10 v1v3v5v4, d(v1,v4)= v1v3v5, d(v1,v5)=14 v1v3v5v6, d(v1,v6)= v1v3v5v6v7, d(v1,v7)=22

30 11.3 图的连通性 定义11.13 设无向图G=<V,E>，若u,vV之间存在通路，则称
u,v是连通的，记作u～v. 规定: vV v～v． 若无向图G是平凡图或G中任何两个顶点都是连通的，则 称G为连通图，否则称G为非连通图． ～是V上的等价关系, 具有自反性、对称性和传递性． 定义9.14 设无向图G=<V,E>，Vi是V关于顶点之间连通关 系～的一个等价类，称导出子图G[Vi]为G的一个连通分支. G的连通分支数记为p(G)．

31 点割集与边割集 定义11.15 设无向图G=<V,E>. 若VV使得p(GV )>p(G), 且
对于任意的V V, 均有p(GV)=p(G), 则称V是G的点割集. 若V ={v}, 则称v为割点． 定义 设无向图G=<V,E>, 若EE使得p(GE )>p(G), 且 对于任意的EE, 均有p(GE)=p(G), 则称E是G的边割集， 简称为割集. 若E ={e}, 则称e为割边或桥． 例3 {v1,v4}，{v6}是点割集， v6是割点. {v2,v5}不是. {e1,e2}，{e1,e3,e5,e6}，{e8}等 是边割集，e8是桥. 而{e7,e9,e5,e6} 不是.

32 点连通度与边连通度 定义11.17 G为连通非完全图, 称 (G) = min{ |V |V 为点割集 }
为G的点连通度, 简称连通度. 若(G)k，则称G为 k-连通图 . 规定 (Kn) = n1, 非连通图的连通度为0. 定义11.18 设G为连通图, 称 (G) = min{|E|E为边割集} 为G的边连通度. 若(G)r，则称G是 r 边-连通图. 规定非连通图的边连通度为0. v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 例 =2, 2-连通图, 也是1-连通. =2, 2边-连通图, 也是1边-连通.

33 几点说明 (Kn)=(Kn)=n1 G非连通，则 ==0 若G中有割点，则=1，若有桥，则=1
若(G)=k, 则G是1-连通图，2-连通图，…，k-连通图，但不是(k+s)-连通图，s1 若(G)=r, 则G是1边-连通图，2边-连通图，…，r边-连通图，但不是(r+s)-边连通图，s1

34 几点说明 定理11.6 (G)(G)(G)
证明 若 G 不连通,则k(G)＝λ(G)＝0,故上式成立.若 G 连通,1) 证明λ(G)≤δ(G) 如果 G 是平凡图,则 λ(G)＝0≤δ(G),若G是非平凡图,则因每一结点的所有关联边必含一个边割集,故λ(G)≤δ(G) . 2) 再证 k(G)≤λ(G) (a) 设λ(G)＝1,即G有一割边,显然这时k(G)＝1,上式成立.(b) 设λ(G)≥2,则必可删去某λ(G)条边,使G不连通,而删去其中λ(G)-1条边,它仍是连通的,且有一条桥e＝(u,v).对λ(G)-1条边中的每一条边都选取一个不同于u,v的端点,把这些端点删去,则必至少删去λ(G)-1条边.若这样产生的图是不连通的,则k(G)≤λ(G)-1＜λ(G),若这样产生的图是连通的,则e仍是桥,此时再删去u或v,就必产生一个不连通图,故 k(G)≤λ(G).由 1) 和 2) 得 k(G)≤λ(G)≤δ(G)

35 有向图的连通性及分类 定义11.19 设D=<V,E>为一个有向图, vi,vjV, 若从vi到vj存在
通路, 则称vi可达vj, 记作vivj . 规定vi vi. 若vivj且vjvi， 则称vi与vj是相互可达的, 记作vivj. 规定vivi． 性质:  具有自反性(vi  vi)、传递性  具有自反性、对称性、传递性 定义 若有向图D=<V,E>的基图是连通图, 则称D是弱连通 图, 简称为连通图. 若vi,vjV, vivj与vjvi至少有一个成立， 则称 D是单向连通图. 若vi,vjV, 均有vivj, 则称D是强连 通图．

36 有向图的连通性 例 强连通 单向连通 弱连通 定理11.7 有向图D=<V,E>是强连通图当且仅当D中存在经过每个顶点至少一次的回路． 证 充分性显然. 证必要性. 设V={v1,v2,,vn}, i为vi到vi+1的通路( i=1,2,…,n1), n为vn到v1的通路. 依次连接1, 2, …, n1, n所得到的回路经过D中每个顶点至少一次．

37 有向图的连通性 定理11.8 有向图G是单向连通图当且仅当G中存在经过每个顶点至少一次的通路． 证明：充分性显然.
必要性：设P是G中经历的不同顶点的个数最多的一条途径. 如果有某个顶点x不在P上：任取P上的顶点v，v和x是单向连通的. 第一种情形：对P上的任何顶点v，都不存在从v到x的路，则对P上第一个顶点u，必有从x到u的路Q，那麼把Q和P连起来得到的途径Q*P比P经历的不同顶点的个数要多，矛盾. 第二种情形：存在P上某顶点v使得存在从v到x的路，那麼可以设u是P上最後一个有从u到x的路的顶点，并设从u到x的路为Q.若u是P上最後一个顶点，那麼P和Q联结起来得到的途径P*Q比P经历的不同顶点的个数要多，矛盾.若P在u後仍有顶点，设w为u的下一个顶点，则必存在从x到w的路q，那麼设P=(p,u,e,w,r)，则途径(p,u)*Q*q*(w,r)比P经历的不同顶点的个数要多，矛盾.所以图G的所有顶点都在P上.

38 扩大路径法 设G=<V,E>为无向图,  为G中一条路径. 若此路径的两个端 点都不与通路外的顶点相邻, 则称 是极大路径.
任取一条边, 如果它有一个端点与其他的顶点相邻, 就将这条 边延伸到这个顶点. 继续这一过程, 直至得到一条极大路径为 止. 称此种方法为“扩大路径法”. 用扩大路径法总可以得到 一条极大路径. 在有向图中可类似讨论. 例 由一条路径扩大出的极大路径不惟一，极大路径不一定是 最长的路径

39 扩大路径法的应用 例4 设 G 为 n（n3）阶无向简单图，  2，证明G 中存在 长度  +1 的圈.
证 设  = v0v1…vl 是一条极大路径, 则 l  . 因为v0 不与  外 顶点相邻, 又 d(v0)  , 因而在 上除 v1外, 至少还存在1个 顶点与 v0 相邻. 设 vx 是离 v0 最远的顶点, 于是v0v1…vxv0 为 G 中长度  +1 的圈.

40 11.4 图的矩阵表示 无向图的关联矩阵 定义 无向图G=<V,E>，|V|=n，|E|=m，令 mij为 vi 与 ej 的关联次数，称(mij)nm为G 的关联矩阵，记为M(G). 例

41 无向图关联矩阵的性质

42 有向图(无环)的关联矩阵 定义11.22 设有向图D=<V,E>中无环，令 则称 (mij)nm为D的关联矩阵，记为M(D).
例

43 有向图关联矩阵的性质 (1) 每列恰好有一个+1和一个-1． (2) -1的个数等于+1的个数，都等于边数m.
第i行中，+1的个数等于d+(vi)，-1的个数等于d(vi)． (4) 平行边对应的列相同

44 有向图的邻接矩阵 定义11.23 设有向图D=<V,E>, V={v1, v2, …, vn}, 令 为顶点
vi 邻接到顶点 vj 边的条数，称( )为D的邻接矩阵，记作 A(D)，或简记为A. 例

45 有向图邻接矩阵的性质

46 邻接矩阵的应用 定理11.9 设 A为有向图 D 的邻接矩阵, 顶点集V={v1,v2,…, vn}，则 A 的 l 次幂 Al（l1）中元素 为长度为 l 的通路总数， 为vi 到vj长度为 l 的通路数， 为vi到自身长度为 l 的回路数， 为长度为 l 的回路总数. 推论 设Bl=A+A2+…+Al (l1), 则 为长度小于或等于 l 的回路数. 为长度小于或等于 l 的通路数,

47 实例 例5 有向图D如图所示，求 A, A2, A3, A4，并回答诸问题：

48 实例求解 (1) D中长度为1的通路为8条，其中有1条是回路. D中长度为2的通路为11条，其中有3条是回路.

49 有向图的可达矩阵 定义11.24 设D=<V,E>为有向图. V={v1, v2, …, vn}, 令
称 (pij)nn 为D的可达矩阵，记作P(D)，简记为P. P(D)的主对角线上的元素全为1. D 强连通当且仅当 P(D)为全1矩阵. 例

50 第九章 习题课 主要内容 无向图和有向图及其有关的概念; 握手定理及其推论；图的同构 通路与回路 无向图的连通性与连通度
有向图的连通性及其分类 图的矩阵表示

51 基本要求 深刻理解图及其有关的概念 深刻理解和灵活地应用握手定理及推论 记住通路与回路的定义、分类及表示法
深刻理解与无向图连通性、连通度有关的诸多概念 会判别有向图连通性的类型 熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵

52 练习1 1．9阶无向图G中，每个顶点的度数不是5就是6. 证明G中至少有5个6度顶点或至少有6个5度顶点. 证 关键是利用握手定理的推论.
证 关键是利用握手定理的推论. 方法一：穷举法 设G中有x个5度顶点，(9x)个6度顶点，由于奇度顶点的个数是偶数，(x, 9x)只有5种可能：(0,9), (2,7), (4,5), (6,3), (8,1）它们都满足要求. 方法二：反证法 否则，至多有4个5度顶点并且至多有4个6度顶点，这与G是 9 阶图矛盾.

53 练习2 2．存在以2, 2, 2, 2, 3, 3为顶点度数的简单图吗？若存在，画出尽可能多的这种非同构的图来. 解

54 练习3 3．设D=<V,E>为有向简单图, 已知 (D)  2,  +(D)>0,
 (D)>0, 证明D中存在长度  max{ +, }+1的圈. 证 用扩大路径法证明. 设    +, 证明D中存在长度   +1的圈. 设  = v0v1…vl为极大路径, 则l   . 在  上存在d(v0)  个顶点 邻接到v0, 设vk是其中离v0最远的顶点, k . 于是, v0v1…vkv0为D中长度   +1的圈 . 当 +   时, 类似可证.

55 练习4 4．有向图D如图所示，回答下列诸问： (1) D中有几种不同构的圈？ (2) 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的可达矩阵.

56 解答 解 (1) 有3种非同构的圈，长度分别为1,2,3. (2) 有3种非同构的非圈简单回路，它们的长度分别为 4,5,6.
解 (1) 有3种非同构的圈，长度分别为1,2,3. (2) 有3种非同构的非圈简单回路，它们的长度分别为 4,5,6. (3) D是强连通的. 为解(4)—(8), 先求D的邻接矩阵的前4次幂.

57 解答 (4) v1到v4长度为1,2,3,4的通路数分别为0,0,2,2. (定义意义下).
(6) 长度为4的通路(不含回路)为33条. (7) 长度为4的回路为11条. (8) 长度4的通路88条，其中22条为回路. (9) 44的全1矩阵.