2024年4月25日发(作者：谯光赫)
图论第二版答案
【篇一：图论与代数结构第一二三章习题解答】
厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；
这样就得到一个无向图。若每点的度数为3，则总度数为27，与图
的总度数总是偶数的性质矛盾。若仅有四个点的度数为偶数，则其
余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是
偶数的性质矛盾。（或者利用度数为奇数的点的个数必须为偶数个）
2. 若存在孤立点，则m不超过kn-1的边数, 故
m = (n-1)(n-2)/2, 与题设矛盾。
?－
3. 记ai为结点vi的正度数，ai为结点vi的负度数，则
nnnn? 2? 22－ ai?[(n?1)?ai]?n(n?1)?2(n?1)ai＋ai－ 2，
i?1i?1i?1i?1 nnn－2? 2 因为 ai?cn?n(n?1)/2， 所以
ai?ai－ 2。
i?1i?1i?1
4. 用向量(a1,a2,a3)表示三个量杯中水的量, 其中ai为第i杯中水的
量, i = 1,2,3.
以满足a1+a2+a3 = 8 (a1,a2,a3为非负整数)的所有向量作为各结点,
如果(a1,a2,a3)中某杯的水倒满另一杯得到 ( a’1, a’2, a’3 ) , 则由结
点到结点画一条有向边。这样可得一个有向图。
本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以
下即是这样的一条： ( 8, 0, 0 ) ( 5, 0, 3 ) ( 5, 3, 0 ) ( 2, 3, 3 ) ( 2, 5,
1 )
(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 1, 3 ) ( 4, 4, 0 )
5. 可以。
???????
6 若9个人中没有4个人相互认识，构造图g，每个点代表一个点，
两个人相互认识则对应的两个点之间有边。
1） 若可以找到点v，d(v)5，则与v相连的6个点中，要么有3个
相互认识，要么有3个
相互不认识（作k6并给边涂色:红=认识，蓝=不认识，只要证图中
必有同色三角形。v1有5条边，由抽屉原则必有三边同色(设为红)，
这三边的另一顶点设为v2, v3, v4。若 △v2v3v4有一边为红，则与
v1构成红色△，若△v2v3v4的三边无红色，则构成蓝色△）。若有
3个人相互认识，则这3个人与v相互认识，这与假设没有4个人相
互认识矛盾，所以这6个人中一定有3个人相互不认识
2） 若可以找到点v，d(v)5，不与v相连的点至少有4个，由于没
有4个人相互认识，所
以这4个人中至少有2个人相互不认识，这两个人与v共3个人相
互不认识
3） 若每个点的度数都为5，则有奇数个度数为奇数的点，不可能。
7. 同构。同构的双射如下：
8. 记e1= (v1,v2), e2= ( v1,v4), e3= (v3,v1), e4= (v2,v5), e5=
(v6,v3), e6= (v6,v4), e7= (v5,v3), e8= (v3,v4), e9 = (v6,v1), 则
?
?010100??11?100000?000010?
邻接矩阵为： ?1 1 0????10010000
0 0 0 ? ? 0010?10?11
??000000? ,关联矩阵为：
???0?1000?10?1
?001000??000?1001 ???0 ??101100????00001100边列表为：
a= (1,1,3,2,6,6,5,3,6), b= (2,4,1,5,3,4,3,4,1).
正向表为：a= (1,3,4,6,6,7,10), b= (2,4,5,1,4,3,3,4,1).
?1?0?0??0??0?1???
习题二
1. 用数学归纳法。k=1时，由定理知结论成立。设对于k命题成立。
对于k+1情形，设前k个连通支的结点总个数为n1, 则由归纳假设，
前k个连通支的总边数m1= ( n1－k+1)( n1－k)/2。最后一个连通支
的结点个数为n－n1, 其边数
m2= ( n－n1)( n－n1－1)/2，
所以，g的总边数
m= m1+ m2= ( n1－k+1)( n1－k)/2 + ( n－n1)( n－n1－1)/2
n1=n－1时，m= ( (n-1)－k+1)( (n-1)－k)/2 +0= ( (n－k)( (n－k－
1)/2, 命题成立。 n1＜= n－2时，由于 n1=k, 故
m= ( (n－2)－k+1)( n1－k)/2 + ( n－n1)( n－k－1)/2＝( n－k)( n－
k－1)/2 , 命题成立。
2．若g连通，则命题已成立；否则， g至少有两个连通支。
任取结点v1, v2，若g的补图中边(v1, v2)不存在，则(v1, v2)是g
中边，v1, v2在g的同一个连通支（假设为g1）中。设g2是g的
2024年4月25日发(作者：谯光赫)
图论第二版答案
【篇一：图论与代数结构第一二三章习题解答】
厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；
这样就得到一个无向图。若每点的度数为3，则总度数为27，与图
的总度数总是偶数的性质矛盾。若仅有四个点的度数为偶数，则其
余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是
偶数的性质矛盾。（或者利用度数为奇数的点的个数必须为偶数个）
2. 若存在孤立点，则m不超过kn-1的边数, 故
m = (n-1)(n-2)/2, 与题设矛盾。
?－
3. 记ai为结点vi的正度数，ai为结点vi的负度数，则
nnnn? 2? 22－ ai?[(n?1)?ai]?n(n?1)?2(n?1)ai＋ai－ 2，
i?1i?1i?1i?1 nnn－2? 2 因为 ai?cn?n(n?1)/2， 所以
ai?ai－ 2。
i?1i?1i?1
4. 用向量(a1,a2,a3)表示三个量杯中水的量, 其中ai为第i杯中水的
量, i = 1,2,3.
以满足a1+a2+a3 = 8 (a1,a2,a3为非负整数)的所有向量作为各结点,
如果(a1,a2,a3)中某杯的水倒满另一杯得到 ( a’1, a’2, a’3 ) , 则由结
点到结点画一条有向边。这样可得一个有向图。
本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以
下即是这样的一条： ( 8, 0, 0 ) ( 5, 0, 3 ) ( 5, 3, 0 ) ( 2, 3, 3 ) ( 2, 5,
1 )
(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 1, 3 ) ( 4, 4, 0 )
5. 可以。
???????
6 若9个人中没有4个人相互认识，构造图g，每个点代表一个点，
两个人相互认识则对应的两个点之间有边。
1） 若可以找到点v，d(v)5，则与v相连的6个点中，要么有3个
相互认识，要么有3个
相互不认识（作k6并给边涂色:红=认识，蓝=不认识，只要证图中
必有同色三角形。v1有5条边，由抽屉原则必有三边同色(设为红)，
这三边的另一顶点设为v2, v3, v4。若 △v2v3v4有一边为红，则与
v1构成红色△，若△v2v3v4的三边无红色，则构成蓝色△）。若有
3个人相互认识，则这3个人与v相互认识，这与假设没有4个人相
互认识矛盾，所以这6个人中一定有3个人相互不认识
2） 若可以找到点v，d(v)5，不与v相连的点至少有4个，由于没
有4个人相互认识，所
以这4个人中至少有2个人相互不认识，这两个人与v共3个人相
互不认识
3） 若每个点的度数都为5，则有奇数个度数为奇数的点，不可能。
7. 同构。同构的双射如下：
8. 记e1= (v1,v2), e2= ( v1,v4), e3= (v3,v1), e4= (v2,v5), e5=
(v6,v3), e6= (v6,v4), e7= (v5,v3), e8= (v3,v4), e9 = (v6,v1), 则
?
?010100??11?100000?000010?
邻接矩阵为： ?1 1 0????10010000
0 0 0 ? ? 0010?10?11
??000000? ,关联矩阵为：
???0?1000?10?1
?001000??000?1001 ???0 ??101100????00001100边列表为：
a= (1,1,3,2,6,6,5,3,6), b= (2,4,1,5,3,4,3,4,1).
正向表为：a= (1,3,4,6,6,7,10), b= (2,4,5,1,4,3,3,4,1).
?1?0?0??0??0?1???
习题二
1. 用数学归纳法。k=1时，由定理知结论成立。设对于k命题成立。
对于k+1情形，设前k个连通支的结点总个数为n1, 则由归纳假设，
前k个连通支的总边数m1= ( n1－k+1)( n1－k)/2。最后一个连通支
的结点个数为n－n1, 其边数
m2= ( n－n1)( n－n1－1)/2，
所以，g的总边数
m= m1+ m2= ( n1－k+1)( n1－k)/2 + ( n－n1)( n－n1－1)/2
n1=n－1时，m= ( (n-1)－k+1)( (n-1)－k)/2 +0= ( (n－k)( (n－k－
1)/2, 命题成立。 n1＜= n－2时，由于 n1=k, 故
m= ( (n－2)－k+1)( n1－k)/2 + ( n－n1)( n－k－1)/2＝( n－k)( n－
k－1)/2 , 命题成立。
2．若g连通，则命题已成立；否则， g至少有两个连通支。
任取结点v1, v2，若g的补图中边(v1, v2)不存在，则(v1, v2)是g
中边，v1, v2在g的同一个连通支（假设为g1）中。设g2是g的