- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 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),
您可能关注的文档
- 常见测试点总结.pdf
- 国家开放大学电大专科《建筑构造》机考网考标准试题及答案11.pdf
- 托业阅读(词汇与语法)模拟试卷5(题后含答案及解析).pdf
- 门、急诊工作质量考核标准.pdf
- 李嘉诚成功案例分析.pdf
- 实用的科技创新作文5篇.pdf
- 职业培训学校考核制度.pdf
- 九年级历史上学期复习课的教学反思.pdf
- 2022白露暖心文案句子80条.pdf
- 人教历史与社会七上《第二单元 第三课 第二课时 不同肤色的人们教案 人教版.pdf
- 2021-2022学年湖南省常德市安乡县四年级上学期期中语文真题及答案.pdf
- 2023-2024学年河南省南阳市社旗县四年级上学期期中数学真题及答案.pdf
- 2022-2023学年云南省曲靖市四年级下学期期末数学真题及答案.pdf
- 2021-2022学年河南省周口市鹿邑县二年级下册月考语文真题及答案.pdf
- 2018年河南焦作解放区教师招聘考试真题及答案.pdf
- 2019年江西公务员行测考试真题及答案-乡镇.pdf
- 2019中国石油报社应届高校毕业生招聘试题及答案解析.pdf
- 光大银行招聘应届毕业生能力素质测试笔试真题及答案.pdf
- 2024年广西百色教师招聘考试模拟题及答案.pdf
- 2021-2022学年浙江绍兴诸暨市五年级上册语文期末试卷及答案.pdf
文档评论(0)