第七章 二元关系
4、
解： （1） },,{)(4321v v v v N =
},,,{)(14321v v v v v N =
（2）},{)(431u u u =Γ-
},{)(321u u u =Γ+
},,{)(4321u u u u N =
},,,{)(14321u u u u u N =
8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？
解：由握手定理图G 的度数之和为：1262=?
设2度点x 个，则1221513=+?+?x ，2=x ，该图有4个顶点. 13、解：说明每个顶点都是2度，从而有6条边。 总共有11种：（1）简单图有2种：
；
（2）非简单图有9种：
；
；；
；
；；
17、画出3阶有向完全图的所有非同构的子图，指出哪些是生成子图，哪些是3阶竞赛图？
解：总共有19种子图：
其中生成子图（即有3个顶点的）共有14种：
（以上两幅同时也是3阶竞赛图）
2阶子图有3种：
1阶子图有1种： N 1 0阶子图有1种：Φ.
20、已知n 阶无向简单图G 有m 条边，试求G 的补图G 的边数m '。
解：n 阶无向完全图总共有2
)
1(-n n 条边， 所以G 的边数是 m n n m --='2
)
1(.
21、无向图G 如下图
(1)求G 的全部点割集与边割集，指出其中的割点和桥； (2) 求G 的点连通度)(G k 与边连通度)(G λ。
a c
解：点割集: {a ,c},{d},割点有d ；
边割集{e 2,e 3},{ e 3,e 4},{e 1, e 2},{ e 1,e 4}{ e 1, e 3},{ e 2,e 4},{e 5}； 割边有e 5
)(G k =)(G λ=1
23、求G 的点连通度)(G k 、边连通度)(G λ与最小度数)(G δ。
解：2)(=G k 、3)(=G λ 、4)(=G δ 44、
（1)v 1到v 4长度为1, 2, 3, 4的通路数分别为0条, 0条, 2条, 2条 （2) v 1到v 1长度为1, 2, 3, 4的回路数分别为1条, 1条, 3条, 5条; (3)D 中长度为4的通路(不含回路)共33条, 长度为4的回路共11条; (4) D 中长度小于或等于4的通路共88条, 其中22条是回路;
(5) ??
???
????
???=1111
11111111
1111)(D P 45、有向图D 如图
(1)求2v 到5v 长度为1，2，3，4的通路数；
(2)求5v 到5v 长度为1，2，3，4的回路数； (3)求D 中长度为4的通路数； (4)求D 中长度小于或等于4的回路数； (5)写出D 的可达矩阵。
v3
v4
解：有向图D 的邻接矩阵为：
(1)2v 到5v 长度为1，2，3，4的通路数为0,2,0,0； (2)5v 到5v 长度为1，2，3，4的回路数为0,0,4,0； (3)D 中长度为4的通路数为32； (4)D 中长度小于或等于4的回路数10；
(5) D 的可达矩阵???
???
?
?
?
?=111111*********
11111
11111P
法二：
???????? ??=010100010110000
0010110000
A ，????????
?
?=002022000
00101
020*******
02A ???
???
?
?
?
?=400000202
00020
2020200020
23A
???????? ?
?=040400040440000
00404400004A ???
???
?
?
?
?=+++452522252
45121
2225255121
0432A A A A