图论第二版答案.pdfVIP

图论第二版答案

【篇一：图论与代数结构第一二三章习题解答】

厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；

这样就得到一个无向图。若每点的度数为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?1nnn－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)的一条有向路，以

下即是这样的一条：

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?

邻接矩阵为：?110???

000??0010?10?11

??000000?,关联矩阵为：

???0?1000?10?1

?001000??000?1001???0??101100???边列表为：

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,则由归纳假设，