--外文翻译.doc

1、毕业设计(论文)外文资料翻译题 目: 图论的基本概念 院系名称： 理学院 专业班级：信息与计算科学F0801 学生姓名： 学 号： 200848490110 指导教师： 教师职称： 副教授 起止日期： 2012-3-53-16 地点:附 件： 1.外文资料翻译译文；2.外文原文。 指导教师评语： 签名： 年 月 日附件1：外文资料翻译译文1.6 路和联通G的一条途径（或通道）是指一个有限非空序列W= v0 e1 v1 e2 v2ek vk ,它的项交替地为顶点和边，使得对1ik，ei的端点是vi-1 和vi 。称W是从v0 到vk 的一条途径，或一条（v0 ，vk）途径顶点。v0 和vk分别成

2、为W 的起点和终点，而v1 ，v2 ，vk-1 称为它的内部顶点。整数k称为W的长。若W= v0 e1 v1 ek vk 和W= vk ek+1 vk+1 el vl都是途径，则W逆转后所得的途径vk ekvk-1 e1 v0 记为W-1,将W和W在vk 处衔接在一起所得的途径v0 e1 v1 el vl记为W W。途径W= v0 e1 v1 ek vk的节是指W中由相继项构成的子序列vi ei+1 vi+1 ej vj ，它也是一条途径；这一子序列又可称为W的（vi ，vj ）节。在简单图中，途径v0 e1 v1 ek vk 由它的顶点序列v0 v1 vk 所确定；所以简单图的途径可简单地由

3、其顶点序列来表示。不仅如此，即使在非简单图中，我们有时也把相继项均相邻的顶点序列看作为“途径”。在这种场合应该理解为：所作的论述对于具有这种顶点序列的每条途径都是正确的。若途径W 的边e 1，e2 ， ，ek 互不相同，则W称为迹；这时W的长恰好是（W）。又若途径W的顶点v0 ，v1 ， ，vk 也互不相同，则W称为路。图1.8 指出了一个图的途径，一条迹和一条路。“路”一次也可用来表示其顶点和边是一条路的各项的图或子图。uvwxbdyefghca 图1.8途径：uavfyfvgyhwbv迹： wcxdyhwbvgy路： xcwhyeuavG的两个顶点u和v称为连通的，如果在G中存在（u，v）

4、路。连通是顶点集V上的一个等价关系。于是就存在V的一个分类，把V分成非空子集V1 ,V2 , ，Vw，使得两个顶点u和v是连通的当且仅当它们属于同一子集V 。子图GV1 ，GV2 ， ，GVw 称为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

5、证明：G是连通图当且仅当对于把V分为两个非空子集V1 和V2 的每个分类，、 总存在一条边，其一个端点在V1 中而另一个端点在V2中。1.6.5（a）证明：若G是简单图且 （ v-21） ，则G连通。 （b）对于v1，找出一个边数= （ v-21） 的不连通简单图。1.6.6（a）证明：若G是简单图且 v/21，则G连通。 （b）当v是偶数时，找出一个不连通的（v/21）正则简单图。1.6.7 证明：若G 不连通，则GC连通。1.6.8（a）证明：若e E，则w（G）w(Ge)w（G）+1。 （b）设vV，证明：在上面的不等式中，一般不能用Gv代替Ge。1.6.9 证明：若G连通且G的每个顶点

6、的度均为偶数，则对于任何vV，w（Gv）1/2 d(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.12 G的直径是指G的两个顶点之间的最大距离。证明：若G的直径大于3，则Gc 的直径小于3。1.6.13 证明：若G是直径为2的简单图且 =v2，则 2v4。1.6.14 证明：若G是连通简单图但不是完全图，则G有三个顶点u,v和w，使得u

7、v，vw E，而uw E。1.7 圈 称一条途径是闭的，如果它有正的长且起点和终点相同，若一条闭迹的起点和内部顶点互不相同，则它称为圈。与路一样，有时用术语“圈”来表示对应于一个圈的图，长为k的圈称为k圈；按k是奇数或偶数，称k圈是奇圈或偶圈。3圈称为三角形。图1.10给出了闭迹和圈的例子。dvubcaxhgwef闭迹：ucvhxgwfwdvbu 图 1.10 图： xaubvhx利用圈的概念，可以给出偶图的一个特征。定理1.2 一个图是偶图当且仅当它不包含奇圈。 证 设G是具有二分类（X，Y）的偶图，并且设C=v0 v1 vk v0 是G的一个圈。不失一般性，可假设v0 X。因为v0 v1E

8、且G是偶图，所以v1Y。同理v2 X。一般说来，v2i X，且v2i+1 Y，又因为v0 X，所以vk Y。于是对某个i，有k=2i+1，由此即得C是偶图。显然仅对连通图证明其逆命题就够了，设G是不包含奇圈的连通图。任选一个顶点u且定义V的一个分类(X，Y)如下:X=xV|d(u,x)是偶数Y=yV|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 和

9、Q的（u1 ，w）节Q1 必有相同的奇偶性。因此推出（v,w）路P1-1Q1 长为偶数。若v和w相连，则P1-1Q1wv 就是一个奇圈，与假设矛盾，故X中任意两个顶点均不相邻；类似地，Y中任意两个顶点也不相邻。习 题17.1 证明：若边e在G的某闭迹中，则e在G的某圈中。1.7.2 证明：若 2，则G包含圈。1.7.3 证明：若G是简单图且 2，则G包含至少是 +1的圈。1.7.4 G的围长是指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：外文原文（复印件）