--外文翻译.doc
- 文档编号:5942127
- 上传时间:2023-05-09
- 格式:DOC
- 页数:9
- 大小:157.44KB
--外文翻译.doc
《--外文翻译.doc》由会员分享,可在线阅读,更多相关《--外文翻译.doc(9页珍藏版)》请在冰点文库上搜索。
毕业设计(论文)外文资料翻译
题目:
图论的基本概念
院系名称:
理学院专业班级:
信息与计算科学F0801
学生姓名:
学号:
200848490110
指导教师:
教师职称:
副教授
起止日期:
2012-3-5~3-16地点:
附件:
1.外文资料翻译译文;2.外文原文。
指导教师评语:
签名:
年月日
附件1:
外文资料翻译译文
1.6路和联通
G的一条途径(或通道)是指一个有限非空序列W=v0e1v1e2v2…ekvk,它的项交替地为顶点和边,使得对1≤i≤k,ei的端点是vi-1和vi。
称W是从v0到vk的一条途径,或一条(v0,vk)途径顶点。
v0和vk分别成为W的起点和终点,而v1,v2,…,vk-1称为它的内部顶点。
整数k称为W的长。
若W=v0e1v1…ekvk和W’=vkek+1vk+1…elvl都是途径,则W逆转后所得的途径vkekvk-1…e1v0记为W-1,将W和W’在vk处衔接在一起所得的途径v0e1v1…elvl记为WW’。
途径W=v0e1v1…ekvk的节是指W中由相继项构成的子序列viei+1vi+1…ejvj,它也是一条途径;这一子序列又可称为W的(vi,vj)节。
在简单图中,途径v0e1v1…ekvk由它的顶点序列v0v1…vk所确定;所以简单图的途径可简单地由其顶点序列来表示。
不仅如此,即使在非简单图中,我们有时也把相继项均相邻的顶点序列看作为“途径”。
在这种场合应该理解为:
所作的论述对于具有这种顶点序列的每条途径都是正确的。
若途径W的边e1,e2,…,ek互不相同,则W称为迹;这时W的长恰好是ε(W)。
又若途径W的顶点v0,v1,…,vk也互不相同,则W称为路。
图1.8指出了一个图的途径,一条迹和一条路。
“路”一次也可用来表示其顶点和边是一条路的各项的图或子图。
u
v
w
x
b
d
y
e
f
g
h
c
a
图1.8
途径:
uavfyfvgyhwbv
迹:
wcxdyhwbvgy
路:
xcwhyeuav
G的两个顶点u和v称为连通的,如果在G中存在(u,v)路。
连通是顶点集V上的一个等价关系。
于是就存在V的一个分类,把V分成非空子集V1,V2,…,Vw,使得两个顶点u和v是连通的当且仅当它们属于同一子集V。
子图G[V1],G[V2],…,G[Vw]称为G的分支。
若G是不练通的。
G的分支个数记为w(G)。
图1.9画出了连通的和不练通的。
(a)
。
(b)
图1.9(a)一个连通图;(b)一个有三个分支的不连通图
习题
1.6.1证明:
若在G中存在(u,v)途径,则在G中也存在(u,v)路。
1.6.2证明:
G中长为k的(vi,vj)途径的数目就是Ak中的第(i,j)元素。
1.6.3证明:
若G是简单图且δ≥k,则G有长为k的路。
1.6.4证明:
G是连通图当且仅当对于把V分为两个非空子集V1和V2的每个分类,、
总存在一条边,其一个端点在V1中而另一个端点在V2中。
1.6.5(a)证明:
若G是简单图且ε>(v-21),则G连通。
(b)对于v>1,找出一个边数ε=(v-21)的不连通简单图。
1.6.6(a)证明:
若G是简单图且δ>[v/2]—1,则G连通。
(b)当v是偶数时,找出一个不连通的([v/2]—1)正则简单图。
1.6.7证明:
若G不连通,则GC连通。
1.6.8(a)证明:
若e∈E,则w(G)≤w(G—e)≤w(G)+1。
(b)设v∈V,证明:
在上面的不等式中,一般不能用G—v代替G—e。
1.6.9证明:
若G连通且G的每个顶点的度均为偶数,则对于任何v∈V,w(G—v)≤1/2d(v)成立。
1.6.10证明:
在连通图中,任意两条最长路必有公共顶点。
1.6.11若在G中顶点u和v是连通的,则u和v之间的距离dG(u,v)是G中最短(u,v)路的长;若没有路连接u和v,则定义dG(u,v)为无穷大。
证明:
对于任何三个顶点u,v和w,d(u,v)+d(v,w)≥d(u,w)成立。
1.6.12G的直径是指G的两个顶点之间的最大距离。
证明:
若G的直径大于3,则Gc的直径小于3。
1.6.13证明:
若G是直径为2的简单图且Δ=v—2,则ε≥2v—4。
1.6.14证明:
若G是连通简单图但不是完全图,则G有三个顶点u,v和w,使得uv,vw∈E,而uwE。
1.7圈
称一条途径是闭的,如果它有正的长且起点和终点相同,若一条闭迹的起点和内部顶点互不相同,则它称为圈。
与路一样,有时用术语“圈”来表示对应于一个圈的图,长为k的圈称为k圈;按k是奇数或偶数,称k圈是奇圈或偶圈。
3圈称为三角形。
图1.10给出了闭迹和圈的例子。
d
v
u
b
c
a
x
h
g
w
e
f
闭迹:
ucvhxgwfwdvbu
图1.10图:
xaubvhx
利用圈的概念,可以给出偶图的一个特征。
定理1.2一个图是偶图当且仅当它不包含奇圈。
证设G是具有二分类(X,Y)的偶图,并且设C=v0v1…vkv0是G的一个圈。
不失一般性,可假设v0∈X。
因为v0v1∈E且G是偶图,所以v1∈Y。
同理v2∈X。
一般说来,v2i∈X,且v2i+1∈Y,又因为v0∈X,所以vk∈Y。
于是对某个i,有k=2i+1,由此即得C是偶图。
显然仅对连通图证明其逆命题就够了,设G是不包含奇圈的连通图。
任选一个顶点u且定义V的一个分类(X,Y)如下:
X={x∈V|d(u,x)是偶数}
Y={y∈V|d(u,y)是奇数}
现在证明(X,Y)是G的一个二分类。
假设v和w是X的两个顶点,P是最短的(u,v)路,Q是最短的(u,w)路,以u记P和Q的最后一个公共顶点。
因P和Q是最短路,
P和Q二者的(u,u1)节也是最短的(u,u1)路,故长相同。
现因P和Q的长都是偶数,所以P的(u1,v)节P1和Q的(u1,w)节Q1必有相同的奇偶性。
因此推出(v,w)路P1-1Q1长为偶数。
若v和w相连,则P1-1Q1wv就是一个奇圈,与假设矛盾,故X中任意两个顶点均不相邻;类似地,Y中任意两个顶点也不相邻。
习题
1.7.1证明:
若边e在G的某闭迹中,则e在G的某圈中。
1.7.2证明:
若δ≥2,则G包含圈。
1.7.3证明:
若G是简单图且δ≥2,则G包含至少是δ+1的圈。
1.7.4G的围长是指G中最短圈的长;若G没有圈,则定义G的围长为无穷大。
证明:
(a)围长为4的k正则图至少有2k个顶点,且(在同构意义下)在2k个顶点上恰好有一个这样的图;
(b)围长为5的k正则图至少有k2+1个顶点。
1.7.5证明:
围长为5,直径为2的k正则图恰好有k2+1个顶点,当k=2,3时找出这种图来。
(Hoffman和Singleton在1960年已证明:
这种图仅当k=2,3,7,可能还有57时存在。
)
1.7.6证明:
(a)若ε≥v,则G包含圈;
(b)若ε≥v+4,则G包含两个边不重的圈。
附件2:
外文原文(复印件)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 外文 翻译