tulun
更新时间:2024-05-23 23:11:01 阅读量: 综合文库 文档下载
第七章 图论
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
C C E F 1N A B
图7-9
(2)首先将表达式化为二叉树,如图7-9(b),从而表达式的后缀表示为: ab+㏑c-ef*+.
14 设有5个城市v1,…,v5,任意两城市之间铁路造价如下(以百万元为单位): W(v1,v2)=4, W(v1,v3)=7, W(v1,v4)=16, W(v1,v5)=10, W(v2,v3)=13, W(v2,v4)=8, W(v2,v5)=17, W(v3,v4 )=3, W(v3 ,v 5)=10, W(v 4,v 5)=12.
试求出连接5个城市而且造价最低的铁路网。
解 首先将本题用一权图来描述,于是求解此题便成为求权图中的最优支撑树问题。
按克鲁斯卡尔算法,图7-10中(b)~ (e) 就是求解最优支撑树的过程。
V1 7
4
V3 16 13 V2
10 8 10 17 3
V4 12 V5
(a)
V3 3 V4
(b)
6
V1 V1 V1 7 7 4
V3 V2 V1 V2 V3 V2
3 3 3 10
(c) (d) (e)
15 试用克鲁斯卡尔算法求图7-11所示权图中的最优支撑树。
1
7
3 4
9 2
5
5 6
8 7 3
图7-11
解 图7-12(a)~ (e) 表示图7-11的最优支撑树。
1
1
1 2
3
(a) (b) (c)
1
3
1
3
2
3
5
2
3
7
2
(d) (e) 16 举出满足下列要求的具有5个点的有向图: (1)G有根,但是 不是强连通的;
(2)G存在一棵有向支撑子树,并标出这棵有向树; (3)G 是强连通的(将 G漠视为于是强连通的),但 G无根。 解 (1)如图7-13(a), A是根,但是不存在从 B到D 的有向路。 (2)如图7-13(b),图7-13(c)是7-13(b)的一棵有向支撑树。 (3)如图7-13(d)。
(a) (b) (c) (d)
17 设 G(P,A)是有向图,G中任意两个不同点之间至多有一条弧,G中没有指向自身的弧,若不考虑G中弧的方向,把弧看成边,则 G是连通的。问 G是否有根?若能肯定 G有根,试给出证明,否则举出反例。
解 回答是否定的。举例如图7-13(d),将此有向图漠视为图以后,它是连通的,但它却无根。
18 设G=(P,A)为有向图,若G与根r,且无有向回路,问G是否是有向树? 解 回答是否定的,举反例如图7-13中(a)。
19 证明:若r是有向图G的根,则G必含有一个以r为根的有向支撑树。
G1 G 2
图7-14 证 用如下方法来构造的支撑树:
令G0={r},设已得GK是有向树,做GK+1如下:
选取P(G)中的某顶点v,使得v∈P(Gk)。设从v到r的有向路进入Gk后第一个顶点v’,进入Gk前的最后一个顶点是v”,再在GK中加入弧v”v’,及顶点v”。
8
又归纳法可证,GK是有向树。
按如上做法便可得到G中以r为根的支撑树。 20 能否对图7-14的边指定方向,使其成为欧拉图?
解 G可以,如图7-15(a)所示,由于G1中的每一个点都是平衡点。
G2不可以,图7-15(b)中所有点的度都是3,因此不论怎样指定边的方向,G2中的每个点都不是平衡点。因此不可能适当地指定G2中各边的方向,使其成欧拉图。
(a) (b) 图7-15
21 下列图形是否可以一笔画出?如可以的话画出欧拉图,否则说明原因。
G1 G 2 图7-16
解 不可以。因为中有8个度为奇数的顶点。
可以。按照边上的标号依次读下来,便可以一笔画出。见图7-17
9
1
5 6 16
4
12 13
11
10 9 14
7
2
8
3
图7-17
21 举出满足下列要求的具有5个点的图。
(1)没有哈密顿回路,也不能适当指定各边的方向使其具有欧拉路; (2)有哈密顿回路,但是不能适当指定各边的方向使其具有欧拉路; (3)没有哈密顿回路,但是能适当指定各边的方向使其具有欧拉路; (4)有哈密顿回路,也能适当指定各边的方向使其具有欧拉路。 解 见图7-18(a)~(d),它们分别满足条件(1)~(4)
(a) (b)
(c) (d)
图7-8
23 使用平面图定义及Jordan曲线性质证明K3..3是非平面图。
证 用反证法。K3..3如图7-19(a)所示,假设可以把K3..3画成一个平面图。
10
回路v1v6v3v4v1构成一个Jorand曲线,设其为C,如图7-19(b),顶点v2或在ext(C)中,不妨假定v2∈int(C),于是边v2v4,v2v6 将int(C)分成两个区域。设C1=v1v4v2v6v1,G2=v4v2v6v3v4,v5必然位于ext(C),int(C1),int(C2)三个区域之一。 (1) 若v5∈int(C),则v2v5与C相交,与K3..3是平面图矛盾。 (2) 若v5∈int(C1),则v3v5与C1相交,也矛盾。 (3) 若v5∈int(C2),则v1v5与C2相交,同样产生矛盾。 同理可证,当v2∈ext(C)时,也产生矛盾。 故假设不成立,即K3..3不是平面图。
V1
V2
V1
V6
Int(C1)
Ext(C)
V4
V5
V6 V4
(a) (b)
图7-19
24 设G是连通平面图,最短回路长度是k(k≥3),边数为u,顶点数为v,证明 u≤k(v-2)/(k-2) 证 因为最短回路长度是,而平面图的每一个面是由一个回路所围起来的,因此对于任一个面都有,于是有
∑f∈F(G)dG(f)≥k& 其中&是图G的面数。
再由∑f∈F(G)dG(f)=2u
可知2u≥k&,即2u/k≥&,根据欧拉公式可得 v-u+2u/k≥2
由此可以推出u≤k(v-2)/(k-2).
25 利用上题结果说明下面各图不是平面图。
V3
11
(a) (b) 图7-20
解 图7-20()中:边数u=9,顶点数v=6,最短路长k=4,因为
u=9≦k(v-2)/(k-2)=8 于是,由上题结果可知7-20(a)不是平面图。
图7-20()中:边数u=15,顶点数v=10,最短路长k=5,因为 u =15≦k(v-2)/(k-2)=40/3 因此7-20(b)不是平面图。
26 若是平面图,并且的所有面全由长度为3的回路围成,证明:u=3v-6。
证 因为中所有面由长度为3的回路围成,因此对任意f∈F(G),都有dG(f)=3,从而∑f∈其中﹠为F(G)dG(f)=3﹠。代入欧拉公式,得
v-u+2u/3=2
即 u=3v-6 证毕。
G的面数。再由∑f∈F(G)dG(f)=2u,其中u为G的边数,可得3﹠=2u,
12
正在阅读:
tulun05-23
《人机工程学》第1章 绪论07-26
诗歌鉴赏探究古诗词中画面的描述12-09
工程力学I模拟试题一答案09-30
《毛泽东思想和中国特色社会主义理论体系概论》2011年春期实践教06-22
幼儿园教育叙事故事02-20
迎奥运2008′全国首届职业院校技能大赛01-08
大班科学《小蚂蚁了不起》活动设计10-26
《国际金融实务》(刘玉操)教师手册04-07
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 公司各个岗位360度考核表.
- 初二第一学期历史教学质量检测试卷 - 2 - 图文
- A数据挖掘2.0 - 图文
- 小组合作学习专题研讨会发言稿:行动就有收获
- 如何培养幼儿折纸艺术活动的行动研究
- (太管用了)公文写作经典小标题字典
- 农村完小新课程实施面临的困难与思考
- 浅析教育系统食堂财务管理工作
- 新局势下如何提升政府统计公信力的思考
- 2014中小学生安全知识竞赛答案
- 2019年整理营销管理
- 运动会志愿者题库
- 彩钢板屋面维修施工方案 - 0000 - 图文
- 人教版新目标英语八年级下册教案(重新整理纯净打印版)
- 安监总局 安监总厅管三函〔2012〕100号《关于危险化学品建设项目
- 辅导员能力大赛试题
- 2010年中考化学试卷分析
- 2012年6月物业管理实务—案例分析参考答案
- 小学足球课教案全集
- 荷兰式招标