发布时间 : 星期三 文章系统分析师复习资料（数学基础知识）更新完毕开始阅读
定义
M(G5)??mij?n，其中当vi为ej的始点时，mij=1；当vi为ej的终点时，mij=－1；当vI
与ej不关联时，mij=0. 于是所求关联矩阵为
e1e2e3e4e5e6?1??0?0??0?1??
a?1?1000?b??11100M(G5)?c?00?110?d?000?11?0000?1e?
(4) 图G5的邻接矩阵为
?0?1??0??0?A(G5)=?11000??1?00100????00010???0001??10000??. A2(G5)=??00100??0?11010????10001???0000??01000??，A3(G5)=??11010?0101??0000??1000?0100??
从A3(G5)可知，从结点b到结点c,d各有1条、0条长度为3的通路. 从b到b长度为2的回
路有1条；长度为3的通路共2条.
??ai?1j?155(3)ij=9条；长度不超过3的通路共有22条，其中回路是
?1?1??0??1?(5) A4(G5)=?00100??2?31010????11000???0100??21010??, B4= A(G5)+ A2(G5)+ A3(G5)+ A4(G5)=??22210?2221??1011??1101?2110??,
有向图G5的可达矩阵.只需将B4中当bij?0时改为1，当bij=0时，不变，bii均改为1，将
得到可达矩阵，于是G5的可达矩阵为
abcda?1?b?1P(G5)?c?1?d?1?e?1
e
1110??1111?1111??1111??1111?
例5.6 单项选择题
1．在图G＝
21
(A) deg(vi)=2?E? (B) deg(vi)=?E? (C)v?V答案：(C)
解答：见握手定理.
?deg(v)?2E (D)
?deg(v)?Ev?V
2. 设G是n个结点的无向完全图，则图G的边数为( )；设D是n个结点的有向完全图，则图D的边数为( )
(A) n(n－1) (B) n(n+1) (C) n(n－1)/2 (D) n(n+1)/2 答案：(C) （A）
?n?n(n?1)??2???2解答：G有n个结点，任意两点有一条边，共有??条边. 故选择(C);有向图
?n???2??D中，任意两点有两条方向相反的边，才能互通，因此n个结点要有2×??
?2?n(n?1)?n(n?1)2条，故选择(A).
3. 仅有一个结点的图称为( )，当然也是( ) (A) 零图 (B) 平凡图 (C) 补图 (D) 子图 答案：(B)， (A)
解答：见定义，只有一个结点的图称为平凡图；有孤立结点组成的图称为零图. 4. 设G＝
解答：因为G中无平行边和环，任何结点最多有n－1条边与其相关联，最大度数小于或
等于n－1. 故选择(A)
5. 图G与G?的结点和边分别存在一一对应关系，是G≌G?(同构)的( ) (A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件 答案：(B)
解答：见图的同构定义.
6. 设V?{a,b,c,d}，则与V能构成强连通图的边集合是( ) (A) (A) E?{?a,d?,?b,a?,?b,d?,?c,b?,?d,c?} (B) (B) E?{?a,d?,?b,a?,?b,c?,?b,d?,?d,c?}
22
(C) (C) E?{?a,c?,?b,a?,?b,c?,?d,a?,?d,c?} (D) (D) E?{?a,b?,?a,c?,?a,d?,?b,d?,?c,d?} 答案：(A)
解答：有向图G任何一对结点间都互相可达，称该图是强连通的. (A)所给的边的集合存在一个通过所有结点的通路. 故选择(A).
7.有向图的邻接矩阵中，行元素之和是对应结点的( )，列元素之和是对应结点的( ) (A)度数 (B) 出度 (C)最大度数 (D) 入度 答案：(B)，(D)
解答：见邻接矩阵的定义.
8、给定无向图如图5－5所示，下面给出的顶点 集子集中，不是点割集的是（ ） (A) {b,d} (B) {d} (C) {e} (D) {f,h}
答案：(A)
a? f ?
b? ? ? ?g
d e
c ? ?h 图5－5
解答：易知d,e是割点，{f,h}满足点割集的定义，而{b,d}含有割点，它不可能是点割集. 选择(A).
例5.7 填空题
1. 设图G＝
答案：V??V或E??E;V??V,E??E 解答：见真子图和生成子图的定义.
2. 在无向图中，结点间的连通关系具有 性， 性， 性，
是 关系.
答案：自反性，对称性，传递性，等价. 解答：见图的连通性质.
3. 图的通路中边的数目称为 . 结点不重复的通路是 通路. 边不重复的通路是 通路.
答案：通路出度；初级；简单. 解答：见有关定义.
4. 给定无向图如图5－5所示，那么该图的
割边(桥)是
答案： {d,e}
解答：易知边(d,e)是割边，
23
? ? ? ? ? ? ? ? ? ? ? ? G1 G2 图5－6
3. 求图G(如图5－7)的点割集、割点、边割集和割边.
4. 判定图5－8给出的两个图，是否为弱连通，单侧连通，强连通？
5.设有向图D(如图5－9), 求图D从v2到v4长度分别为1,2,3,4的通路各有几条. v ? ? v ? v v1 ? e 6 v ?v4 e1 v6 e?v7 e 3 e 8 412 111
e7 e9 e2 ? ? v10 ? e 5 ?v8 ee3 10 v2? ? v5 ?v9
v2? ?v4
图5－7
v1? ? v4
v4? ? v3 ? v3
D1 D2 图5－8
v2? ? v3
图5－9
三、练习题
1. 在有21条边的无向图中，有多少个结点，其中3个4度结点，其余均为3度结点. 2. 判定图5－6所示二图是否同构？
6. 设图G＝
四、练习题答案
V?n,E?m是简单图，则
?(G)?2m??(G)n.
1. 13个结点. 边数m=21, 有42＝3×4＋3x(x个3度结点)，
2. 在G1中，一度结点有3个，在G2中一度结点有4个. 即度数相同的结点数不同，故
G1与G2不同构.
3.点割集：V?＝{v4,v5,v10},割点：v3,v6,v7,v8；边割集：E?＝{e1,e2,e3}或{ e8,e9,e10},割边：e4,e5 e6,e7,e11等.
4. (1) 将D1，D2中边的方向略去后，显然得到两个连通的无向图，故D1，D2都
是弱连通.
(2) 在D1中v1到v2有一条有向路，故v1可达v2，类似可知，v1可达v2，v1可达
24