图论的基本概念外文翻译.pdf

  1. 1、本文档共6页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多

图论的基本概念-外文翻译

毕业设计论文外文资料翻译

题目:图论的基本概念院系名称:理学院专业班级:信息与计算科

学F0801学生姓名:学号:200848490110

指导教师:教师职称:副教授

起止日期:2012-3-5~3-16地点:

附件:1.外文资料翻译译文;2.外文原文。

指导教师评语:签名:年月日

附件1:外文资料翻译译文

1.6路和联通

G的一条途径(或通道)是指一个有限非空序列Wv0e1v1e2v2…ekvk,

它的项交替地为顶点和边,使得对1≤i≤k,ei的端点是vi-1和vi。称W是从

v0到vk的一条途径,或一条(v0,vk)途径顶点。v0和vk分别成为W的起点和

终点,而v1,v2,…,vk-1称为它的内部顶点。整数k称为W的长。

若Wv0e1v1…ekvk和W’vkek+1vk+1…elvl都是途径,则W

逆转后所得的途径vkekvk-1…e1v0记为W-1,将W和W’在vk处衔接在一起

所得的途径v0e1v1…elvl记为WW’。途径Wv0e1v1…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指

出了一个图的途径,一条迹和一条路。“路”一次也可用来表示其顶点和边是一条

路的各项的图或子图。

途径: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),

文档评论(0)

180****8094 + 关注
实名认证
内容提供者

小学毕业生

1亿VIP精品文档

相关文档