新编文档-离散数学第十四章图论基本概念-精品文档_图文

第五部分 图论
本部分主要内容 ? 图的基本概念 ? 欧拉图、哈密顿图 ? 树 ? 平面图 ? 支配集、覆盖集、独立集、匹配与着色

1

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

2

14.1 图
定义14.1 无向图G = <V,E>, 其中 (1) V ? ?为顶点集,元素称为顶点 (2) E为V?V 的多重集,其元素称为无向边,简称边

实例

设 V = {v1, v2, …,v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} 则 G = <V,E>为一无向图
3

有向图
定义14.2 有向图D=<V,E>, 只需注意E是V?V 的多重子集 图2表示的是一个有向图,试写出它的V 和 E

注意:图的数学定义与图形表示,在同构(待叙)的意义下 是一一对应的
4

1. 图 ① 可用G泛指图(无向的或有向的) ② V(G), E(G), V(D), E(D) ③ n阶图 2. 有限图 3. n 阶零图与平凡图 4. 空图——? 5. 用 ek 表示无向边或有向边 6. 顶点与边的关联关系 ① 关联、关联次数 ②环 ③ 孤立点 7. 顶点之间的相邻与邻接关系
5

相关概念

相关概念
8. 邻域与关联集 ① v?V(G) (G为无向图)
v 的邻 N ( v ) ? { 域 u | u ? V ( G ) ? ( u , v ) ? E ( G ) ? u ? v } v 的闭 N ( v ) ? N 邻 ( v ) ? { v } 域

( v ) ? { e | e ? E ( G ) ? e 与 v 关联 } v 的关联集 I ② v?V(D) (D为有向图)
? v 的后继元集 ? ( v )? { u |u ? V ( D ) ? ? v ,u ?? E ( D )? u ? v } D ? v 的先驱元集 ? ( v )? { u |u ? V ( D ) ? ? u ,v ?? E ( D )? u ? v } D ? ? v 的邻域 N ( v ) ? ? ( v ) ? ? ( v ) D D D

v 的闭邻域 N ( v )? N ( v ) ? { v } D D

9. 标定图与非标定图 10. 基图
6

多重图与简单图
定义14.3 (1) 无向图中的平行边及重数 (2) 有向图中的平行边及重数(注意方向性) (3) 多重图 (4) 简单图 在定义14.3中定义的简单图是极其重要的概念

7

顶点的度数
定义14.4 (1) 设G=<V,E>为无向图, ?v?V, d(v)——v的度数, 简称度 (2) 设D=<V,E>为有向图, ?v?V, d+(v)——v的出度 d?(v)——v的入度 d(v)——v的度或度数 (3) ?(G), ?(G) (4) ?+(D), ?+(D), ??(D), ??(D), ?(D), ?(D) (5) 奇顶点度与偶度顶点

8

握手定理
定理14.1 设G=<V,E>为任意无向图,V={v1,v2,…,vn}, |E|=m, 则

?d(v ) ? 2m
i i?1

n

证 G中每条边 (包括环) 均有两个端点,所以在计算G中各顶点 度数之和时,每条边均提供2度,m 条边共提供 2m 度. 定理14.2 设D=<V,E>为任意有向图,V={v1,v2,…,vn}, |E|=m, 则
? d ( v ) ? 2 m , 且 d ( v ) ? d ( v ) ? m ? ? ? i i i ? i ? 1 i ? 1 i ? 1 n n n

本定理的证明类似于定理14.1
9

握手定理推论
推论 任何图 (无向或有向) 中,奇度顶点的个数是偶数. 证 设G=<V,E>为任意图,令 V1={v | v?V? d(v)为奇数} V2={v | v?V? d(v)为偶数} 则V1?V2=V, V1?V2=?,由握手定理可知
2 m ? d ( v ) ? d ( v ) ? d ( v ) ? ? ?

由于2m, ? d ( v ) 均为偶数,所以 ? d ( v ) 为偶数,但因为V1中
v?V2
v?V1

v ? V

v ? V 1

v ? V 2

顶点度数为奇数,所以|V1|必为偶数.

10

握手定理应用
例1 无向图G有16条边,3个4度顶点,4个3度顶点,其余 顶点度数均小于3,问G的阶数n为几? 解 本题的关键是应用握手定理. 设除3度与4度顶点外,还有x个顶点v1, v2, …, vx, 则 d(vi) ? 2,i =1, 2, …, x, 于是得不等式 32 ? 24+2x 得 x ? 4, 阶数 n ? 4+4+3=11.

11

图的度数列
1 . V={v1, v2, …, vn}为无向图G的顶点集,称d(v1), d(v2), …, d(vn)为G的度数列 2. V={v1, v2, …, vn}为有向图D的顶点集, D的度数列:d(v1), d(v2), …, d(vn) D的出度列:d+(v1), d+(v2), …, d+(vn) D的入度列:d?(v1), d?(v2), …, d?(vn) 3. 非负整数列d=(d1, d2, …, dn)是可图化的,是可简单图化的. 易知:(2, 4, 6, 8, 10),(1, 3, 3, 3, 4) 是可图化的,后者又是可 简单图化的,而(2, 2, 3, 4, 5),(3, 3, 3, 4) 都不是可简单图化 的,特别是后者也不是可图化的
12

图的同构
定义14.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. ? 图之间的同构关系具有自反性、对称性和传递性. ? 能找到多条同构的必要条件,但它们全不是充分条件: ① 边数相同,顶点数相同; ② 度数列相同; ③ 对应顶点的关联集及邻域的元素个数相同,等等 若破坏必要条件,则两图不同构 ? 判断两个图同构是个难题 13

图同构的实例

(1)

(2)

(3)

(4)

图中,(1)与(2)不同构(度数列不同),(3)与(4)也不同构.

(1)

(2)
14

图中(1)与(2)的度数列相同,它们同构吗?为什么?

n 阶完全图与竞赛图
定义14.6 (1) n (n?1) 阶无向完全图——每个顶点与其余顶点均相邻的 无向简单图,记作 Kn. n ( n ? 1 ) 简单性质:边数 m ? , ? ? ? ? n ? 1 2

(2) n (n?1)阶有向完全图——每对顶点之间均有两条方向相 反的有向边的有向简单图. ? ? ? n ( n ? 1 ), ? ? ? 2 ( n ? 1 ), ? ? ? n ? 1 简单性质: m

?
2

?

(3) n (n?1) 阶竞赛图——基图为Kn的有向简单图. n ( n ? 1 ) 简单性质:边数 m ? , ? ? ? ? n ? 1
15

n 阶 k 正则图

(1)

(2)

(3)

(1)为K5,(2)为3阶有向完全图,(3)为4阶竞赛图. 定义14.7 n 阶k正则图——?=?=k 的无向简单图 简单性质:边数(由握手定理得)m ? nk 2 Kn是 n?1正则图, 彼得松图(见书上图14.3(1) 所示,记住它)
16

子图
定义14.8 G=<V,E>, G?=<V?,E?> (1) G??G —— G?为G的子图,G为G?的母图 (2) 若G??G且V?=V,则称G?为G的生成子图 (3) 若V??V或E??E,称G?为G的真子图 (4) V?(V??V且V???)的导出子图,记作G[V?] (5) E?(E??E且E???)的导出子图,记作G[E?]

17

实例
例2 画出K4的所有非同构的生成子图

18

补图
定义14.9 设G=<V,E>为n阶无向简单图,以V为顶点集,以 所有使G成为完全图Kn的添加边组成的集合为边集的图, 称为G的补图,记作 G . 若G? G , 则称G是自补图.

相对于K4, 求上面图中所有图的补图,并指出哪些是自补图.
问:互为自补图的两个图的边数有何关系?

19

14.2 通路与回路
定义14.11 给定图G=<V,E>(无向或有向的),G中顶点与 边的交替序列 ? = v0e1v1e2…elvl, vi?1, vi 是 ei 的端点. (1) 通路与回路:? 为通路;若 v0=vl,? 为回路,l 为回路长 度. (2) 简单通路与回路:所有边各异,? 为简单通路,又若v0=vl, ? 为简单回路 (3) 初级通路(路径)与初级回路(圈):? 中所有顶点各异,则 称? 为初级通路(路径),又若除v0=vl,所有的顶点各不相 同且所有的边各异,则称? 为初级回路(圈) (4) 复杂通路与回路:有边重复出现

20

几点说明
表示法 ① 定义表示法 ② 只用边表示法 ③ 只用顶点表示法(在简单图中) ④ 混合表示法 环(长为1的圈)的长度为1,两条平行边构成的圈长度为 2,无向简单图中,圈长?3,有向简单图中圈的长度?2. 不同的圈(以长度?3的为例) ① 定义意义下 无向图:图中长度为l(l?3)的圈,定义意义下为2l个 有向图:图中长度为l(l?3)的圈,定义意义下为l个 ② 同构意义下:长度相同的圈均为1个 试讨论l=3和l=4的情况
21

通路与回路的长度
定理14.5 在n 阶图G中,若从顶点vi 到vj(vi?vj)存在通路, 则从vi 到 vj 存在长度小于或等于n?1 的通路. 推论 在 n 阶图G中,若从顶点vi 到 vj(vi?vj)存在通路,则 从vi 到vj 存在长度小于或等于n?1的初级通路(路径).

定理14.6 在一个n 阶图G中,若存在 vi 到自身的回路,则一 定存在vi 到自身长度小于或等于 n 的回路.
推论 在一个n 阶图G中,若存在 vi 到自身的简单回路,则一 定存在长度小于或等于n 的初级回路.

22

14.3 图的连通性
无向图的连通性 (1) 顶点之间的连通关系:G=<V,E>为无向图 ① 若 vi 与 vj 之间有通路,则 vi?vj ② ?是V上的等价关系 R={<u,v>| u,v ?V且u?v} (2) G的连通性与连通分支 ① 若?u,v?V,u?v,则称G连通 ② V/R={V1,V2,…,Vk},称G[V1], G[V2], …,G[Vk]为连通分 支,其个数 p(G)=k (k?1); k=1,G连通

23

短程线与距离
(3) 短程线与距离 ① u与v之间的短程线:u?v,u与v之间长度最短的通路 ② u与v之间的距离:d(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)

24

1. 删除顶点及删除边 G?v ——从G中将v及关联的边去掉 G?V?——从G中删除V?中所有的顶点 G?e ——将e从G中去掉 G?E?——删除E?中所有边 2. 点割集与边割集 点割集与割点 定义14.16 G=<V,E>, V??V V?为点割集——p(G?V?)>p(G)且有极小性 v为割点——{v}为点割集 定义14.17 G=<V,E>, E??E E?是边割集——p(G?E?)>p(G)且有极小性 e是割边(桥)——{e}为边割集
25

无向图的连通度

点割集与割点
例3 {v1,v4},{v6}是点 割集,v6是割点. {v2,v5} 是点割集吗? {e1,e2},{e1,e3,e5,e6}, {e8}等是边割集,e8是 桥,{e7,e9,e5,e6} 是边割 集吗? 几点说明: ? Kn中无点割集,Nn中既无点割集,也无边割集,其中Nn为 n 阶零图. ? 若G 连通,E?为边割集,则 p(G?E?)=2,V?为点割集,则 p(G?V?)?2 26

点连通度与边连通度
定义14.18 G为连通非完全图 点连通度— ?(G) = min{ |V ?|?V ?为点割集 } 规定 ?(Kn) = n?1 若G非连通,?(G) = 0 若 ?(G)?k,则称G为 k-连通图 定义14.19 设G为连通图 边连通度——?(G) = min{|E?|?E?为边割集} 若G非连通,则?(G) = 0 若?(G)?r,则称G是 r 边-连通图

图中, ?=?=1,它是 1-连通图 和 1边-连通图
27

几点说明
? ?(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 ? ?, ?, ?之间的关系. 定理7.5 ?(G)??(G)??(G) 请画出一个?<?<?的无向简单图
28

有向图的连通性
定义14.20 D=<V,E>为有向图 vi ? vj(vi 可达 vj)——vi 到vj 有通路 vi ? vj(vi 与vj 相互可达) 性质 ? 具有自反性(vi ? vi)、传递性 ? 具有自反性、对称性、传递性 vi 到vj 的短程线与距离 类似于无向图中,只需注意距离表示法的不同 (无向图中d(vi,vj),有向图中d<vi,vj>) 及 d<vi,vj>无对称性

29

有向图的连通性及分类
定义14.22 D=<V,E>为有向图 D弱连通(连通)——基图为无向连通图 D单向连通——?vi,vj?V,vi?vj 或 vj?vi D强连通——?vi,vj?V,vi?vj 易知,强连通?单向连通?弱连通 判别法 定理14.8 D强连通当且仅当D中存在经过每个顶点至少一次 的回路 定理14.9 D单向连通当且仅当D中存在经过每个顶点至少一 次的通路
30

扩大路径法
无向图中 设G=<V,E>为 n 阶无向图,E??. 设 ?l 为G中一条路径,若 此路径的始点或终点与通路外的顶点相邻,就将它们扩到通 路中来,继续这一过程,直到最后得到的通路的两个端点不 与通路外的顶点相邻为止. 设最后得到的路径为?l+k(长度 为 l 的路径扩大成了长度为 l+k 的路径),称?l+k为“极大路 径”,称使用此种方法证明问题的方法为“扩大路径法”. 有向图中类似讨论,只需注意,在每步扩大中保证有向边方 向的一致性.

31

实例
(1) (2)

(3)

(4)

由某条路径扩大出的极大路径不惟一,极大路径不一定是 图中最长的路径 上图中,(1)中实线边所示的长为2的初始路径?,(2),(3),(4) 中实线边所示的都是它扩展成的极大路径. 还能找到另外的极大路径吗?
32

扩大路径法的应用
例4 设 G 为 n(n?3)阶无向简单图,? ? 2,证明G 中存在 长度 ? ?+1 的圈. 证 设 ? = v0v1…vl 是由初始路径 ?0 用扩大路径法的得到的极 大路径,则 l ? ? (为什么?). 因为v0 不与 ? 外顶点相邻,又 d(v0) ? ?,因而在 ?上除 v1 外,至少还存在 ??1个顶点与 v0 相邻. 设 vx 是离 v0 最远的顶 点,于是 v0v1…vxv0 为 G 中长度 ? ?+1 的圈.

33

二部图
定义14.23 设 G=<V,E>为一个无向图,若能将 V分成 V1和V2 (V1?V2=V,V1?V2=?),使得 G 中的每条边的两个端点都是 一个属于V1,另一个属于V2,则称 G 为二部图 ( 或称二分 图、偶图等 ),称V1和V2为互补顶点子集,常将二部图G 记为<V1,V2,E>.
又若G是简单二部图,V1中每个顶点均与V2中所有的顶点相 邻,则称G为完全二部图,记为 Kr,s,其中r=|V1|,s=|V2|. 注意,n 阶零图为二部图.

34

二部图的判别法
定理14.10 无向图G=<V,E>是二部图当且仅当G中无奇圈 由定理14.10可知图9中各图都是二部图,哪些是完全二部 图?哪些图是同构的?

35

14.4 图的矩阵表示
无向图的关联矩阵(对图无限制) 定义14.24 无向图G=<V,E>,|V|=n,|E|=m,令 mij为 vi 与 ej 的关联次数,称(mij)n?m为G 的关联矩阵,记为M(G). 性质 (1)

? m ? 2 ( j ? 1,2,...,m ) ( 2) ? m ? d ( v ) ( i ? 1, 2,...,n) ( 3) ? m ? 2m
n i ?1 m ij j ?1 ij i ij i, j

(4) 平 行 边 的 列 相 同

36

有向图的关联矩阵
有向图的关联矩阵(无环有向图) 定义14.25 有向图D=<V,E>,令 则称 (mij)n?m为D的关联矩阵,记为M(D).

性质

? 1 , vi为ej的 始 点 ? mij ? ? 0, vi与ej不 关 联 ?? 1, v 为e 的 终 点 i j ?
n

( 1 )? m ? 0 i ? 1 ij
m

(j? 1 , 2 ,..., m )
m

? ? ( 2 )? ( m ? 1 ) ? d ( v ), ( m ? ? 1 ) ? d ( v 1 , 2 ,..., n ? ij i ij i), i? j ? 1 j ? 1

( 3 )? m 0 ij?

(4) 平行边对应的列相同

i ,j

37

有向图的邻接矩阵(无限制)
定义14.26 设有向图D=<V,E>, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令为顶点 vi 邻接到顶点 vj 边的条数,称为D的邻接矩 阵,记作A(D),或简记为A. 性质

(1) (2) (3) (4)

(1) ? a ? d (vi ), i ? 1,2,...,n ?j?1 ij n (1) ? a ? d (vj ), ?i?1 ij n

j ? 1,2,...,n

(1) a 1的 通 路 数 ? ij ? m ? ? ? D中 长 度 为 i, j (1) a 1的 回 路 数 ?i?1 ii ? ? ? D中 长 度 为 n
38

邻接矩阵的应用
定理14.11 设 A为有向图 D 的邻接矩阵,V={v1, v2, …, vn}为 顶点集,则 A 的 l 次幂 Al(l?1)中元素
a ij( l )

a ii( l )

为D中vi 到vj长度为 l 的通路数,其中 为vi到自身长度为 l 的回路数,而
a ij( l ) 为D中长度为 l 的通路总数,

??

n

n

i?1 j?1

?

n

a ii( l ) 为D 中长度为 l 的回路总数.

i?1

推论 设Bl=A+A2+…+Al(l?1),则 n n Bl中元素 ? ? b ij( l ) 为D中长度小于或等于 l 的通路数.

?

n

i?1 j?1

b ii( l ) 为D中长度小于或等于 l 的回路数
39

i?1

实例
例5 有向图D如图所示,求 A, A2, A3, A4,并回答诸问题: (1) D 中长度为1, 2, 3, 4的通路各有多少条?其中回路分别为多 少条? (2) D 中长度小于或等于4的通路为多少条?其中有多少条回路?

40

?1 ?2 A?? ?1 ? ?1 ?1 ?4 A3 ? ? ?3 ? ?3

0 0 0 0 0 0 0 0

0 1 0 1 0 1 0 1

0? 0? ? 1? ? 0? 0? 0? ? 1? ? 0?

实例求解
?1 ?3 A2 ? ? ?2 ? ?2

0 0 0 0 0 0 0 0

0 0 1 0 0 0 1 0

?1 ?5 A4 ? ? ?4 ? ?4

0? 1? ? 0? ? 1? 0? 1? ? 0? ? 1?

(1) D中长度为1的通路为8条,其中有1条是回路. D中长度为2的通路为11条,其中有3条是回路. D中长度为3和4的通路分别为14和17条,回路分别 为1与3条. (2) D中长度小于等于4的通路为50条,其中有8条是回路.

41

有向图的可达矩阵(无限制)
定义14.27 设D=<V,E>为有向图. V={v1, v2, …, vn}, 令

, v vj ?0 i可达 p ij ?? 1 , 否则 ?

称 (pij)n?n 为D的可达矩阵,记作P(D),简记为P. 由于?vi?V,vi?vi,所以P(D)主对角线上的元素全为1. 由定义不难看出, D 强连通当且仅当 P(D)为全1矩阵. 下图所示有向图 D 的可达矩阵为

?1 ?1 P ?? ?1 ? ?1

0 1 0 0

0 1 1 1

0? 1? ? 1? ? 1?

42

第十四章 习题课
主要内容 ? 无向图、有向图、关联与相邻、简单图、完全图、正则图、 子图、补图;握手定理与推论;图的同构 ? 通路与回路及其分类 ? 无向图的连通性与连通度 ? 有向图的连通性及其分类 ? 图的矩阵表示

43

基本要求
? 深刻理解握手定理及推论的内容并能灵活地应用它们 ? 深刻理解图同构、简单图、完全图、正则图、子图、补图、 二部图的概念以及它们的性质及相互之间的关系 ? 记住通路与回路的定义、分类及表示法 ? 深刻理解与无向图连通性、连通度有关的诸多概念 ? 会判别有向图连通性的类型 ? 熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方 法,会求可达矩阵

44

练习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)它们都满足要求.
方法二:反证法 否则,由握手定理推论可知,“G至多有4个5度顶点并且 至多有4个6度顶点”,这与G是 9 阶图矛盾.
45

练习2
2.数组2, 2, 2, 2, 3, 3能简单图化吗?若能,画出尽可能多的 非同构的图来. 只要能画出6 阶无向简单图,就说明它可简单图化. 下图的4 个图都以此数列为度数列,请证明它们彼此不同构,都是K6 的子图.

46

练习3
3.设D=<V,E>为有向简单图,已知 ?(D) ? 2,?+(D)>0, ??(D)>0,证明D中存在长度 ? max{?+,??}+1的圈. 用扩大路径法证明. 情况一:?? ? ?+. 证明D中存在长度 ? ??+1的圈. 设 ? = v0v1…vl为极大路径,则l ? ??(为什么?).由于d?(v0)? ??, ,v v v ... v v v v i i2 ,..., i ? 邻接到v0,于是 v 所以在 ? 上存在 v 0 1 i... i ... i ? 0 1 ? ?
1 2

为D中长度 ? ??+1的有向圈

情况二:?+ ? ??,只需注意d+(vl) ? ? + .

PLAY
47

练习4
4.有向图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的可达矩阵.

48

解答
(1) D中有3种非同构的圈,长度分别为1,2,3,请画出它们的 图形. (2) D中有3种非圈的非同构的简单回路,它们的长度分别为 4,5,6. 请画出它们的图形来. (3) D是强连通的(为什么?) 为解(4)—(8),只需先求D的邻接矩阵的前4次幂.
?1 ?0 A?? ?1 ? ?0 ?3 ?1 A3 ? ? ?2 ? ?1 2 0 0? 0 1 0? ? 0 0 1? ? 0 1 0? 2 2 2? 2 1 0? ? 2 2 1? ? 2 1 0? ?1 ?1 A2 ? ? ?1 ? ?1 ?5 ?2 A4 ? ? ?4 ? ?2 2 0 2 0 6 2 4 2 2 0? 0 1? ? 1 0? ? 0 1? 4 2? 2 1? ? 3 2? ? 2 1?

49

解答
(4) v1到v4长度为1,2,3,4的通路数分别为0,0,2,2. 其中只有 长度为4的两条是非初级的简单通路(定义意义下),见 下图所示.

50

解答
(5) v1到v1长度为1,2,3,4的回路数分别为1,1,3,5. 其中长度为1 的是初级的(环);长度为2的是复杂的;长度为3的中有1 条是复杂的,2条是初级的;长度为4的有1条是复杂的, 有4条是非初级的简单回路. 请在图中行遍以上各回路.

(6) 长度为4的通路(不含回路)为33条.
(7) 长度为4的回路为11条. (8) 长度?4的通路88条,其中22条为回路.

(9) 4?4的全1矩阵.

51


相关文档

离散数学第十四章图论基本概念
离散数学第十四章图论基本概念-PPT精选文档
离散数学--第8章+图论-7-文档资料
离散数学--第7章+图论-1图的基本概念
新编文档-离散数学第10章 图概念与表示-精品文档
离散数学—图论1216版-精品文档
离散数学--第7章+图论-2-文档资料
离散数学CH04_图论_基本概念
《图论第2章 基本概念-PPT精品文档
新编文档-离散数学第8章 图论8树-精品文档
学霸百科
新词新语
电脑版 | 学霸百科