tulun

第七章 图论

1设P={u,v,w,x,y},画出图G={P，L}，其中 （1）L={uv,ux,uw,vy,xy};

(2)L={uv,vw,wx,wy,xy},并指出各个点的度。 解 对应于（1）的图如图7—1所示。

其中各点的度为：dG (u)=3, dG (x)=2, dG (y)=2, dG (v)=2, dG (w)=1.

对应于（2）的图如7—2所示。各点的度为：dG (u)=1, dG (x)=2, dG (y)=2, dG (v)=2, dG (w)=3。

U V U V X Y Y

W W

X

图7—1

2 设图G有5个点，4条边，在同构的意义下，画出图G的所有可能形式。

解 图7—3是图G的所有可能形式。

1

(a) (b) (c) (d)

(e) (f) (g)

图7—2 图7--3

3 图G=（P，L）如图7—4所示，试画出G的三个不同支撑子图。

图7--4

解 图7—5（a）,(b),(c)就是图G的三个支撑子图。

（a） (b) (c) 图7--5

4 是否可以画一个图，使各点的度与下面给出的序列一致，如可能，画出一个符合条件的

2

图，如不可能，说明原因。 （1）3，3，3，3，3，3； （2）3，4，7，7，7，7； （3）1，2，3，4，5，5；

解 （1）可以，如图7—6所示：

图7—6

（2）不可能。在六个顶点中，奇数度点为5个，与定理2相矛盾。

（3）不可能。考虑两个度为5的顶点，设其为u和v，因为只有6个顶点，因此u和v除自身之外的个顶点皆相连。而除u，v之外的4个顶点中的每一个都至少是两条边的端点，即这4个顶点的度都至少是非，这与其中某一个顶点的度为1矛盾。

/ 2

5 设G是有限图，M，A分别是G的关联矩阵和相邻矩阵，证明：M*M和A 的对角线

上的元素恰好是G中所有点的度。

证 设L（G），P（G）的元素分别为n,m. 令B= M*M/ ，由矩阵的乘法定义知

nbii=

j?1/

aij * aji

i=1,2,3---------m

因为M/ 是M的转置矩阵，所以 aij= a/ji，，又因为aij非0即1，所以aij2 = aij 故

n得bii=

?j?1 aij * aji=

/

n?j?1 aij

2

n=?j?1 aij

即bii等于M的第I 行中所有1的个数，也就是bii等于M的第I行所对应的点

的度。故M*M/ 的对角线上的元素是G中所有点的度。

令C=A则Cii=

2

m?aji?ajij?1 I=1,2,------,m

mm因为A 是对称矩阵，所以aij=aji,aij2=aij,所以cii=?j?1aij?aji=

?j?1 aij=

2

m?j?1aij.

即cii等于第I行所有1的个数，即第I行所对应点的度，（I=1，2，-------M）。故A2的

对角线上的元素是G中所有点的度。 6 设G 是有限图，P（G），L（G）的元素分别为m,n,＆ △分别是G中点的最小度现最

3

大度。证明：＆≤2n／m≤△

证 因为 ＆ △分别是G中点的最小度和最大度，因此有m*＆≤ ≤m*△ 又因为 =2n，所以m*＆≤ 2n ≤m*△ 即 ＆≤2n／m≤△ 证毕

7 证明连通图中两条最长年简单路必有公共点。 证 用反证法。若不然，设两条最长路为l1=(u,-----u/),l2=(v----v/).因为图是连通的，故从u 到 v有路，设此路最后一次离开l1的点是w ,第一次进入l2的点是w，由题设可知，

/

w≠w,见图7—7：

L1 N’

L2 W’ V’

W

/

/

图7—7

取max{ (u,------,w),(w,-----, u/)}∪{(w,----,w/)}∪ max{ (v,-----, w/),( w/,-----, v/)便得到一条更长的简单路，与l1，l2是两条最长的简单路矛盾。因此，连通图中任意两条最长的简单路必有公共点。

8 一公司在六个城市C1，C2，----，C6中每一个都有分公司，从CI到CJ的班机旅费由下列矩阵中第I行第J列的元素给出（∞表示没有直接班机）。 0 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0

公司所关心的是计算两城市间的费用最低的路线，对上述六城市中任意一对城市，计算两城市间费用 最低的路线。

解 首先，求C1到C2，----，C6的最短路线。

（1） 从C2，---，C6，中找出与C1距离最近的一个，为C6，于是l（C6）=10，最短

路线C1→C6。 （2） 从d（C1，Ci），l(C6)+d(C6,Ci)中选取最小者，其中i2,3,4,5,可得dC1，C5），于

是lC5）=25，最短路线C1→C5。 （3） 类似于步骤（2），依次可得：l（C4）=15，最短路线C1→C6→C4； l（C2）=35，最短路线C1→C6→C2； l（C3）=45，最短路线C1→C5→C3

4

对于城市C2，----，C6，可以用类似于C1的方法得到最短路线 。

9 设G是图，＆是G 中最小度，K 是一个正整数，若k≤＆，试证明G 中有一

条长为k的简单路。

证明 不妨设＆≥0，当＆=0时，命题显然成立。以下设＆≠0，任取一点v0,显然d(v0)≥＆, 故可找到一相邻点v1。

设已找到vi, i＜＆. 由 d(vi)≥＆, 看vi 的相邻点，至少有一个不同于v0，v1，---，是vi –1取这样一个点设为vi+1；如此下去可一直找到v﹠，而（v0，v1，---，v﹠）正是

一条长为﹠的简单路。因此，若k≤＆,则必有一条长为k的简单路。

10 设G为图（可能无限），无回路，但若外加任意一边于G 后就形成一回路，试7证明G必为树。

证 按树的定义可知，只需证G为连通即可。任取不相领两点v,v1,由已知，加上边vv1后就形成一回路。于是去掉边vv1，从v到v1仍有路v,…,v1,即v,v1相连。由v,v1 的任意性可知G是连通的。因此，G必为树。 证毕。 11 在具有n个顶点的完全图kn中需删去多少条边才能得到树？

解 n个点的完全图kn中共有Cn2条边，而n个点中的树中共有n-1条边。因此需要 删除cn-(n-1)=.(n-1)(n-2)/2条边后方可得到树。

12 分别用三种不同的遍历方式写出图7-8中二叉树点的访问次序。 A

B C G D

E J

H I

K L

F

2

图7-8 解 先根次序：ABDEHKLCFGIJ; 中根次序：DBEKHLAFCIGJ; 后根次序：DKLHEBFIJGCA. 13 分别写出下列表达式的后缀表示： （1） （a+b）*c;

(2) ln(a+b)-c+e*f.

解 （1）首先将表达式化成二叉树如图7-9（a）,由此可知表达式的后缀表示为：ab+c*.

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库tulun在线全文阅读。