第六章 代数系统
6.1第129页
1． 证明：
任取x , y ∈I ，g (y , x ) =算*是可交换的； 任取x , y , z ∈I ，
y *x =y +x -yx =x +y -xy =g (x , y ) ，因此，二元运
g (x , g (y , z )) =x *(y *z )
=x *(y +z -yz )
=x +y +z -yz -x (y +z -yz ) =x +y +z -xy -xz -yz +xyz
g (g (x , y ), z )
=(x *y ) *z
=(x +y -xy ) *z
=x +y -xy +z -(x +y -xy ) z =x +y +z -xy -xz -yz +xyz =g (x , g (y , z ))
因此，运算*是可结合的。
该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。 2．
证明：任取x , y ∈N , x ≠是可交换的。 任取
y ，由x *y =x , y *x =y ≠x 知，y *x ≠x *y ，*运算不(x *y ) *=z
x =*z
，x x *(y *z ) =x *y =x 知，
x , y , z ∈N
，由
(x *y ) *=z *运算是可结合的。 x *(y ，*z
任取x ∈N ，x *x =x ，可知N 中的所有元素都是等幂的。
*运算有右么元，任取x , y ∈N ，x *y =*运算没有左么元。
x ，知N 中的所有元素都是右么元。
证明：采用反证法。假定e 为*运算的左么元，取b ∈N , b ≠e ，由*的运算公式知e *b =e ，由么元的性质知，e *b =b ，得e =b ，这与b ≠e 相矛盾，因此，*运算没有左么元。
3．解：
① 任取x , y ∈I , x ≠y
x *y =x 和y 的最小公倍数
y *x =y 和x 的最小公倍数=x 和y 的最小公倍数
因此对于任意的x , y ∈I , x ≠y 都有x *y =y *x ，即二元运算*是可交换的。 ② 任取x , y , z ∈I ,
（x *y ）*z =(x 和y 的最小公倍数) *z =x , y , z 的最小公倍数 x *（y *z ) =x *(y 和z 的最小公倍数) =x , y , z 的最小公倍数
（x *y ）*z =x *（y *z ) ，即二元运算*是可结合的。 因此对于任意的x ，y ，z ，都有
③ 设幺元为e
x *e =e *x =x 和e 的最小公倍数=x ，则e =1，即幺元为1.
④ 对于所有的元素x ∈I ，都有x *x =x ，所以所有元素都是等幂的。
4．解：设X =n
① 设f 是X 上的二元运算，则f 是一个从X →X 的映射。 求X 上有多少个二元运算即相当于求这样的映射的个数。
22n n
由于X =n ，映射f 的个数为n ，即X 上有n 个二元运算。
2
2
2
② 可交换即f =f 设集合X ={1, 2, 3, 4}，要求
X
上可交换的二元运算的个数，即相当于求映射f 的个数，
f :A →X ，其中：
A ={, , }
具体如下图所示：
, , , , 1, 2, 3 4X A
此时映射f 的个数N 4
=4
6+4
=4
2C 4+4
推广到X 有n 个元素时，映射f 的个数N n ③ 单位元素即幺元，若存在必唯一。 设集合X ={1, 2, 3, 4}，若幺元为1，则有
=n
2
C n +n
→1, →2
, →3
, →4
此时的二元运算的个数相当于求映射f :A →X 的个数，其中：
A
X
1 2 34
(4-1) 2
映射f :A →X 的个数为N =4=4
9
幺元为2，3，4时同理，N 4
=4⋅4=C ⋅4
9
14
9
14
(4-1) 2
个有单位元素的二元运算。
因此集合X ={1, 2, 3, 4}上有N 4
=4⋅4=C ⋅4
(4-1) 2
推广到X 有n 个元素时，具有单位元素的二元运算的个数为N n
5．解：任取a 1, a 2, a 3∈R ①
=C ⋅n
1n
(n -1) 2
。
a 1*a 2=a 1-a 2
a 2*a 1=a 2-a 1=a 1-a 2=a 1*a 2
对于任意的a 1, a 2∈R 都有a 2*a 1=a 1*a 2，故二元运算*是可交换的。
(a 1*a 2)*a 3=a 1-a 2)*a 3=
若a 1
a 1-a 2-a 3
a 1*(a 2*a 3) =a 1*(a 2-a 3) =a 1-a 2-a 3
=1, a 2=-3, a 3=-2
(a 1*a 2)*a 3=6，a 1*(a 2*a 3) =0，此时(a 1*a 2)*a 3≠a 1*(a 2*a 3)
故二元运算*是不可结合的。
不存在这样e 使得任意的x ∈R 都有x *e =x -e =x ， 因此，二元运算*不含幺元。 ②a 1*a 2
=(a 1+a 2)/2
a 2*a 1=(a 2+a 1)/2=(a 1+a 2)/2=a 1*a 2
对于任意的a 1, a 2∈R 都有a 2*a 1=a 1*a 2，故二元运算*是可交换的。
a 1+a 2
+a 3
a +a +2a 3
(a 1*a 2)*a 3=((a 1+a 2)/2)*a 3==12
24a 1*(a 2*a 3) =a 1*((a 2+a 3)/2)=
故二元运算*是不可结合的。
不存在这样e 使得任意的x ∈R 都有x *e =(x +e ) /2=x ，
a 1+
a 2+a 3
=2a 1+a 2+a 3≠a 1+a 2+2a 3244
因此，二元运算*不含幺元。 ③
a 1*a 2=a 1/a 2
a 2*a 1=a 2/a 1≠a 1*a 2
因此，二元运算*是不可交换的。
(a 1*a 2)*a 3=(a 1/a 2)*a 3=a 1/a 2=
a 3a 1
a 2a 3
a 1a 3a 1a 1
a 1*(a 2*a 3) =a 1*(a 2/a 3) ==≠
a 2/a 3a 2a 2a 3
故二元运算*是不可结合的。
由于二元运算*不是可交换的，所以不存在这样e 使得任意的x ∈R 都有x *e =e *x =x /e =x ， 因此，二元运算*不含幺元。
6．设x 是X 中的任意元素。 由于二元运算*是可结合的， 故(x *x ) *x =x *(x *x )
又对于任意的x , y ∈X ，若x *y =y *x ，则y =x 故x *x =x
即对于X 中的任意元素，都有x *x =x ， 所以X 中的 每一个元素都是等幂的。
6.2第137页
4． 证明：
首先，U 和V 都只含有一个二元运算，因此是同类型的； 第二，
f 的定义域是自然数集合N ，值域是{0,1}，是V 定义域的子集。
第三，验证是否运算的像等于像的运算。 任取x , y ∈N ，分情况讨论： （1） x 和y 都可以表示成2，设x =2
k
k 1
, y =2k 2，
那么
f (x y ) =f (2k 12k 2) =f (2k 1+k 2) =1，f (x ) =f (y ) =1
f (x ) f (y ) =11=1=f (x y )
（2） x 和y 都不能表示成2，那么x
k
y 也不能表示成2k
f (x y ) =0, f (x ) =f (y ) =0 f (x ) f (y ) =00=0=f (x y )
（3） x 可以表示成2，y 不能表示成2，那么x
k
k
y 也不能表示成2k
f (x y ) =0, f (x ) =1, f (y ) =0 f (x ) f (y ) =10=0=f (x y )
（4） x 不可以表示成2，y 能表示成2，那么x
k
k
y 也不能表示成2k
f (x y ) =0, f (x ) =0, f (y ) =1 f (x ) f (y ) =01=0=f (x y )
可知，无论x 和y 如何取值，都能够保证综上所述，5．
证明：设U =〈{a , b , c },*〉，V =〈{1,2,3},⊕〉
首先，U 和V 都仅有一个二元运算，因此U 和V 是同类型的； 第二，U 和V 的定义域大小相同，具备构成双射函数的条件；
第三，寻找特异元素，U 中么元是a ，右零元是c ，三个元素都是等幂元；V 中么元是3，右零元是1，三个元素都是等幂元。 第四，在U 和V 的定义域之间构造双射函数把*运算表中的元素都用f 下的像点代替，得
调整表头的顺序为1，2，3，转变为下表
f (x ) f (y ) =f (x y ) 。
f
是U 到V 的同态映射。
f
，使得
f (a ) =3, f (b ) =2, f (c ) =1。
跟V 中⊕运算表完全相同，因此代数系统〈{a , b , c },*〉和〈{1,2,3},⊕〉是同构的。 6. 证明：
(1) 两个代数系统都只存在一个二元运算，故满足同型。 (2) 构造函数f ，使得(3) 对于任意的X , Y ∈ρ(X )
故
，所以满足运算的像=像的运算。
，显然f 是双射函数。
由(1),(2),(3)可知，两代数系统是同构的。
7. 解：
f p (X ) =(px ) mod 6, p =0, 1, 2, 3, 4, 5
当p =0时，f 0零同态；
当p =1时，f 1恒等映射，自同态；
当p =2时，f 2={, , , , , }； 当p =3时，f 3={, , , , , }； 当p =4时，f 4={, , , , , }； 当p =5时，f 5={, , , , , }自同构。
8. 证明：x -1=0的n 个复数根可表示成：
n
2π
x k i =cos k i α
+sin k i αi , α=, k i =0, 1, 2,.... n -1
n
(1) 与都含有一个二元运算，故为同型的。 (2) 与
定义域大小相同，具备构成双射函数的条件。
(3) 构造双射函数
f (x k i ) =k i (mod n )
对于任意的x k 1, x k 2∈E n ，
f (x k 1∙x k 2) =f ((cosk 1α+sin k 1αi ) ∙(cosk 2α+sin k 2αi ))
=f (cosk 1α⋅cos k 2α+cos k 1αsin k 2αi +sin k 1cos k 2αi +sin k 1sin k 2i 2) =f (cosk 1α⋅cos k 2α+cos k 1αsin k 2αi +sin k 1cos k 2αi -sin k 1sin k 2) =f (cos(k 1+k 2) α+sin(k 1+k 2) αi ) =(k 1+k 2)(modn )
f (x k 1) +n f (x k 2) =k 1(modn ) +n k 2(modn ) =(k 1(modn ) +k 2(modn ))(modn ) =(k 1+k 2)(modn )
因此，f (x k 1∙x k 2) =f (x k 1) +n f (x k 2) 。 由(1),(2),(3)可知，
9．证明：
(1) g 是代数系统到当的同态映射 ∴g [X ]⊆Y
又 是的子代数
同构于
。
∴X 1⊆X ∴g [X 1]⊆Y
(2) 对于∀a , b ∈g [X 1]，必存在X a , X b ∈X 1， 使得g [X a ]=a ，g [X b ]=b ,
a ∙b =g [X a ]∙g [X b ]
由于g 为代数系统到当的同态映射
∴g [X a ]∙g [X b ]=g [X a *X b ]
X a , X b ∈X 1，又 是的子代数
故X 1对*运算封闭
∴X a *X b ∈X 1
∴g [X a *X b ]∈g [X 1]，即a ∙b ∈g [X 1] ∴g [X 1]对∙运算满足封闭性。
由(1),(2),(3)可知, 为的子代数。
6.3第141页
1．解：
解：首先，判断≡m 是否是等价关系。任取x ∈I ，由于x -是自反的；任取x , y ∈I ，若x ≡m
x =0⋅m ，因此x ≡m x ，≡m
y ，即x -y =a ⋅m （a ∈I ），则y -x =-a ⋅m ，
y ≡m x ，因此≡m 是对称的；任取x , y , z ∈I ，若x ≡m y , y ≡m z ，则x -y =a ⋅m
（a ∈I ），y -z
=b ⋅m （b ∈I ），于是x -z =(x -y ) +(y -z ) =(a +b ) ⋅m ，
a +b ∈I ，因此x ≡m z ，可知≡m 是可传递的。因此，≡m 是等价关系。
其次，判断≡m 关于*是否满足代换性质。 任取x , y ∈I ，若x ≡m
y ，即存在某个p ∈I ，满足x -y =p ⋅m
*(x ) =x k (modm ) *(y ) =y k (modm )
则
*(x ) =(y +p ⋅m ) k (modm )
1k -1
=C k 0y k +C k y (p ⋅m ) 1+C k 2y k -2(p ⋅m ) 2+1k -1=y k +p ⋅m ⋅(C k y +C k 2y k -2(p ⋅m ) 1+
+C k k y 0(p ⋅m ) k
+C k k y 0(p ⋅m ) k -1)
于是
1k -1
*(x ) -*(y ) =p ⋅m ⋅(C k y +C k 2y k -2(p ⋅m ) 1++C k k y 0(p ⋅m ) k -1) +C y (p ⋅m ) ) ⋅m
k
+k
(C
-k
k k
k -1
=p ⋅(C y
由于
1k -1
p ⋅(k C y +
1
k
k -1
+C y
2k
k -2
(p ⋅m ) +
1
k
2k -1C (y 2⋅) p +m
⋅y ) ，p ) 因∈m 此，I
*(x ) ≡m *(y ) ，≡m 关于*是满足代换性质。
综上所述，≡m 是U 上的同余关系。
2. 解：
（1）对于+运算，在二元运算下，任取
x 1, x 2, y 1, y 2∈I ，验证下式是否成立
x 1Ry 1x 2Ry 2
⇒
取
⎫⎬2行⎭
x 1+x 2Ry 1+y 2
1
1，2
x 1=1, x 2=2, y 1=1, y 2=-2，可知满足x Ry
x Ry 2，但|x 1+x 2|≠|y 1+y 2|
，
即x 1+x 2y 1+y 2。可知对于运算+，R 不满足代换性质。
（2）对于⋅运算，在二元运算下，任取
x 1, x 2, y 1, y 2∈I ，
y 1|,|x 2|=|y 2|
若x 1Ry 1，x 2Ry 2，则必然满足|x 1|=|于是|x 1⋅x 2|=|x 1|⋅|x 2|=|可得x 1⋅x 2Ry 1⋅y 2。
y 1|⋅|y 2|=|y 1⋅y 2|
由x 1, x 2, y 1, y 2取值的任意性可知，对于运算⋅，R 满足代换性质。
3．证明：
(1) 对于∀x 1, x 2, y 1, y 2，有x 1Ry 1, x 2Ry 2
由于R 对+3具有代换性质，所以有(x 1+x 1) R (y 1+y 1) 由此可知：
(x 1+3x 1+3... +3x 1) R (y 1+3y 1+3... +3y 1) ⇒x 1⋅3x 2Ry 1⋅3x 2
x 2个x 1
同理可知：
x 2个y 1
(x 2+3x 2+3... +3x 2) R (y 2+3y 2+3... +3y 2) ⇒y 1⋅3x 2Ry 1⋅3y 2
y 1个x 2
y 2个y 1
因R 是等价关系，故是可传递的，所以有x 1⋅3x 2Ry 1⋅3y 2 所以R 对⋅3具有代换性质。
(2) S ={, , , , }对⋅3具有代换性质，
但对+3不具有代换性质，因+3=∉S
4．设代数系统V =，R 1, R 2为同余关系。 (1)即证：R 1 R 2为同余关系 证明：R 1 R 2为等价关系
若w ∈Ω对任意
a 1, b 1, a 2, b 2,... a n w , b n w ∈G
R 2) b n w
a n w R 1b n w a n w R 2b n w
有a 1(R 1 R 2) b 1, a 2(R 1 R 2) b 2, …a n w (R 1 则a 1R 1b 1， a 2R 1b 2，…
a 1R 2b 1， a 2R 2b 2，…
R 1 R 2为同余关系
∴w () R 1w () ∴w () R 2w () ∴w () R 1 R 2w ()
所以R 1 R 2为同余关系。 (2) R 1 R 2为等价关系
若w ∈Ω对任意
a 1, b 1, a 2, b 2,... a n w , b n w ∈G
w
有a 1(R 1 R 2) b 1, a 2(R 1 R 2) b 2, …a n w (R 1 R 2) b n 未必有a 1R 1b 1， a 2R 1b 2，…
a n w R 1b n w
a 1R 2b 1， a 2R 2b 2，…
因此，可能不满足代换性质
a n w R 2b n w
所以R 1 R 2未必是同余关系。
5．
（1）xRy , 当且仅当(x
=0, y 1=3, x 2=-1, y 2=-2, 则x 1Ry 1, x 2Ry 2，
=-10，因此x 1+x 2y 1+y 2，不满足代换性质。
（2）xRy , 当且仅当x -y
x =0, y =9, z =15，则xRy
，
yRz
，但
|x -z |=15>10，x z ，R 不满足可传递性，不是等价关系。
（3）xRy , 当且仅当(x =y =0) ∨(x ≠0∧y ≠0) 解：R 不是〈I , +〉上的同余关系，取取x 1但是x 1+x 2
=-3, y 1=2, x 2=3, y 2=2, 则x 1Ry 1, x 2Ry 2，
=0，y 1+y 2=4≠0，因此x 1+x 2y 1+y 2，不满足代换性质。
（4）xRy , 当且仅当x ≥y
解：R 不是〈I , +〉上的同余关系，取x =9, y =8，则xRy ，但y x ，即y 足对称性，不是等价关系。
x ，R 不满
6.4第143页
1.
解：
（1）设F 2⨯F 3=
>
其中，N 2⨯N 3={, , , , , }
任取
>, ∈N 2⨯N 3
⊕= =
下面通过运算表构造*运算（这里仅给出了一个运算表，另一个照推）
⊕
（2）设F 3⨯F 2=
其中，N 3⨯N 2={, , , , , }
任取
>, ∈N 3⨯N 2
⊕=
=
运算表的构造方法与上同。 2.
(1) 证明：任取, ∈X ⨯Y ，
∆=
∙和*可交换
∴∆===
2, y 2>∆
∴∆是可交换的。
(2) 任取, , ∈X ⨯Y
∆∆=
∙和*可结合
∴∆∆==∆
=∆(∆)
∴∆是可结合的。
3.
+m
0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 5 2 2 3 4 5 0 3 3 4 5 0 1 4 4 5 0 1 2 5
5 0 1 2 3 ⊕
证明：
① 与A 6都只有一个二元运算，故为同型的。
5 5 0 1 2 3 4
② 与A 6定义域大小相同，具备构成双射函数的条件。 ③ 构造双射函数
f () =0, f () =1, f () =2, f () =3, f () =4, f () =5
由上图可知，像的运算=运算的像 所以与A 6是同构的。
6.5第155页
1. （1）半群 （2）半群 （3）半群
（4）独异点，么元0
（5）不是半群，取a=b=1,c=2，则
(a -3b ) -3c =1a -3(b -3c ) =2
不满足结合律
（6）不是半群，因为||不是二元运算； （7）半群
（8）独异点，么元0 （9）半群
（10）独异点，么元为恒等关系； （11）独异点，么元为a 2.
（1）二元运算表如下图所示： GCD 1 2 3
1 1 1 1
2 1 2 1
3 1 1 3
4 1 2 1
6 1 2 3
8 1 2 1
12 1 2 3
24 1 2 3
4 1 2 1 4 2 4 4 6 1 2 3 2 6 2 6 8 1 2 1 4 2 8 4 12 1 2 3 4 6 4 12 24 1
2
3
4
6
8
12
（2）〈X X , 〉, 其中X ={1,2,3}。（假定X X
为丛X 到X 的双射函数）
解：X 到X 有6个双射函数，分别用
p 1, p 2, , p 6表示，设
X :a b c
↓↓↓
p 1:a b c
p 2:a c b
p
3:b a c
p 4:b c a p 5:c a b p 6:
c
b
a
构造运算表如下：
p 1 p 2 p 3 p 4 p 5 p 1 p 1 p 2 p 3 p 4 p 5 p 2 p 2 p 1 p 5 p 6 p 3 p 3 p 3 p 4 p 1
p 2 p 6 p 4 p 4 p 3 p 6
p 5 p 1 p 5 p 5 p 6 p 2 p 1 p 4 p 6
p 6
p 5
p 4
p 3
p 2
4 6 8 12 24
p 6 p 6 p 4 p 5 p 2 p 3 p 1
第七章 图论
6.1第164页
1. 画出图G =〈V , E , ψ〉的图示，指出其中哪些图是简单图。 （1）
v 4
不是简单图。
（2）
4
3
不是简单图。
2（3）
e 1
47
v 8
v 2
是简单图。
2. 写出图7-8的抽象数学定义。 （1）解：G =〈V , E , ψ〉，其中
V ={1, 2, 3，, E ={a , b , c , d , e , f }，
ψ={>, >, >, >, >, >}
（2）解：G =〈V , E , ψ〉，其中V ={1,2,3,4,5,6,7,8,9}，E ={a , b , c , d , e , f , g , h , i ,
j , k , l }
，
ψ={, , , , ,
, , , , , , }
3. 证明：在n 阶简单有向图中，完全有向图的边数最多，其边数为n (n -1) 。
证明：简单有向图是没有自环，没有平行边的有向图，只要两个不同的结点之间才能有边。完全有向图是每个结点的出度和入度都是n-1的简单有向图，也就是每个结点都有到其他所有结点的边，因此，完全有向图的边数最多。
在完全有向图中，所有结点的出度之和为n(n-1)，所有结点的入度之和为n(n-1)，设边的个数为m ，由握手定理可知，2m= n(n-1)+ n(n-1)，即m= n(n-1)，得证。 4. 证明：3度正则图必有偶数个结点。
证明：设三度正则图的结点个数为n ，那么所有结点的度数之和为3n ，由握手定理可知，边的个数为3n/2=1.5n，由于边的个数一定是整数，因此，n 为偶数。得证。
5. 在一次集会中，相互认识的人会彼此握手，试证明：与奇数个人握手的人数是偶数个。 证明：设集会上的人一共有m 个，可分为两部分，一部分为与奇数个人握手的人，设为x 个，另一部分为与偶数个人握手的人，为m-x 个。
由于握手是相互的，即一次握手，两个人握手的次数都加1，一共加2，因此，集会上所有人的握手次数之和为偶数。
与偶数个人握手的人，这些人的握手次数之和为，为偶数。 a 1, a 2, , a m -x 都是偶数）
与奇数个人握手的人，这些人的握手次数之和为b 1+b 2
a 1+a 2++a m -x （其中，
+
+b x （其中，b 1, b 2, , b x 为+
+b x 也要为偶数，即
基数），由于所有人的握手次数之和偶数，因此b 1+b 2
(b 1+b 2+
又因为
+b x )mod2=0
+b x )mod 2
+b x mod 2
(b 1+b 2+
=b 1mod 2+b 2mod 2+
=x mod 2
即x mod2=0，因此x 为偶数，即与奇数个人握手的人是偶数个，得证。
6. 证明：图7-7中的两个图同构。
证明：首先，给这两幅图标上对应的结点编号，如下
1
23
1'
2'
3'
4'
4
两
个
图
5
的
结
6
点
和
边
的
数
6'
目
都
5'
相
同
。假
设函数
ψ={, , , , , }，左图中相邻的结点是
1和4，1和5，1和6，2和4，2和5，2和6，3和4，3和5，3和6，对应的像点1’和4’，1’和2’，1’和6’，5’和4’，5’和2’，5’和6’，3’和5’，3’和2’，3’和6’在右图中也相邻，因此，两图同构。
7. 证明：在任意六个人中，若没有三个人彼此认识，则必有三个人彼此都不认识。 证明：分三种情况：
（1）任何一个人最多认识另外一个人 将相互认识的两个人分成一组，则至少可以分3组，每组取一个人，则这三个必不认识。 （2）任何一个人最多认识另外两个人 最糟糕的情况是当每个人都认识另外两个人时，若认识的人之间画一条线可以构成一个六边形，取不相邻的三个点即是不认识的。 （3）任何一个人最多认识另外的三个人
A
F
不妨设点A 与B,C,E 认识（用实线连接）。因为B,C,E 之间只有有两个人认识就不满足任何三个人都不认识的条件，比如B,C 认识画一条实线，那么A,B,C 就相互认识，与已知矛盾。所以B,C,E 是所求的三个互补认识的人。 （4）任何一个人最多认识两外4或5个人 该情况与（3）类似，所求的人即与A 认识的两外4或5个人中的三个人。 证毕。
8. 证明：图7-9的两个图不同构。
证明：给这两幅图标上对应的结点编号，如下：
1
e 1
21'
'e 1
2'
e 9
5
e 5
6
e 95'
'e 5
6'
e 4
e 103
e 87
e 6
e 7e 3a)
8
e 2'e 4'e 87'
'e 6
'e 7'e 3b)
8'
'e 2
e '
4
3'
4'
两个图的点数和边数相同。假设函数：
ψ={, , , , , , , }
易证：① a ）中的子图G 1=，V 1={1,2,3,4}，E 1={e 1, e 2, e 3, e 4}，
ψ1={, , , }与
G 1'=
，
b ）中的子图
，
V 1'={1', 2',3', 4'}
，
E 1'={e 1', e 2', e 3', e 4'}
ψ1'={, , , }同构。
② a ）中的子图G 2=，V 2={5,6,7,8}，E 2={e 5, e 6, e 7, e 8}，
ψ2={, , , }与
b ）中的子图
G 2'=，G 2'=，V 2'={5',6',7',8'}，E 2'={e 5', e 6', e 7', e 8'}，
ψ2'={, , , }同构。
除这两个子图以外，对应a ）中的子图G 3=1,5,7,3}，3，V 2={
E 2={e 4, e 8, e 9, e 10}，ψ2={, , , }在b ）无
中对应的同构图。因此a ）和b ）两个图不同构。
9．图7-10的两个图是否同构？说明理由。
'
b)
+-
解：对于图b ）中的点d '，其出度为：d G '(d ') =3，入度：d G '(d ') =0。而在a) 图中不存
在这样的结点。因此这两个图不同构。
10．证明：任何阶大于1的简单无向图必有两个结点的度数相等。
证明：考虑一个有n 个结点的连通图（如果有一个孤立结点，去掉孤立结点考虑联通子图）。因为是无向连通图，每个结点的最大度数是n-1，最小度数是1。即对n 个点赋值，共n-1种取值，由抽屉原理，必有两个结点的取值相同，即必有两个点的度数相同。
11．设n 阶无向图G 有m 条边，其中n k 个结点的度数为k ，其余结点的度数为k+1，证明：
n k =(k +1) n -2m 。
证明：由题意，结点数为n ，由总边数建立关系：
m =
n k ⋅k +(n -n k )(k +1)
，由此可得：n k =(k +1) n -2m 。
2
7.2第168页
1．画出K 4的所有不同的子图，并说明其中哪些是生成子图，找出互为补图的生成子图。 解：
(1)
(2)(3)
（4）
(5)
(6)(7)
其中，（1）和（7），（2）和（6），（3）和（5），（4）中的后两个图可以构成互补的生产子图。
2．设G =是完全有向图。证明：对于V 的任意非空子集V '，
G [V ']是完全有向图。
证明：（1）当V '中只有一个结点时，G [V ']是完全有向图。
（2）当V '中有多于一个结点时，对其中任意两个结点V i , V j 是V
的子集，即V i , V j ∈V 。因为图G 是完全有向图，因此V i , V j 间存在两条有向边e ij 和e ji 。G [V ']是由非空子集V '生成的子图，故e ij , e ji ∈G [V ']，即
G [V ']中任意两个结点间存在两条有向边，故G [V ']是完全有向图。
3．画出图7-15的两个图的交、并和环和。
v 1
e 1
v 2
e 2v 3
e 3
e 6
e 4
7v 4e 5
v 5
v 2
v 3
e 8
e 1
e 3
v 1
v 4
a) b)
解：
交： 并：
v 1
v 1
e 3
e e 1
v 2
e 2
e 3
e 6
e 4
e 5
v 57v 4
e 1
v 2
v 3
v 4
v 3
环和：
v 1
e 5
v 2
e 2v 3
e 8
v 4e 4
7
v 5
4．设G 是任意6阶简单无向图，证明：G 或必有一个子图是3阶无向图。
证明：取G 或任意取三个点，取与这三个点相关联的变构成一个3阶的无向子图。
5．我们称与补图同构的简单无向图为自补图。证明：每个自补图的阶能够被4整除或被4整除余数为1。
n (n -1)
, 由自补图的定义知该2
n (n -1)
图与其子图的边数相同（同构），故其边数为，由该数是整数
4
n (n -1)
=k ，n =4k or n =4k +1。故每个自补图的阶能够被4整除或得：4
证明：设图的顶点数为n ，Kn 的边数为
被4整除余数为1。
7.3第173页
1．考虑图7-21
（1）从A 至F 的路径有多少条？找出所有长度小于6的从A 至F 的路径。
解：A 到F 的路径有无数条。长度小于6的有24条。（c f h:4,c g h:4, c e i:4, b d e f h:2, b d e g h:2, b d i:4）
（2）找出从A 至F 的所有简单路径。
解：12条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i),还有一个自环，需乘以2.
（3）找出从A 至F 的所有基本路径。
解：6条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i) （4）求出从A 至F 的距离。求出该图的直径。 解：距离为3。直径为3。 （5）找出该图的所有回路。
解：AaA, AbDdEeBcA, BeEiFhCgB; BgCfB; AbDdEiFhCgBcA; BeEiFhCfB;
2．证明：图7-21中基本路径必为简单路径。
证明：基本路径要求途经的顶点不重复，简单路径要求途经的边不重复。在图7-21中，对于所有的基本路径，边不重复出现。所以基本路径必是简单路径。 3．考虑图7-22
（1）对于每个结点v ，求R (v ) 。
解：R (v 1) =R (v 2) =R (v 3) =R (v 4) ={v 1, v 2, v 3, v 4, v 5, v 6}, R (v 5) ={v 5, v 6},R (v 6) ={v 6},R (v 7) ={v 6, v 7} R (v 8) ={v 6, v 7, v 8},R (v 9) ={v 9},R (v 10) ={v 10} （2）找出所有强分支、单向分支和弱分支。
解：强分支7个，分别是{v 9},{v 10},{v 8},{v 7},{v 6},{v 5},{v 1, v 2, v 3, v 4} 单项分支4个，分别是{v 9},{v 10},{v 6, v 7, v 8},{v 1, v 2, v 3, v 4, v 5, v 6}
弱分支3个，分别是{v 9},{v 10},{v 1, v 2, v 3, v 4, v 5, v 6, v 7, v 8}
4．设v 1v 2v 3是任意无向图（有向图）G 的三个任意结点，以下三个公式是否成立？如果成立，给出证明；如果不成立，举出反例。 （1）d (v 1, v 2) ≥0，并且等号成立，当且仅当v 1=v 2。 解：成立。当v 1≠v 2时，距离必定大于1。 （2）d (v 1, v 2) =d (v 2, v 1)
解：成立。因为无向图是无方向的。
5. 证明：有向图的每个结点和每条边恰处于一个弱分支中。 反证法：若任意结点V 处于两个或两个以上的弱分支中，不妨设两个弱分支为G1, G2, 则G1, G2是G 的极大联通子图。设v ∈G 1, v ∈G 2，又G 1, G 2∈G , 故G 1, G 2联通。这与G1, G2是极大联通子图矛盾，故命题得证。
6. 有向图的每个结点（每条边）是否恰处于一个强分支中？是否恰处于一个单向分支中？
解：有向图中的每个结点处于一个强分支中，而边不一定。有向图的结点和边可能出现在两个单向分支中。图见书上（P141 图7-18） 7. 证明同阶的回路必同构。
证明：同阶表明两个图的顶点个数相同，设为V; 又联通二度正则图称为回路。即两个图的每个顶点的度数相同为2. 边数为2V/2 = V,相同。由于两个图的顶点数，边数相同，且每个顶点的度数均为2，故两个图同构。
+9. 设G 是弱联通有向图，如果对于G 的任意结点v, d G (v ) =1, 则G 恰
有一条有向回路。试给出证明。
证明：因为G 是弱联通有向图，不妨设一条极大单向联通子图：
+
因为: d G (v ) =1, 所以对V k ，∃e =。若V ≠V 1⋅⋅⋅V k -1，则与极大联通子图矛盾，故V 必为V 1⋅⋅⋅V k -1之一。
又假设有两条以上的回路（反证法），不妨设有两条，则这两条回路上所有点的出度为1，而要使这两条回路联通，则至少其中有一个点
+的出度大于1，这与d G (v ) =1矛盾。故G 恰有一条会向回路。
V 1V 2V k -1V k
10. 设G 为n 阶简单无向图，对G 的任意结点v, d G (v ) ≥(n -1) /2，证明G 是联通的。 证明：
V j
任取V i , V j , 因为d G (v ) ≥(n -1) /2, 故至少存在⎡⎢多还剩余n -2-⎡⎢
n -1⎤
个点与V i 相连，最⎥2⎢⎥
n -1⎤⎡n -1⎤n -1
V i , V j 剩余的点）。故对于V j =-1
至少存在一个与V i 连接的点与V j 相连，因此V i 与V j 联通。由V i 与V j 选取的任意性，G 联通。
11. 证明：对于小于或等于n 的任意正整数k, n阶连通无向图有k
阶连通子图。
证明：n 阶连通无向图，则n 个顶点中的任意点与其他顶点均可达。取其中的k 个顶点也满足该性质，故存在k 阶连通子图。
7.4第181页
1.
解：根据图7-26得邻接矩阵为：
v 1到v 4：
长度为1的基本路径为：v 1→v 4 长度为2的基本路径为：v 1→v 2→v 4 长度为4的基本路径为：v 1→v 2→v 3→v 2→v 4
⎡0⎢0A =⎢
⎢0⎢⎣0
10110100
1⎤⎡0
⎢01⎥2⎥，A =⎢⎢01⎥
⎥⎢0⎦⎣0
1
2101011
1⎤⎡0
⎢01⎥3⎥, A =⎢⎢01⎥
⎥⎢1⎦⎣0
2
1221210
2⎤⎡0
⎢02⎥4⎥, A =⎢⎢02⎥
⎥⎢2⎦⎣0
3
43121223⎤3⎥⎥ 3⎥⎥2⎦
2.
解：（1）对于n=1,2,„,6，试计算矩阵A 1n 中的各元素。
⎡0
⎢0⎢⎢11
A 1=⎢
⎢1⎢1⎢⎣0
01110⎤⎡311
⎢12000011⎥⎥⎢
⎢10200100⎥2
A 1=⎢⎥，
01010⎥⎢211
⎢11210101⎥
⎥⎢
10010⎦⎣110
211⎤⎡425
⎢222111⎥⎥⎢
⎢522120⎥3
A 1=⎢⎥，
311⎥⎢525
⎢752141⎥
⎥⎢
112⎦⎣232
572⎤
253⎥⎥522⎥
⎥，
472⎥745⎥
⎥
252⎦
⎡17⎢9⎢⎢9A 14=⎢
⎢16⎢13⎢⎣916139⎤
84997⎥⎥4109144⎥
，⎥
9917139⎥91413249⎥
⎥
74998⎦
99
⎡38⎢22⎢⎢33A 15=⎢
⎢39⎢51⎢⎣[1**********]2⎤1618223317⎥⎥1818332618⎥
⎥
2233385122⎥3326514433⎥
⎥
1718223316⎦
，
⎡⎢[**************]⎤⎢[1**********]9⎥A 6⎢[1**********]44⎥⎥
1=⎢
⎢[**************]⎥
⎢⎥⎢[**************]7⎥
⎣[1**********]0⎥
⎦
2）
⎡⎢0001100⎤⎡1100⎤
⎢0000011⎥⎢201
0200000⎥⎢001000⎥⎥
⎢
⎢1010100⎥⎥
A 1
⎢02=⎢1
010100⎥⎢⎥，A 2
2
=⎢⎢1003100⎥
⎥ ⎢1001000⎥
⎢1011200⎥
⎢0100000⎥⎢⎥⎢
⎢000
0011⎥
⎥⎣0100000⎥⎦⎢⎣
0000011⎥⎦
⎡⎢2014300⎤⎡70⎢0000022⎥⎢46600⎤
0400000⎥⎢003100⎥⎥
⎢A 3
⎢12=⎢4
032400⎥⎢4032400⎥⎥⎢⎥，A 4
2
=⎢⎢60211600⎥⎥ ⎢3014200⎥
⎢6046700⎥⎢0200000⎥⎢⎥⎢⎢0000022⎥
⎣0200000⎥⎦⎢⎥
⎣0000022⎥⎦⎡⎢1206171300⎤⎡1731290⎢00
00044⎥⎢300
080000⎢0211600⎥⎥
⎢
1114170A 5
⎢62=⎢17
011141700⎥⎢⎢⎥，A 6
⎢1702
=⎢3101445310⎢1306171200⎥
⎢291731300⎢0400000⎥0⎢⎥⎢
⎢00
0004⎣
04
00000⎥⎦⎢⎣
0000043）试求出图中G1和G2中的所有基本循环。
0⎤
0⎥0⎥⎥
0⎥
⎥ 0⎥
4⎥
⎥4⎥⎦
（（
k
对于A 1和A 2，a ii 表示结点v i (i =1,2,...7) 上长度为k 的循环的个数。
3. 对于图7-26中的有向图，试求出邻接矩阵A 的转置A T , AA T , A T A , 列出矩阵A ∧A T 的元素值，并说明它们的意义。
解：A 表示有向图逆图的邻接矩阵，即原图中如果有第i 个结点到第j 个结点长度为1的路径，则A 中第j 行第i 列为1；
第i 个结点和第j 个结点引出的边，可以同时终止于某些结点，这些结点的个数为AA 中第i 行第j 列的元素值。
从某些结点引出的边，可以同时终止于第i 个结点和第j 个结点，这
T
些结点的个数为A A 中第i 行第j 列的元素值。
T
T
T
A ∧A T 中第i 行第j 列对应元素为1表示从第i 个结点和第j 个结点
引出的边，可以同时终止于某些结点；为0表示第i 个结点和第j 个结点引出的边，不可以同时终止于某个结点。 4. 对于nxn 的布尔矩阵A ，试证明：
(I ∨A ) (2)=(I ∨A ) ∧(I ∨A ) =I ∨A ∨A (2)
其中I 是nxn 的单位矩阵，并且有A (2)=A ⨯A 。再证明：对于任何正整数n ∈I +, 都有(I ∨A ) (n ) =I ∨A ∨A 2∨⋅⋅⋅∨A (n )
证明：（1）(I ∨A ) (2)=(I ∨A ) (I ∨A ) ，若该矩阵中的a ij =1, 则存在v k 使得a ik =1且a kj =1，即(I ∨A ) ∧(I ∨A ) , 故(I ∨A ) (2)=(I ∨A ) ∧(I ∨A ) 。又
I ∧A =A ，A ∧I =A (因为I
相当于每个顶点到自己的边，不改变该顶
点到其他顶点的边) ，因此有：(I ∨A ) ∧(I ∨A ) =I 2∨(I ∧A ) ∨(A ∧I ) ∨A 2=
I ∨A ∨A 2, 故问题一得证。
（2）用数学归纳法证明：
当n=2时成立。
假设当n=k是成立，则有：(I ∨A ) (k ) =I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) 当n=k+1时，
(I ∨A ) (k +1) =(I ∨A ) (k ) (I ∨A )
=(I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) (I ∨A ) =(I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∧(I ∨A )
=((I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∧I ) ∨((I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∧A ) =(I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∨((I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∧A ) =(I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∨(A ∨A (2)∨⋅⋅⋅∨A (k ) ∨A (k +1) )
=I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ∨A (k +1)
故命题成立。
5. 给定简单有向图G =，并且有=n 。设A 是G 的邻接矩阵。试证明：根据第1题中所得到的结果能够把路径矩阵表示成
P =(I ∨A ) (n ) 。
证明：对于有向图的路径矩阵：P =A ∨A (2) ∨(3) ∨⋅⋅⋅∨A (n ) ，而对于第一题有：A ∨A (2) ∨(3) ∨⋅⋅⋅∨A (n ) =I ∨A ∨A (2) ∨(3) ∨⋅⋅⋅∨A (n ) ，故有：
P =I ∨A ∨A (2) ∨(3) ∨⋅⋅⋅∨A (n ) ，由第4题得到：(I ∨A ) (n ) =I ∨A ∨A 2∨⋅⋅⋅∨A (n ) ，
故有：P =(I ∨A ) (n ) ，得证。
6. 图7-27给出一个简单有向图。试求出该图的邻接矩阵A ，并求出其路径矩阵P =A +。 解：
⎡0⎢0⎢A =⎢1
⎢⎢0⎢⎣0⎡0⎢0⎢4
A =⎢0
⎢⎢0⎢⎣0
1000⎤⎡00
⎢000010⎥⎥⎢2
0000⎥，A =⎢01
⎥⎢
0001⎥⎢01
⎢1000⎥⎦⎣001000⎤⎡00⎢000010⎥⎥⎢(5)
0001⎥，A =⎢01
⎥⎢
0001⎥⎢01
⎢1000⎥⎦⎣00
010⎤⎡00
⎢01001⎥⎥⎢3
000⎥，A =⎢00
⎥⎢
000⎥⎢00
⎢010⎥⎦⎣00010⎤
001⎥⎥000⎥，
⎥
000⎥010⎥⎦
001⎤
000⎥⎥010⎥，
⎥
010⎥001⎥⎦
P =A +=A ∨A (2)∨A (3)∨A (4)∨A (5)
⎡01011⎤⎢01011⎥⎢⎥=⎢11011⎥ ⎢⎥01011⎢⎥⎢⎣01011⎥⎦
7. 使给出图7-25中的有向图的距离矩阵。d ij =1意味着什么？ 解：
⎡012∞∞⎤⎢101∞∞⎥⎢⎥
D =⎢210∞∞⎥, d ij =1表示有一条v i 到v j 的边。
⎢⎥∞∞∞01⎢⎥⎢⎣∞∞∞10⎥⎦
8. 试求出第2题中的图G1和G2的距离矩阵。 解：
⎡0⎢2⎢⎢1D 1=⎢
⎢1⎢1⎢⎣2
⎡0
21112⎤⎢∞
⎢03211⎥⎥⎢2
⎥30123⎢
D =, ⎥2⎢121012⎥
⎢1
⎥12101⎢⎥⎢∞13210⎦⎢∞
⎣
∞
∞∞⎤
0∞∞∞11⎥⎥∞012∞∞⎥
⎥
∞101∞∞⎥ ∞210∞∞⎥
⎥
1∞∞∞02⎥1∞∞∞20⎥⎦
211
9. 如何才能从一个距离矩阵中求得一个路径矩阵呢？
证明：对于任意结点v i 和v j （i ≠j ），由题意a ij ≠0，因此从v i 到v j 必定存在一条长度不为0的路径，由结点选取的任意性得：任何两个结点均是联通的。故G 的强联通的有向图。
从距离矩阵求路径矩阵：将距离矩阵中不为0的值变为1，即可得到。 10. 试确定图7-25所示的图是否是强分支。 解：对图7-25由距离矩阵求得的路径矩阵为：
⎡0⎢1⎢P =⎢1
⎢⎢0⎢⎣0
1100⎤
0100⎥⎥
1000⎥，由路径矩阵知该图不是强分支。
⎥
0001⎥0010⎥⎦
7.5第184页
1.
解：a), b), c)是欧拉图，d), e), f)不是欧拉图。
2. 如果G 1和G 2是可运算的欧拉有向图，则G 1⊕G 2仍是欧拉有向图。这句话对吗？如果对，给出证明，如果不对，举出反例。 证明：不对, 不能保证连通.
4. 设G 是平凡的连通无向图，证明：G 是欧拉图，当且仅当G 是若干个边不相交的回路的并。
证明：充分性，当进行若干个不相交的回路的并运算后，每个结点都是偶结点，因此G 是欧拉图。
必要性，对于G 是欧拉图，则G 必定有欧拉闭路。如果某个结点的度数大于2，可以对结点的环路进行分解，分解为多个小的环路的并。
7.6第186页
1. 图7-34是不是二部图？如果是，找出其互补结点子集。 解：是，互补结点子集是：{v 1, v 3, v 5},{v 2, v 4, v 6, v 7}。 2. 如何由无向图G 的邻接矩阵判断G 是不是二部图？
解：设G 的邻接矩阵为A ，=n ，计算A (2) ，A (3) ，„A (n ) 。其中如果矩阵的对角线出现了基数，则G 不是二部图。如果所有的矩阵（包括矩阵A ）的回路长度都是偶数，则是二部图。
3. 举出一个二部图的例子，它不满足定理7.6.3的条件，但是存在完美匹配。
解：如第一题的例子，二部图为：
该图中不满足定理7.6.3的条件（对于V1，在V2中至少有2个结点与其相邻，但是在V2中，各结点最多有有2个结点与V1中结点相邻），但是该图是完美匹配，因为匹配数为3（=1）（如v 1v 2，v 3v 4 ，v 5v 7） 4. 证明：n 阶简单二部图的边数不能超过[n 2/4]。
证明：对于简单二部图，当为完全二部图时边数最多，边数为1*2，又1+2=n ，当1=2即1=2=n /2时，1*2有最大值n 2/4，故边数取整，故边数不能超过[n 2/4]。得证。 5.
解：可能，如下图：
P
1
P 234
6. 解：
张明王同
李林赵丽
7. 图7-35是否存在{v 1, v 2, v 3, v 4}到{u 1, u 2, u 3, u 4, u 5}的完美匹配？如果存在，指出它的一个完美匹配。 解：存在。如：v 1u 2，v 2u 1，v 3u 4，v 4u 5。
7.7第192页
1. 对于下列情况，验证欧拉公式n-m+k=2 (1)图7-45中的多边形的图。
解：对a) 点数7，面的个数3，边的个数8，7+3-8=2，成立。 对b) 顶点个数8，面的个数3，边的个数9，8+3-9=2，成立。 (2)一个具有(r 1) 2个结点的无向边，它描述了r 2个正方形的网络，例如棋盘等。
解：顶点个数为(r +1) 2，面的个数为r 2+1，边的个数为r 2，
(r +1) 2+r 2+1-2r (r +1) =2，成立。
2. 试证明：图7-42b 中的库拉图斯基图是个非平面图。 证明：
对于基本环路：v 1v 2v 3v 4v 5v 1, 考虑v 2v 5和v 3v 5在环的内侧，直线v 1v 4必定在外侧。对于直线v 1v 3和v 2v 4必定相交。故该图是非平面图。 3. 画图所有不同构的6阶非平面图。
解：根据分析图至少有9条边，最多为15条边。所有情况如下图：
9
910
111112
131415
4. 试用库拉斯基定理证明：图7-48中的图是个非平面图。 证明：图7-48中村子一个子图与阶数为6的库拉斯基图同构。将图7-48变形得到：
其中的由{v 1, v 2, v 3, v 4, v 5, v 6}构成的子图与阶数为6的库拉斯基图同构。故该图是非平面图。
5. 图7-49给出一个多边形的图，试构成该图的对偶。
解：对偶图如下：
7.8第204页
1. 画出所有不同构的一、二、三、四、五、六阶树。 解：一阶：
二阶：
四阶(2)
五阶(3)
六阶(6)
2.
如何由无向图G 的邻接矩阵确定G 不是树？
解：根据“G 不含回路而且有n-1条边则G 是树”可以得出图G
是一
棵树的判定条件如下：(1)无线图G 的邻接矩阵A 的n 次幂A n 中，对角线上全是0（说明不存在回路）。（2）邻接矩阵中1的个数的总数为2(n-1),说明边的个数为n-1。邻接矩阵同时满足上面两个条件可以判断图G 是树，如果不同时满足，则判断不是树。
3. 设v 和v '是树T 的两个不同的结点，从v 至v '的基本路径是T 中最长的基本路径。证明：d T (v ) =d T (v ') =1 证明：反证法
假设v 或v '有一个结点的度数大于1，不妨设d T (v ) >1, 则必然存在一个
v ''与v 相连，由树的定义知v ''不在v 至v '的路径中（否则构成了环）。
设v 至v '的路径长度为l ，则v '到v ''的距离为l +1>l ，这与v 至v '的基本路径是T 中最长的基本路径矛盾。故d T (v ) =d T (v ') =1。 4. 。 解：a) b)
7. 证明：任何二叉树有基数个结点。
证明：在二叉树中，任何结点的出度不是0，就是2；假设出度为2的结点有x 个，则该二叉树的出度之和为2x ；设二叉树共有n
个结
点，这些结点中除了根结点的入度为0，其余结点的入度都为1，因此，所有结点的入度之和为n-1。由图的性质，可知二叉树的出度之和与入度之和相等。即n-1=2x， n=2x+1，因此，无论x 如何取值，二叉树的结点总数n 都是基数。得证。
9. 证明：n 阶二叉树的叶子结点数目为(n+1)/2，其高度h 满足log2(n+1)-1≤h ≤ (n-1)/2
证明：（1）在二叉树中，出度为0的结点是叶子结点，出度为2的结点是分支结点，设分支结点个数为x ，由上题证明过程可知，n=2x+1, x=(n-1)/2。因此，叶子结点的个数为n-x=(n+1)/2。
（2）n 阶二叉树的叶子结点有(n+1)/2个，分支结点有(n-1)/2个。利用(n-1)/2个结点构造一棵一元或二元树，设树高为m ，则h=m+1。 考察(n-1)/2个结点构造的一棵一元或二元树，树高最大的情况是一元树，高度为(n-1)/2-1，因此，h 最大值是(n-1)/2-1+1=(n-1)/2。 树高最小的情况是构造了一棵满二叉树，满二叉树的高度x 和结点个数(n-1)/2满足关系2x+1-1=(n-1)/2，解得x=log(n+1)-2，因此h 最小值是log(n+1)-1。因此，log2(n+1)-1≤h ≤ (n-1)/2。 10. 如何由有向图G 的邻接矩阵确定G 是不是有向树？
解：根据有向树的判定定义：仅一个结点的入度为0，其余结点的入度均为1的连通有向图。如果G 是有向树，则其邻接矩阵满足：（1）有且仅有一列全为0。（2）其余的列有且只有一个1。否则有向图不是有向树。
11. 找出叶的权分别为2，3，5，7，11，13，17，19，23，29，31，
37和41的最优叶加权二叉树，并求其叶加权路径长度。
解：对于2,3,5,7,11,13,17,19,23,29,31,37,41，先组合两个最小的权2+3=5，得5,5,7,11,13,17,19,23,29,31,37,41；在所得到的序列中再组合5+5=10，得10,7,11,13,17,19,23,29,31,37,41；再组合10+7=17，得17,11,13,17,19,23,29,31,37,41；继续下去。。。。，过程如下：
5 7 11 13 17 19 23 29 31 37 41
7 11 13 17 19 23 29 31 37 41 11 13 17 19 23 29 31 37 41 17 17 19 23 29 31 37 41 24 19 23 29 31 37 41 24 34 29 31 37 41 34 42 31 37 41 42 53 37 41 42 53 65 65 78 95 238
所得到的最优二叉树如下图：
12. 找出图7-71给出的有向序森林所对应的二元有向有序树，并求其前缀编码。 解：
1： 2：0 3：01 4：011 5：0111 6：00 7：001 8：010 9：01110 10：011101 11：111011 12：1 13：10 14：101 15：100 16：1010 17：10101 18：11 19：110 20：1101 21：1100 22：11001 23：11010 24：110101 25：11000 26：110001 27：1101010 28：11010101 13. 求图7-72的最小生成树。
2
1
3
1
44
解：
7.9第219页
1. 用标号法求图7-86所示的运输网络的最大流，其中无向的边是双向的。
解：求得的网络流量分配如下图：
2. 设x 1, x 2, x 3是三家工厂，y 1, y 2, y 3是三个仓库，工厂生产的产品要运往仓库，其运输网络如图7-87所示，设x 1, x 2, x 3的生产能力分别为40，20，10个单位，问如何安排生产？
解：x 1生产20个单位，x 2生产20个单位，x 3生产10个单位，最多生产50个单位。运输网络分配如下图：
y 1
y 2
3
y 3
3. 七种设备要用五架飞机运往目的地，每种设备各有四台。这五架飞机的容量分别是8，8，5，4，4，问能否有一种装法，使同一种类型设备不会有两台在同一架飞机上？
解：飞机容量为8：类型一4台+类型二4台，飞机容量为8：类型三4台+类型四4台，飞机容量为5：类型五4台，飞机容量为4：类型六4台，飞机容量为4：类型七4台。
4. 在第三题中，若飞机的容量分别是7，7，6，4，4台，求问题的解。 解：各个飞机的分配如下图：
5. 已知开关函数f ab =x 1x 3+x 1x 2x 5+x 2x 3x 4+x 4x 5, 求实现这个简单接触的网络。
解：简单接触网络如下图：
第六章 代数系统
6.1第129页
1． 证明：
任取x , y ∈I ，g (y , x ) =算*是可交换的； 任取x , y , z ∈I ，
y *x =y +x -yx =x +y -xy =g (x , y ) ，因此，二元运
g (x , g (y , z )) =x *(y *z )
=x *(y +z -yz )
=x +y +z -yz -x (y +z -yz ) =x +y +z -xy -xz -yz +xyz
g (g (x , y ), z )
=(x *y ) *z
=(x +y -xy ) *z
=x +y -xy +z -(x +y -xy ) z =x +y +z -xy -xz -yz +xyz =g (x , g (y , z ))
因此，运算*是可结合的。
该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。 2．
证明：任取x , y ∈N , x ≠是可交换的。 任取
y ，由x *y =x , y *x =y ≠x 知，y *x ≠x *y ，*运算不(x *y ) *=z
x =*z
，x x *(y *z ) =x *y =x 知，
x , y , z ∈N
，由
(x *y ) *=z *运算是可结合的。 x *(y ，*z
任取x ∈N ，x *x =x ，可知N 中的所有元素都是等幂的。
*运算有右么元，任取x , y ∈N ，x *y =*运算没有左么元。
x ，知N 中的所有元素都是右么元。
证明：采用反证法。假定e 为*运算的左么元，取b ∈N , b ≠e ，由*的运算公式知e *b =e ，由么元的性质知，e *b =b ，得e =b ，这与b ≠e 相矛盾，因此，*运算没有左么元。
3．解：
① 任取x , y ∈I , x ≠y
x *y =x 和y 的最小公倍数
y *x =y 和x 的最小公倍数=x 和y 的最小公倍数
因此对于任意的x , y ∈I , x ≠y 都有x *y =y *x ，即二元运算*是可交换的。 ② 任取x , y , z ∈I ,
（x *y ）*z =(x 和y 的最小公倍数) *z =x , y , z 的最小公倍数 x *（y *z ) =x *(y 和z 的最小公倍数) =x , y , z 的最小公倍数
（x *y ）*z =x *（y *z ) ，即二元运算*是可结合的。 因此对于任意的x ，y ，z ，都有
③ 设幺元为e
x *e =e *x =x 和e 的最小公倍数=x ，则e =1，即幺元为1.
④ 对于所有的元素x ∈I ，都有x *x =x ，所以所有元素都是等幂的。
4．解：设X =n
① 设f 是X 上的二元运算，则f 是一个从X →X 的映射。 求X 上有多少个二元运算即相当于求这样的映射的个数。
22n n
由于X =n ，映射f 的个数为n ，即X 上有n 个二元运算。
2
2
2
② 可交换即f =f 设集合X ={1, 2, 3, 4}，要求
X
上可交换的二元运算的个数，即相当于求映射f 的个数，
f :A →X ，其中：
A ={, , }
具体如下图所示：
, , , , 1, 2, 3 4X A
此时映射f 的个数N 4
=4
6+4
=4
2C 4+4
推广到X 有n 个元素时，映射f 的个数N n ③ 单位元素即幺元，若存在必唯一。 设集合X ={1, 2, 3, 4}，若幺元为1，则有
=n
2
C n +n
→1, →2
, →3
, →4
此时的二元运算的个数相当于求映射f :A →X 的个数，其中：
A
X
1 2 34
(4-1) 2
映射f :A →X 的个数为N =4=4
9
幺元为2，3，4时同理，N 4
=4⋅4=C ⋅4
9
14
9
14
(4-1) 2
个有单位元素的二元运算。
因此集合X ={1, 2, 3, 4}上有N 4
=4⋅4=C ⋅4
(4-1) 2
推广到X 有n 个元素时，具有单位元素的二元运算的个数为N n
5．解：任取a 1, a 2, a 3∈R ①
=C ⋅n
1n
(n -1) 2
。
a 1*a 2=a 1-a 2
a 2*a 1=a 2-a 1=a 1-a 2=a 1*a 2
对于任意的a 1, a 2∈R 都有a 2*a 1=a 1*a 2，故二元运算*是可交换的。
(a 1*a 2)*a 3=a 1-a 2)*a 3=
若a 1
a 1-a 2-a 3
a 1*(a 2*a 3) =a 1*(a 2-a 3) =a 1-a 2-a 3
=1, a 2=-3, a 3=-2
(a 1*a 2)*a 3=6，a 1*(a 2*a 3) =0，此时(a 1*a 2)*a 3≠a 1*(a 2*a 3)
故二元运算*是不可结合的。
不存在这样e 使得任意的x ∈R 都有x *e =x -e =x ， 因此，二元运算*不含幺元。 ②a 1*a 2
=(a 1+a 2)/2
a 2*a 1=(a 2+a 1)/2=(a 1+a 2)/2=a 1*a 2
对于任意的a 1, a 2∈R 都有a 2*a 1=a 1*a 2，故二元运算*是可交换的。
a 1+a 2
+a 3
a +a +2a 3
(a 1*a 2)*a 3=((a 1+a 2)/2)*a 3==12
24a 1*(a 2*a 3) =a 1*((a 2+a 3)/2)=
故二元运算*是不可结合的。
不存在这样e 使得任意的x ∈R 都有x *e =(x +e ) /2=x ，
a 1+
a 2+a 3
=2a 1+a 2+a 3≠a 1+a 2+2a 3244
因此，二元运算*不含幺元。 ③
a 1*a 2=a 1/a 2
a 2*a 1=a 2/a 1≠a 1*a 2
因此，二元运算*是不可交换的。
(a 1*a 2)*a 3=(a 1/a 2)*a 3=a 1/a 2=
a 3a 1
a 2a 3
a 1a 3a 1a 1
a 1*(a 2*a 3) =a 1*(a 2/a 3) ==≠
a 2/a 3a 2a 2a 3
故二元运算*是不可结合的。
由于二元运算*不是可交换的，所以不存在这样e 使得任意的x ∈R 都有x *e =e *x =x /e =x ， 因此，二元运算*不含幺元。
6．设x 是X 中的任意元素。 由于二元运算*是可结合的， 故(x *x ) *x =x *(x *x )
又对于任意的x , y ∈X ，若x *y =y *x ，则y =x 故x *x =x
即对于X 中的任意元素，都有x *x =x ， 所以X 中的 每一个元素都是等幂的。
6.2第137页
4． 证明：
首先，U 和V 都只含有一个二元运算，因此是同类型的； 第二，
f 的定义域是自然数集合N ，值域是{0,1}，是V 定义域的子集。
第三，验证是否运算的像等于像的运算。 任取x , y ∈N ，分情况讨论： （1） x 和y 都可以表示成2，设x =2
k
k 1
, y =2k 2，
那么
f (x y ) =f (2k 12k 2) =f (2k 1+k 2) =1，f (x ) =f (y ) =1
f (x ) f (y ) =11=1=f (x y )
（2） x 和y 都不能表示成2，那么x
k
y 也不能表示成2k
f (x y ) =0, f (x ) =f (y ) =0 f (x ) f (y ) =00=0=f (x y )
（3） x 可以表示成2，y 不能表示成2，那么x
k
k
y 也不能表示成2k
f (x y ) =0, f (x ) =1, f (y ) =0 f (x ) f (y ) =10=0=f (x y )
（4） x 不可以表示成2，y 能表示成2，那么x
k
k
y 也不能表示成2k
f (x y ) =0, f (x ) =0, f (y ) =1 f (x ) f (y ) =01=0=f (x y )
可知，无论x 和y 如何取值，都能够保证综上所述，5．
证明：设U =〈{a , b , c },*〉，V =〈{1,2,3},⊕〉
首先，U 和V 都仅有一个二元运算，因此U 和V 是同类型的； 第二，U 和V 的定义域大小相同，具备构成双射函数的条件；
第三，寻找特异元素，U 中么元是a ，右零元是c ，三个元素都是等幂元；V 中么元是3，右零元是1，三个元素都是等幂元。 第四，在U 和V 的定义域之间构造双射函数把*运算表中的元素都用f 下的像点代替，得
调整表头的顺序为1，2，3，转变为下表
f (x ) f (y ) =f (x y ) 。
f
是U 到V 的同态映射。
f
，使得
f (a ) =3, f (b ) =2, f (c ) =1。
跟V 中⊕运算表完全相同，因此代数系统〈{a , b , c },*〉和〈{1,2,3},⊕〉是同构的。 6. 证明：
(1) 两个代数系统都只存在一个二元运算，故满足同型。 (2) 构造函数f ，使得(3) 对于任意的X , Y ∈ρ(X )
故
，所以满足运算的像=像的运算。
，显然f 是双射函数。
由(1),(2),(3)可知，两代数系统是同构的。
7. 解：
f p (X ) =(px ) mod 6, p =0, 1, 2, 3, 4, 5
当p =0时，f 0零同态；
当p =1时，f 1恒等映射，自同态；
当p =2时，f 2={, , , , , }； 当p =3时，f 3={, , , , , }； 当p =4时，f 4={, , , , , }； 当p =5时，f 5={, , , , , }自同构。
8. 证明：x -1=0的n 个复数根可表示成：
n
2π
x k i =cos k i α
+sin k i αi , α=, k i =0, 1, 2,.... n -1
n
(1) 与都含有一个二元运算，故为同型的。 (2) 与
定义域大小相同，具备构成双射函数的条件。
(3) 构造双射函数
f (x k i ) =k i (mod n )
对于任意的x k 1, x k 2∈E n ，
f (x k 1∙x k 2) =f ((cosk 1α+sin k 1αi ) ∙(cosk 2α+sin k 2αi ))
=f (cosk 1α⋅cos k 2α+cos k 1αsin k 2αi +sin k 1cos k 2αi +sin k 1sin k 2i 2) =f (cosk 1α⋅cos k 2α+cos k 1αsin k 2αi +sin k 1cos k 2αi -sin k 1sin k 2) =f (cos(k 1+k 2) α+sin(k 1+k 2) αi ) =(k 1+k 2)(modn )
f (x k 1) +n f (x k 2) =k 1(modn ) +n k 2(modn ) =(k 1(modn ) +k 2(modn ))(modn ) =(k 1+k 2)(modn )
因此，f (x k 1∙x k 2) =f (x k 1) +n f (x k 2) 。 由(1),(2),(3)可知，
9．证明：
(1) g 是代数系统到当的同态映射 ∴g [X ]⊆Y
又 是的子代数
同构于
。
∴X 1⊆X ∴g [X 1]⊆Y
(2) 对于∀a , b ∈g [X 1]，必存在X a , X b ∈X 1， 使得g [X a ]=a ，g [X b ]=b ,
a ∙b =g [X a ]∙g [X b ]
由于g 为代数系统到当的同态映射
∴g [X a ]∙g [X b ]=g [X a *X b ]
X a , X b ∈X 1，又 是的子代数
故X 1对*运算封闭
∴X a *X b ∈X 1
∴g [X a *X b ]∈g [X 1]，即a ∙b ∈g [X 1] ∴g [X 1]对∙运算满足封闭性。
由(1),(2),(3)可知, 为的子代数。
6.3第141页
1．解：
解：首先，判断≡m 是否是等价关系。任取x ∈I ，由于x -是自反的；任取x , y ∈I ，若x ≡m
x =0⋅m ，因此x ≡m x ，≡m
y ，即x -y =a ⋅m （a ∈I ），则y -x =-a ⋅m ，
y ≡m x ，因此≡m 是对称的；任取x , y , z ∈I ，若x ≡m y , y ≡m z ，则x -y =a ⋅m
（a ∈I ），y -z
=b ⋅m （b ∈I ），于是x -z =(x -y ) +(y -z ) =(a +b ) ⋅m ，
a +b ∈I ，因此x ≡m z ，可知≡m 是可传递的。因此，≡m 是等价关系。
其次，判断≡m 关于*是否满足代换性质。 任取x , y ∈I ，若x ≡m
y ，即存在某个p ∈I ，满足x -y =p ⋅m
*(x ) =x k (modm ) *(y ) =y k (modm )
则
*(x ) =(y +p ⋅m ) k (modm )
1k -1
=C k 0y k +C k y (p ⋅m ) 1+C k 2y k -2(p ⋅m ) 2+1k -1=y k +p ⋅m ⋅(C k y +C k 2y k -2(p ⋅m ) 1+
+C k k y 0(p ⋅m ) k
+C k k y 0(p ⋅m ) k -1)
于是
1k -1
*(x ) -*(y ) =p ⋅m ⋅(C k y +C k 2y k -2(p ⋅m ) 1++C k k y 0(p ⋅m ) k -1) +C y (p ⋅m ) ) ⋅m
k
+k
(C
-k
k k
k -1
=p ⋅(C y
由于
1k -1
p ⋅(k C y +
1
k
k -1
+C y
2k
k -2
(p ⋅m ) +
1
k
2k -1C (y 2⋅) p +m
⋅y ) ，p ) 因∈m 此，I
*(x ) ≡m *(y ) ，≡m 关于*是满足代换性质。
综上所述，≡m 是U 上的同余关系。
2. 解：
（1）对于+运算，在二元运算下，任取
x 1, x 2, y 1, y 2∈I ，验证下式是否成立
x 1Ry 1x 2Ry 2
⇒
取
⎫⎬2行⎭
x 1+x 2Ry 1+y 2
1
1，2
x 1=1, x 2=2, y 1=1, y 2=-2，可知满足x Ry
x Ry 2，但|x 1+x 2|≠|y 1+y 2|
，
即x 1+x 2y 1+y 2。可知对于运算+，R 不满足代换性质。
（2）对于⋅运算，在二元运算下，任取
x 1, x 2, y 1, y 2∈I ，
y 1|,|x 2|=|y 2|
若x 1Ry 1，x 2Ry 2，则必然满足|x 1|=|于是|x 1⋅x 2|=|x 1|⋅|x 2|=|可得x 1⋅x 2Ry 1⋅y 2。
y 1|⋅|y 2|=|y 1⋅y 2|
由x 1, x 2, y 1, y 2取值的任意性可知，对于运算⋅，R 满足代换性质。
3．证明：
(1) 对于∀x 1, x 2, y 1, y 2，有x 1Ry 1, x 2Ry 2
由于R 对+3具有代换性质，所以有(x 1+x 1) R (y 1+y 1) 由此可知：
(x 1+3x 1+3... +3x 1) R (y 1+3y 1+3... +3y 1) ⇒x 1⋅3x 2Ry 1⋅3x 2
x 2个x 1
同理可知：
x 2个y 1
(x 2+3x 2+3... +3x 2) R (y 2+3y 2+3... +3y 2) ⇒y 1⋅3x 2Ry 1⋅3y 2
y 1个x 2
y 2个y 1
因R 是等价关系，故是可传递的，所以有x 1⋅3x 2Ry 1⋅3y 2 所以R 对⋅3具有代换性质。
(2) S ={, , , , }对⋅3具有代换性质，
但对+3不具有代换性质，因+3=∉S
4．设代数系统V =，R 1, R 2为同余关系。 (1)即证：R 1 R 2为同余关系 证明：R 1 R 2为等价关系
若w ∈Ω对任意
a 1, b 1, a 2, b 2,... a n w , b n w ∈G
R 2) b n w
a n w R 1b n w a n w R 2b n w
有a 1(R 1 R 2) b 1, a 2(R 1 R 2) b 2, …a n w (R 1 则a 1R 1b 1， a 2R 1b 2，…
a 1R 2b 1， a 2R 2b 2，…
R 1 R 2为同余关系
∴w () R 1w () ∴w () R 2w () ∴w () R 1 R 2w ()
所以R 1 R 2为同余关系。 (2) R 1 R 2为等价关系
若w ∈Ω对任意
a 1, b 1, a 2, b 2,... a n w , b n w ∈G
w
有a 1(R 1 R 2) b 1, a 2(R 1 R 2) b 2, …a n w (R 1 R 2) b n 未必有a 1R 1b 1， a 2R 1b 2，…
a n w R 1b n w
a 1R 2b 1， a 2R 2b 2，…
因此，可能不满足代换性质
a n w R 2b n w
所以R 1 R 2未必是同余关系。
5．
（1）xRy , 当且仅当(x
=0, y 1=3, x 2=-1, y 2=-2, 则x 1Ry 1, x 2Ry 2，
=-10，因此x 1+x 2y 1+y 2，不满足代换性质。
（2）xRy , 当且仅当x -y
x =0, y =9, z =15，则xRy
，
yRz
，但
|x -z |=15>10，x z ，R 不满足可传递性，不是等价关系。
（3）xRy , 当且仅当(x =y =0) ∨(x ≠0∧y ≠0) 解：R 不是〈I , +〉上的同余关系，取取x 1但是x 1+x 2
=-3, y 1=2, x 2=3, y 2=2, 则x 1Ry 1, x 2Ry 2，
=0，y 1+y 2=4≠0，因此x 1+x 2y 1+y 2，不满足代换性质。
（4）xRy , 当且仅当x ≥y
解：R 不是〈I , +〉上的同余关系，取x =9, y =8，则xRy ，但y x ，即y 足对称性，不是等价关系。
x ，R 不满
6.4第143页
1.
解：
（1）设F 2⨯F 3=
>
其中，N 2⨯N 3={, , , , , }
任取
>, ∈N 2⨯N 3
⊕= =
下面通过运算表构造*运算（这里仅给出了一个运算表，另一个照推）
⊕
（2）设F 3⨯F 2=
其中，N 3⨯N 2={, , , , , }
任取
>, ∈N 3⨯N 2
⊕=
=
运算表的构造方法与上同。 2.
(1) 证明：任取, ∈X ⨯Y ，
∆=
∙和*可交换
∴∆===
2, y 2>∆
∴∆是可交换的。
(2) 任取, , ∈X ⨯Y
∆∆=
∙和*可结合
∴∆∆==∆
=∆(∆)
∴∆是可结合的。
3.
+m
0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 5 2 2 3 4 5 0 3 3 4 5 0 1 4 4 5 0 1 2 5
5 0 1 2 3 ⊕
证明：
① 与A 6都只有一个二元运算，故为同型的。
5 5 0 1 2 3 4
② 与A 6定义域大小相同，具备构成双射函数的条件。 ③ 构造双射函数
f () =0, f () =1, f () =2, f () =3, f () =4, f () =5
由上图可知，像的运算=运算的像 所以与A 6是同构的。
6.5第155页
1. （1）半群 （2）半群 （3）半群
（4）独异点，么元0
（5）不是半群，取a=b=1,c=2，则
(a -3b ) -3c =1a -3(b -3c ) =2
不满足结合律
（6）不是半群，因为||不是二元运算； （7）半群
（8）独异点，么元0 （9）半群
（10）独异点，么元为恒等关系； （11）独异点，么元为a 2.
（1）二元运算表如下图所示： GCD 1 2 3
1 1 1 1
2 1 2 1
3 1 1 3
4 1 2 1
6 1 2 3
8 1 2 1
12 1 2 3
24 1 2 3
4 1 2 1 4 2 4 4 6 1 2 3 2 6 2 6 8 1 2 1 4 2 8 4 12 1 2 3 4 6 4 12 24 1
2
3
4
6
8
12
（2）〈X X , 〉, 其中X ={1,2,3}。（假定X X
为丛X 到X 的双射函数）
解：X 到X 有6个双射函数，分别用
p 1, p 2, , p 6表示，设
X :a b c
↓↓↓
p 1:a b c
p 2:a c b
p
3:b a c
p 4:b c a p 5:c a b p 6:
c
b
a
构造运算表如下：
p 1 p 2 p 3 p 4 p 5 p 1 p 1 p 2 p 3 p 4 p 5 p 2 p 2 p 1 p 5 p 6 p 3 p 3 p 3 p 4 p 1
p 2 p 6 p 4 p 4 p 3 p 6
p 5 p 1 p 5 p 5 p 6 p 2 p 1 p 4 p 6
p 6
p 5
p 4
p 3
p 2
4 6 8 12 24
p 6 p 6 p 4 p 5 p 2 p 3 p 1
第七章 图论
6.1第164页
1. 画出图G =〈V , E , ψ〉的图示，指出其中哪些图是简单图。 （1）
v 4
不是简单图。
（2）
4
3
不是简单图。
2（3）
e 1
47
v 8
v 2
是简单图。
2. 写出图7-8的抽象数学定义。 （1）解：G =〈V , E , ψ〉，其中
V ={1, 2, 3，, E ={a , b , c , d , e , f }，
ψ={>, >, >, >, >, >}
（2）解：G =〈V , E , ψ〉，其中V ={1,2,3,4,5,6,7,8,9}，E ={a , b , c , d , e , f , g , h , i ,
j , k , l }
，
ψ={, , , , ,
, , , , , , }
3. 证明：在n 阶简单有向图中，完全有向图的边数最多，其边数为n (n -1) 。
证明：简单有向图是没有自环，没有平行边的有向图，只要两个不同的结点之间才能有边。完全有向图是每个结点的出度和入度都是n-1的简单有向图，也就是每个结点都有到其他所有结点的边，因此，完全有向图的边数最多。
在完全有向图中，所有结点的出度之和为n(n-1)，所有结点的入度之和为n(n-1)，设边的个数为m ，由握手定理可知，2m= n(n-1)+ n(n-1)，即m= n(n-1)，得证。 4. 证明：3度正则图必有偶数个结点。
证明：设三度正则图的结点个数为n ，那么所有结点的度数之和为3n ，由握手定理可知，边的个数为3n/2=1.5n，由于边的个数一定是整数，因此，n 为偶数。得证。
5. 在一次集会中，相互认识的人会彼此握手，试证明：与奇数个人握手的人数是偶数个。 证明：设集会上的人一共有m 个，可分为两部分，一部分为与奇数个人握手的人，设为x 个，另一部分为与偶数个人握手的人，为m-x 个。
由于握手是相互的，即一次握手，两个人握手的次数都加1，一共加2，因此，集会上所有人的握手次数之和为偶数。
与偶数个人握手的人，这些人的握手次数之和为，为偶数。 a 1, a 2, , a m -x 都是偶数）
与奇数个人握手的人，这些人的握手次数之和为b 1+b 2
a 1+a 2++a m -x （其中，
+
+b x （其中，b 1, b 2, , b x 为+
+b x 也要为偶数，即
基数），由于所有人的握手次数之和偶数，因此b 1+b 2
(b 1+b 2+
又因为
+b x )mod2=0
+b x )mod 2
+b x mod 2
(b 1+b 2+
=b 1mod 2+b 2mod 2+
=x mod 2
即x mod2=0，因此x 为偶数，即与奇数个人握手的人是偶数个，得证。
6. 证明：图7-7中的两个图同构。
证明：首先，给这两幅图标上对应的结点编号，如下
1
23
1'
2'
3'
4'
4
两
个
图
5
的
结
6
点
和
边
的
数
6'
目
都
5'
相
同
。假
设函数
ψ={, , , , , }，左图中相邻的结点是
1和4，1和5，1和6，2和4，2和5，2和6，3和4，3和5，3和6，对应的像点1’和4’，1’和2’，1’和6’，5’和4’，5’和2’，5’和6’，3’和5’，3’和2’，3’和6’在右图中也相邻，因此，两图同构。
7. 证明：在任意六个人中，若没有三个人彼此认识，则必有三个人彼此都不认识。 证明：分三种情况：
（1）任何一个人最多认识另外一个人 将相互认识的两个人分成一组，则至少可以分3组，每组取一个人，则这三个必不认识。 （2）任何一个人最多认识另外两个人 最糟糕的情况是当每个人都认识另外两个人时，若认识的人之间画一条线可以构成一个六边形，取不相邻的三个点即是不认识的。 （3）任何一个人最多认识另外的三个人
A
F
不妨设点A 与B,C,E 认识（用实线连接）。因为B,C,E 之间只有有两个人认识就不满足任何三个人都不认识的条件，比如B,C 认识画一条实线，那么A,B,C 就相互认识，与已知矛盾。所以B,C,E 是所求的三个互补认识的人。 （4）任何一个人最多认识两外4或5个人 该情况与（3）类似，所求的人即与A 认识的两外4或5个人中的三个人。 证毕。
8. 证明：图7-9的两个图不同构。
证明：给这两幅图标上对应的结点编号，如下：
1
e 1
21'
'e 1
2'
e 9
5
e 5
6
e 95'
'e 5
6'
e 4
e 103
e 87
e 6
e 7e 3a)
8
e 2'e 4'e 87'
'e 6
'e 7'e 3b)
8'
'e 2
e '
4
3'
4'
两个图的点数和边数相同。假设函数：
ψ={, , , , , , , }
易证：① a ）中的子图G 1=，V 1={1,2,3,4}，E 1={e 1, e 2, e 3, e 4}，
ψ1={, , , }与
G 1'=
，
b ）中的子图
，
V 1'={1', 2',3', 4'}
，
E 1'={e 1', e 2', e 3', e 4'}
ψ1'={, , , }同构。
② a ）中的子图G 2=，V 2={5,6,7,8}，E 2={e 5, e 6, e 7, e 8}，
ψ2={, , , }与
b ）中的子图
G 2'=，G 2'=，V 2'={5',6',7',8'}，E 2'={e 5', e 6', e 7', e 8'}，
ψ2'={, , , }同构。
除这两个子图以外，对应a ）中的子图G 3=1,5,7,3}，3，V 2={
E 2={e 4, e 8, e 9, e 10}，ψ2={, , , }在b ）无
中对应的同构图。因此a ）和b ）两个图不同构。
9．图7-10的两个图是否同构？说明理由。
'
b)
+-
解：对于图b ）中的点d '，其出度为：d G '(d ') =3，入度：d G '(d ') =0。而在a) 图中不存
在这样的结点。因此这两个图不同构。
10．证明：任何阶大于1的简单无向图必有两个结点的度数相等。
证明：考虑一个有n 个结点的连通图（如果有一个孤立结点，去掉孤立结点考虑联通子图）。因为是无向连通图，每个结点的最大度数是n-1，最小度数是1。即对n 个点赋值，共n-1种取值，由抽屉原理，必有两个结点的取值相同，即必有两个点的度数相同。
11．设n 阶无向图G 有m 条边，其中n k 个结点的度数为k ，其余结点的度数为k+1，证明：
n k =(k +1) n -2m 。
证明：由题意，结点数为n ，由总边数建立关系：
m =
n k ⋅k +(n -n k )(k +1)
，由此可得：n k =(k +1) n -2m 。
2
7.2第168页
1．画出K 4的所有不同的子图，并说明其中哪些是生成子图，找出互为补图的生成子图。 解：
(1)
(2)(3)
（4）
(5)
(6)(7)
其中，（1）和（7），（2）和（6），（3）和（5），（4）中的后两个图可以构成互补的生产子图。
2．设G =是完全有向图。证明：对于V 的任意非空子集V '，
G [V ']是完全有向图。
证明：（1）当V '中只有一个结点时，G [V ']是完全有向图。
（2）当V '中有多于一个结点时，对其中任意两个结点V i , V j 是V
的子集，即V i , V j ∈V 。因为图G 是完全有向图，因此V i , V j 间存在两条有向边e ij 和e ji 。G [V ']是由非空子集V '生成的子图，故e ij , e ji ∈G [V ']，即
G [V ']中任意两个结点间存在两条有向边，故G [V ']是完全有向图。
3．画出图7-15的两个图的交、并和环和。
v 1
e 1
v 2
e 2v 3
e 3
e 6
e 4
7v 4e 5
v 5
v 2
v 3
e 8
e 1
e 3
v 1
v 4
a) b)
解：
交： 并：
v 1
v 1
e 3
e e 1
v 2
e 2
e 3
e 6
e 4
e 5
v 57v 4
e 1
v 2
v 3
v 4
v 3
环和：
v 1
e 5
v 2
e 2v 3
e 8
v 4e 4
7
v 5
4．设G 是任意6阶简单无向图，证明：G 或必有一个子图是3阶无向图。
证明：取G 或任意取三个点，取与这三个点相关联的变构成一个3阶的无向子图。
5．我们称与补图同构的简单无向图为自补图。证明：每个自补图的阶能够被4整除或被4整除余数为1。
n (n -1)
, 由自补图的定义知该2
n (n -1)
图与其子图的边数相同（同构），故其边数为，由该数是整数
4
n (n -1)
=k ，n =4k or n =4k +1。故每个自补图的阶能够被4整除或得：4
证明：设图的顶点数为n ，Kn 的边数为
被4整除余数为1。
7.3第173页
1．考虑图7-21
（1）从A 至F 的路径有多少条？找出所有长度小于6的从A 至F 的路径。
解：A 到F 的路径有无数条。长度小于6的有24条。（c f h:4,c g h:4, c e i:4, b d e f h:2, b d e g h:2, b d i:4）
（2）找出从A 至F 的所有简单路径。
解：12条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i),还有一个自环，需乘以2.
（3）找出从A 至F 的所有基本路径。
解：6条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i) （4）求出从A 至F 的距离。求出该图的直径。 解：距离为3。直径为3。 （5）找出该图的所有回路。
解：AaA, AbDdEeBcA, BeEiFhCgB; BgCfB; AbDdEiFhCgBcA; BeEiFhCfB;
2．证明：图7-21中基本路径必为简单路径。
证明：基本路径要求途经的顶点不重复，简单路径要求途经的边不重复。在图7-21中，对于所有的基本路径，边不重复出现。所以基本路径必是简单路径。 3．考虑图7-22
（1）对于每个结点v ，求R (v ) 。
解：R (v 1) =R (v 2) =R (v 3) =R (v 4) ={v 1, v 2, v 3, v 4, v 5, v 6}, R (v 5) ={v 5, v 6},R (v 6) ={v 6},R (v 7) ={v 6, v 7} R (v 8) ={v 6, v 7, v 8},R (v 9) ={v 9},R (v 10) ={v 10} （2）找出所有强分支、单向分支和弱分支。
解：强分支7个，分别是{v 9},{v 10},{v 8},{v 7},{v 6},{v 5},{v 1, v 2, v 3, v 4} 单项分支4个，分别是{v 9},{v 10},{v 6, v 7, v 8},{v 1, v 2, v 3, v 4, v 5, v 6}
弱分支3个，分别是{v 9},{v 10},{v 1, v 2, v 3, v 4, v 5, v 6, v 7, v 8}
4．设v 1v 2v 3是任意无向图（有向图）G 的三个任意结点，以下三个公式是否成立？如果成立，给出证明；如果不成立，举出反例。 （1）d (v 1, v 2) ≥0，并且等号成立，当且仅当v 1=v 2。 解：成立。当v 1≠v 2时，距离必定大于1。 （2）d (v 1, v 2) =d (v 2, v 1)
解：成立。因为无向图是无方向的。
5. 证明：有向图的每个结点和每条边恰处于一个弱分支中。 反证法：若任意结点V 处于两个或两个以上的弱分支中，不妨设两个弱分支为G1, G2, 则G1, G2是G 的极大联通子图。设v ∈G 1, v ∈G 2，又G 1, G 2∈G , 故G 1, G 2联通。这与G1, G2是极大联通子图矛盾，故命题得证。
6. 有向图的每个结点（每条边）是否恰处于一个强分支中？是否恰处于一个单向分支中？
解：有向图中的每个结点处于一个强分支中，而边不一定。有向图的结点和边可能出现在两个单向分支中。图见书上（P141 图7-18） 7. 证明同阶的回路必同构。
证明：同阶表明两个图的顶点个数相同，设为V; 又联通二度正则图称为回路。即两个图的每个顶点的度数相同为2. 边数为2V/2 = V,相同。由于两个图的顶点数，边数相同，且每个顶点的度数均为2，故两个图同构。
+9. 设G 是弱联通有向图，如果对于G 的任意结点v, d G (v ) =1, 则G 恰
有一条有向回路。试给出证明。
证明：因为G 是弱联通有向图，不妨设一条极大单向联通子图：
+
因为: d G (v ) =1, 所以对V k ，∃e =。若V ≠V 1⋅⋅⋅V k -1，则与极大联通子图矛盾，故V 必为V 1⋅⋅⋅V k -1之一。
又假设有两条以上的回路（反证法），不妨设有两条，则这两条回路上所有点的出度为1，而要使这两条回路联通，则至少其中有一个点
+的出度大于1，这与d G (v ) =1矛盾。故G 恰有一条会向回路。
V 1V 2V k -1V k
10. 设G 为n 阶简单无向图，对G 的任意结点v, d G (v ) ≥(n -1) /2，证明G 是联通的。 证明：
V j
任取V i , V j , 因为d G (v ) ≥(n -1) /2, 故至少存在⎡⎢多还剩余n -2-⎡⎢
n -1⎤
个点与V i 相连，最⎥2⎢⎥
n -1⎤⎡n -1⎤n -1
V i , V j 剩余的点）。故对于V j =-1
至少存在一个与V i 连接的点与V j 相连，因此V i 与V j 联通。由V i 与V j 选取的任意性，G 联通。
11. 证明：对于小于或等于n 的任意正整数k, n阶连通无向图有k
阶连通子图。
证明：n 阶连通无向图，则n 个顶点中的任意点与其他顶点均可达。取其中的k 个顶点也满足该性质，故存在k 阶连通子图。
7.4第181页
1.
解：根据图7-26得邻接矩阵为：
v 1到v 4：
长度为1的基本路径为：v 1→v 4 长度为2的基本路径为：v 1→v 2→v 4 长度为4的基本路径为：v 1→v 2→v 3→v 2→v 4
⎡0⎢0A =⎢
⎢0⎢⎣0
10110100
1⎤⎡0
⎢01⎥2⎥，A =⎢⎢01⎥
⎥⎢0⎦⎣0
1
2101011
1⎤⎡0
⎢01⎥3⎥, A =⎢⎢01⎥
⎥⎢1⎦⎣0
2
1221210
2⎤⎡0
⎢02⎥4⎥, A =⎢⎢02⎥
⎥⎢2⎦⎣0
3
43121223⎤3⎥⎥ 3⎥⎥2⎦
2.
解：（1）对于n=1,2,„,6，试计算矩阵A 1n 中的各元素。
⎡0
⎢0⎢⎢11
A 1=⎢
⎢1⎢1⎢⎣0
01110⎤⎡311
⎢12000011⎥⎥⎢
⎢10200100⎥2
A 1=⎢⎥，
01010⎥⎢211
⎢11210101⎥
⎥⎢
10010⎦⎣110
211⎤⎡425
⎢222111⎥⎥⎢
⎢522120⎥3
A 1=⎢⎥，
311⎥⎢525
⎢752141⎥
⎥⎢
112⎦⎣232
572⎤
253⎥⎥522⎥
⎥，
472⎥745⎥
⎥
252⎦
⎡17⎢9⎢⎢9A 14=⎢
⎢16⎢13⎢⎣916139⎤
84997⎥⎥4109144⎥
，⎥
9917139⎥91413249⎥
⎥
74998⎦
99
⎡38⎢22⎢⎢33A 15=⎢
⎢39⎢51⎢⎣[1**********]2⎤1618223317⎥⎥1818332618⎥
⎥
2233385122⎥3326514433⎥
⎥
1718223316⎦
，
⎡⎢[**************]⎤⎢[1**********]9⎥A 6⎢[1**********]44⎥⎥
1=⎢
⎢[**************]⎥
⎢⎥⎢[**************]7⎥
⎣[1**********]0⎥
⎦
2）
⎡⎢0001100⎤⎡1100⎤
⎢0000011⎥⎢201
0200000⎥⎢001000⎥⎥
⎢
⎢1010100⎥⎥
A 1
⎢02=⎢1
010100⎥⎢⎥，A 2
2
=⎢⎢1003100⎥
⎥ ⎢1001000⎥
⎢1011200⎥
⎢0100000⎥⎢⎥⎢
⎢000
0011⎥
⎥⎣0100000⎥⎦⎢⎣
0000011⎥⎦
⎡⎢2014300⎤⎡70⎢0000022⎥⎢46600⎤
0400000⎥⎢003100⎥⎥
⎢A 3
⎢12=⎢4
032400⎥⎢4032400⎥⎥⎢⎥，A 4
2
=⎢⎢60211600⎥⎥ ⎢3014200⎥
⎢6046700⎥⎢0200000⎥⎢⎥⎢⎢0000022⎥
⎣0200000⎥⎦⎢⎥
⎣0000022⎥⎦⎡⎢1206171300⎤⎡1731290⎢00
00044⎥⎢300
080000⎢0211600⎥⎥
⎢
1114170A 5
⎢62=⎢17
011141700⎥⎢⎢⎥，A 6
⎢1702
=⎢3101445310⎢1306171200⎥
⎢291731300⎢0400000⎥0⎢⎥⎢
⎢00
0004⎣
04
00000⎥⎦⎢⎣
0000043）试求出图中G1和G2中的所有基本循环。
0⎤
0⎥0⎥⎥
0⎥
⎥ 0⎥
4⎥
⎥4⎥⎦
（（
k
对于A 1和A 2，a ii 表示结点v i (i =1,2,...7) 上长度为k 的循环的个数。
3. 对于图7-26中的有向图，试求出邻接矩阵A 的转置A T , AA T , A T A , 列出矩阵A ∧A T 的元素值，并说明它们的意义。
解：A 表示有向图逆图的邻接矩阵，即原图中如果有第i 个结点到第j 个结点长度为1的路径，则A 中第j 行第i 列为1；
第i 个结点和第j 个结点引出的边，可以同时终止于某些结点，这些结点的个数为AA 中第i 行第j 列的元素值。
从某些结点引出的边，可以同时终止于第i 个结点和第j 个结点，这
T
些结点的个数为A A 中第i 行第j 列的元素值。
T
T
T
A ∧A T 中第i 行第j 列对应元素为1表示从第i 个结点和第j 个结点
引出的边，可以同时终止于某些结点；为0表示第i 个结点和第j 个结点引出的边，不可以同时终止于某个结点。 4. 对于nxn 的布尔矩阵A ，试证明：
(I ∨A ) (2)=(I ∨A ) ∧(I ∨A ) =I ∨A ∨A (2)
其中I 是nxn 的单位矩阵，并且有A (2)=A ⨯A 。再证明：对于任何正整数n ∈I +, 都有(I ∨A ) (n ) =I ∨A ∨A 2∨⋅⋅⋅∨A (n )
证明：（1）(I ∨A ) (2)=(I ∨A ) (I ∨A ) ，若该矩阵中的a ij =1, 则存在v k 使得a ik =1且a kj =1，即(I ∨A ) ∧(I ∨A ) , 故(I ∨A ) (2)=(I ∨A ) ∧(I ∨A ) 。又
I ∧A =A ，A ∧I =A (因为I
相当于每个顶点到自己的边，不改变该顶
点到其他顶点的边) ，因此有：(I ∨A ) ∧(I ∨A ) =I 2∨(I ∧A ) ∨(A ∧I ) ∨A 2=
I ∨A ∨A 2, 故问题一得证。
（2）用数学归纳法证明：
当n=2时成立。
假设当n=k是成立，则有：(I ∨A ) (k ) =I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) 当n=k+1时，
(I ∨A ) (k +1) =(I ∨A ) (k ) (I ∨A )
=(I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) (I ∨A ) =(I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∧(I ∨A )
=((I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∧I ) ∨((I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∧A ) =(I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∨((I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∧A ) =(I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ) ∨(A ∨A (2)∨⋅⋅⋅∨A (k ) ∨A (k +1) )
=I ∨A ∨A (2)∨⋅⋅⋅∨A (k ) ∨A (k +1)
故命题成立。
5. 给定简单有向图G =，并且有=n 。设A 是G 的邻接矩阵。试证明：根据第1题中所得到的结果能够把路径矩阵表示成
P =(I ∨A ) (n ) 。
证明：对于有向图的路径矩阵：P =A ∨A (2) ∨(3) ∨⋅⋅⋅∨A (n ) ，而对于第一题有：A ∨A (2) ∨(3) ∨⋅⋅⋅∨A (n ) =I ∨A ∨A (2) ∨(3) ∨⋅⋅⋅∨A (n ) ，故有：
P =I ∨A ∨A (2) ∨(3) ∨⋅⋅⋅∨A (n ) ，由第4题得到：(I ∨A ) (n ) =I ∨A ∨A 2∨⋅⋅⋅∨A (n ) ，
故有：P =(I ∨A ) (n ) ，得证。
6. 图7-27给出一个简单有向图。试求出该图的邻接矩阵A ，并求出其路径矩阵P =A +。 解：
⎡0⎢0⎢A =⎢1
⎢⎢0⎢⎣0⎡0⎢0⎢4
A =⎢0
⎢⎢0⎢⎣0
1000⎤⎡00
⎢000010⎥⎥⎢2
0000⎥，A =⎢01
⎥⎢
0001⎥⎢01
⎢1000⎥⎦⎣001000⎤⎡00⎢000010⎥⎥⎢(5)
0001⎥，A =⎢01
⎥⎢
0001⎥⎢01
⎢1000⎥⎦⎣00
010⎤⎡00
⎢01001⎥⎥⎢3
000⎥，A =⎢00
⎥⎢
000⎥⎢00
⎢010⎥⎦⎣00010⎤
001⎥⎥000⎥，
⎥
000⎥010⎥⎦
001⎤
000⎥⎥010⎥，
⎥
010⎥001⎥⎦
P =A +=A ∨A (2)∨A (3)∨A (4)∨A (5)
⎡01011⎤⎢01011⎥⎢⎥=⎢11011⎥ ⎢⎥01011⎢⎥⎢⎣01011⎥⎦
7. 使给出图7-25中的有向图的距离矩阵。d ij =1意味着什么？ 解：
⎡012∞∞⎤⎢101∞∞⎥⎢⎥
D =⎢210∞∞⎥, d ij =1表示有一条v i 到v j 的边。
⎢⎥∞∞∞01⎢⎥⎢⎣∞∞∞10⎥⎦
8. 试求出第2题中的图G1和G2的距离矩阵。 解：
⎡0⎢2⎢⎢1D 1=⎢
⎢1⎢1⎢⎣2
⎡0
21112⎤⎢∞
⎢03211⎥⎥⎢2
⎥30123⎢
D =, ⎥2⎢121012⎥
⎢1
⎥12101⎢⎥⎢∞13210⎦⎢∞
⎣
∞
∞∞⎤
0∞∞∞11⎥⎥∞012∞∞⎥
⎥
∞101∞∞⎥ ∞210∞∞⎥
⎥
1∞∞∞02⎥1∞∞∞20⎥⎦
211
9. 如何才能从一个距离矩阵中求得一个路径矩阵呢？
证明：对于任意结点v i 和v j （i ≠j ），由题意a ij ≠0，因此从v i 到v j 必定存在一条长度不为0的路径，由结点选取的任意性得：任何两个结点均是联通的。故G 的强联通的有向图。
从距离矩阵求路径矩阵：将距离矩阵中不为0的值变为1，即可得到。 10. 试确定图7-25所示的图是否是强分支。 解：对图7-25由距离矩阵求得的路径矩阵为：
⎡0⎢1⎢P =⎢1
⎢⎢0⎢⎣0
1100⎤
0100⎥⎥
1000⎥，由路径矩阵知该图不是强分支。
⎥
0001⎥0010⎥⎦
7.5第184页
1.
解：a), b), c)是欧拉图，d), e), f)不是欧拉图。
2. 如果G 1和G 2是可运算的欧拉有向图，则G 1⊕G 2仍是欧拉有向图。这句话对吗？如果对，给出证明，如果不对，举出反例。 证明：不对, 不能保证连通.
4. 设G 是平凡的连通无向图，证明：G 是欧拉图，当且仅当G 是若干个边不相交的回路的并。
证明：充分性，当进行若干个不相交的回路的并运算后，每个结点都是偶结点，因此G 是欧拉图。
必要性，对于G 是欧拉图，则G 必定有欧拉闭路。如果某个结点的度数大于2，可以对结点的环路进行分解，分解为多个小的环路的并。
7.6第186页
1. 图7-34是不是二部图？如果是，找出其互补结点子集。 解：是，互补结点子集是：{v 1, v 3, v 5},{v 2, v 4, v 6, v 7}。 2. 如何由无向图G 的邻接矩阵判断G 是不是二部图？
解：设G 的邻接矩阵为A ，=n ，计算A (2) ，A (3) ，„A (n ) 。其中如果矩阵的对角线出现了基数，则G 不是二部图。如果所有的矩阵（包括矩阵A ）的回路长度都是偶数，则是二部图。
3. 举出一个二部图的例子，它不满足定理7.6.3的条件，但是存在完美匹配。
解：如第一题的例子，二部图为：
该图中不满足定理7.6.3的条件（对于V1，在V2中至少有2个结点与其相邻，但是在V2中，各结点最多有有2个结点与V1中结点相邻），但是该图是完美匹配，因为匹配数为3（=1）（如v 1v 2，v 3v 4 ，v 5v 7） 4. 证明：n 阶简单二部图的边数不能超过[n 2/4]。
证明：对于简单二部图，当为完全二部图时边数最多，边数为1*2，又1+2=n ，当1=2即1=2=n /2时，1*2有最大值n 2/4，故边数取整，故边数不能超过[n 2/4]。得证。 5.
解：可能，如下图：
P
1
P 234
6. 解：
张明王同
李林赵丽
7. 图7-35是否存在{v 1, v 2, v 3, v 4}到{u 1, u 2, u 3, u 4, u 5}的完美匹配？如果存在，指出它的一个完美匹配。 解：存在。如：v 1u 2，v 2u 1，v 3u 4，v 4u 5。
7.7第192页
1. 对于下列情况，验证欧拉公式n-m+k=2 (1)图7-45中的多边形的图。
解：对a) 点数7，面的个数3，边的个数8，7+3-8=2，成立。 对b) 顶点个数8，面的个数3，边的个数9，8+3-9=2，成立。 (2)一个具有(r 1) 2个结点的无向边，它描述了r 2个正方形的网络，例如棋盘等。
解：顶点个数为(r +1) 2，面的个数为r 2+1，边的个数为r 2，
(r +1) 2+r 2+1-2r (r +1) =2，成立。
2. 试证明：图7-42b 中的库拉图斯基图是个非平面图。 证明：
对于基本环路：v 1v 2v 3v 4v 5v 1, 考虑v 2v 5和v 3v 5在环的内侧，直线v 1v 4必定在外侧。对于直线v 1v 3和v 2v 4必定相交。故该图是非平面图。 3. 画图所有不同构的6阶非平面图。
解：根据分析图至少有9条边，最多为15条边。所有情况如下图：
9
910
111112
131415
4. 试用库拉斯基定理证明：图7-48中的图是个非平面图。 证明：图7-48中村子一个子图与阶数为6的库拉斯基图同构。将图7-48变形得到：
其中的由{v 1, v 2, v 3, v 4, v 5, v 6}构成的子图与阶数为6的库拉斯基图同构。故该图是非平面图。
5. 图7-49给出一个多边形的图，试构成该图的对偶。
解：对偶图如下：
7.8第204页
1. 画出所有不同构的一、二、三、四、五、六阶树。 解：一阶：
二阶：
四阶(2)
五阶(3)
六阶(6)
2.
如何由无向图G 的邻接矩阵确定G 不是树？
解：根据“G 不含回路而且有n-1条边则G 是树”可以得出图G
是一
棵树的判定条件如下：(1)无线图G 的邻接矩阵A 的n 次幂A n 中，对角线上全是0（说明不存在回路）。（2）邻接矩阵中1的个数的总数为2(n-1),说明边的个数为n-1。邻接矩阵同时满足上面两个条件可以判断图G 是树，如果不同时满足，则判断不是树。
3. 设v 和v '是树T 的两个不同的结点，从v 至v '的基本路径是T 中最长的基本路径。证明：d T (v ) =d T (v ') =1 证明：反证法
假设v 或v '有一个结点的度数大于1，不妨设d T (v ) >1, 则必然存在一个
v ''与v 相连，由树的定义知v ''不在v 至v '的路径中（否则构成了环）。
设v 至v '的路径长度为l ，则v '到v ''的距离为l +1>l ，这与v 至v '的基本路径是T 中最长的基本路径矛盾。故d T (v ) =d T (v ') =1。 4. 。 解：a) b)
7. 证明：任何二叉树有基数个结点。
证明：在二叉树中，任何结点的出度不是0，就是2；假设出度为2的结点有x 个，则该二叉树的出度之和为2x ；设二叉树共有n
个结
点，这些结点中除了根结点的入度为0，其余结点的入度都为1，因此，所有结点的入度之和为n-1。由图的性质，可知二叉树的出度之和与入度之和相等。即n-1=2x， n=2x+1，因此，无论x 如何取值，二叉树的结点总数n 都是基数。得证。
9. 证明：n 阶二叉树的叶子结点数目为(n+1)/2，其高度h 满足log2(n+1)-1≤h ≤ (n-1)/2
证明：（1）在二叉树中，出度为0的结点是叶子结点，出度为2的结点是分支结点，设分支结点个数为x ，由上题证明过程可知，n=2x+1, x=(n-1)/2。因此，叶子结点的个数为n-x=(n+1)/2。
（2）n 阶二叉树的叶子结点有(n+1)/2个，分支结点有(n-1)/2个。利用(n-1)/2个结点构造一棵一元或二元树，设树高为m ，则h=m+1。 考察(n-1)/2个结点构造的一棵一元或二元树，树高最大的情况是一元树，高度为(n-1)/2-1，因此，h 最大值是(n-1)/2-1+1=(n-1)/2。 树高最小的情况是构造了一棵满二叉树，满二叉树的高度x 和结点个数(n-1)/2满足关系2x+1-1=(n-1)/2，解得x=log(n+1)-2，因此h 最小值是log(n+1)-1。因此，log2(n+1)-1≤h ≤ (n-1)/2。 10. 如何由有向图G 的邻接矩阵确定G 是不是有向树？
解：根据有向树的判定定义：仅一个结点的入度为0，其余结点的入度均为1的连通有向图。如果G 是有向树，则其邻接矩阵满足：（1）有且仅有一列全为0。（2）其余的列有且只有一个1。否则有向图不是有向树。
11. 找出叶的权分别为2，3，5，7，11，13，17，19，23，29，31，
37和41的最优叶加权二叉树，并求其叶加权路径长度。
解：对于2,3,5,7,11,13,17,19,23,29,31,37,41，先组合两个最小的权2+3=5，得5,5,7,11,13,17,19,23,29,31,37,41；在所得到的序列中再组合5+5=10，得10,7,11,13,17,19,23,29,31,37,41；再组合10+7=17，得17,11,13,17,19,23,29,31,37,41；继续下去。。。。，过程如下：
5 7 11 13 17 19 23 29 31 37 41
7 11 13 17 19 23 29 31 37 41 11 13 17 19 23 29 31 37 41 17 17 19 23 29 31 37 41 24 19 23 29 31 37 41 24 34 29 31 37 41 34 42 31 37 41 42 53 37 41 42 53 65 65 78 95 238
所得到的最优二叉树如下图：
12. 找出图7-71给出的有向序森林所对应的二元有向有序树，并求其前缀编码。 解：
1： 2：0 3：01 4：011 5：0111 6：00 7：001 8：010 9：01110 10：011101 11：111011 12：1 13：10 14：101 15：100 16：1010 17：10101 18：11 19：110 20：1101 21：1100 22：11001 23：11010 24：110101 25：11000 26：110001 27：1101010 28：11010101 13. 求图7-72的最小生成树。
2
1
3
1
44
解：
7.9第219页
1. 用标号法求图7-86所示的运输网络的最大流，其中无向的边是双向的。
解：求得的网络流量分配如下图：
2. 设x 1, x 2, x 3是三家工厂，y 1, y 2, y 3是三个仓库，工厂生产的产品要运往仓库，其运输网络如图7-87所示，设x 1, x 2, x 3的生产能力分别为40，20，10个单位，问如何安排生产？
解：x 1生产20个单位，x 2生产20个单位，x 3生产10个单位，最多生产50个单位。运输网络分配如下图：
y 1
y 2
3
y 3
3. 七种设备要用五架飞机运往目的地，每种设备各有四台。这五架飞机的容量分别是8，8，5，4，4，问能否有一种装法，使同一种类型设备不会有两台在同一架飞机上？
解：飞机容量为8：类型一4台+类型二4台，飞机容量为8：类型三4台+类型四4台，飞机容量为5：类型五4台，飞机容量为4：类型六4台，飞机容量为4：类型七4台。
4. 在第三题中，若飞机的容量分别是7，7，6，4，4台，求问题的解。 解：各个飞机的分配如下图：
5. 已知开关函数f ab =x 1x 3+x 1x 2x 5+x 2x 3x 4+x 4x 5, 求实现这个简单接触的网络。
解：简单接触网络如下图：