离散数学及其应用论文翻译原文和译文.doc

本科毕业设计（论文）外文翻译译文本科毕业设计（论文）外文翻译译文学生姓名学生姓名： 院院 （系）：（系）： 理学院理学院 专业班级专业班级： 信息信息 0901 班班 指导教师指导教师： 完成日期完成日期： 2013 年年 3 月月 20 日日 0离散数学及其应用 Discrete Mathematics and Its Applications 作者：作者： Kenneth H.Rosen起止页码：起止页码：115-122, 641-758出版日期（期刊号）：出版日期（期刊号）：2008.3.1出版单位：机械工业出版社出版单位：机械工业出版社 2 基本结构基本结构: :集合集合介绍在本节中, 我们研究离散结构的基础, 即集合. 集合是用在一起的组的对象. 一般情况下, 是一组有相似的性质对象. 例如所有的学生; 在学校招收的学生组成一组. 在离散数学中, 同样的, 在任何学校所有的学生学习课程也可以组成一组, 形成一个集合. 语言是一种方式, 集合是在一个有组织的方式上进行研究的. 现在给一个直观的定义, 它不属于正式集合论.定义1一个无序的一组对象定义为集合A, 其中的对象称为元素或集合的成员. 用aA 表示a是集合A当中的元素.用 aA表示元素a不是集合A当中的元素. 集合一般是使用大写字母来表示. 小写字母通常用来表示集合的元素.下面有几种方法来描述集合.第一种方法列举法: 可以列出所有的集合成员, 当然前提是这些元素都是可列的. 我们用一个符号, 将所有的成员都列在大括号之间就构成集合. 例如符号{ a, b, c, d }代表四种元素的集合. 这种方式描述一组被称为列举法.例1 元音字母在英文字母可以写成集合V = { a, e, i, o, u }.例2 正整数集合O小于10的奇数集合可以表示为O = { 1, 3, 5, 7, 9 }.例3 虽然集合元素通常是一组有相似性质的对象, 但有时候也可以是一组 看似无关的元素. 例如{a, 2, 弗雷德,新泽西}是一组包含四元素a, 2, 弗雷德和新泽西.有时列举法用于描述所有没有清单的一组成员. 例如一些成员已经列出的集合, 然后省略号(……). 用在通用模式的元素是显而易见的.例4 一组小于100的正整数可以用{ 1, 2, 3,……, 99 }.另一种方法是一组使用集合构造符号的描述. 例如正整数集合O小于10的奇数集合可以表示为O = { x | x是一个小于10的奇数 }; 或O = { xZ + | x是奇数和x < 10 }. 当它是不可列出的元素集合时, 我们经常使用这种类型的符号来描述集合. 例如, 集合1Q +有理数可以写成Q+ = { x∈R | x = p / q,对于一些正整数p和q }.这些集合, 每个使用黑体字表示字母,在离散数学扮演重要的角色:N = { 0, 1, 2, 3,……},自然数集合;Z = {……,−2, - 1, 0, 1, 2,……},整数的集合;Z + = { 1, 2, 3,……},正整数集合;Q = { p / q | p, qZ ,q≠0 },有理数集合;R,实数集合;R +,正实数集合;C,复数集合.(注意, 有些人并不认为0一个自然数, 使用自然数时候要小心.)当a和b是实数并且a< b, 我们写成：[a, b]= { x |a≤x≤b }[a, b)= { x |a≤x < b }(a, b)= { x | a< x≤b }(a, b)= { x | a< x < b }注意: [a, b]称为从a到b的闭区间； (a, b)称为从a到b的开区间. 集合可以有其它集合作为其元素, 如例5所示.例5 集合{ N, Z, Q, R }是一组包含四个元素, 都是集合. 这四个元素的集合是: 自然数的集合N; 整数集合Z; 有理数集合Q和实数集合R.定义2 两个集合相等当且仅当它们具有相同的元素. 因此, 如果A和B是两个集合, 它们相等, 当且仅当x(xA↔xB),我们写A = B 如果A和B是相等的集.例6 集{ 1, 3, 5 }和{ 3, 5, 1 }都是相等的, 因为他们有相同的元素.注意, 集合与元素列出的顺序没关系. 还请注意, 如果有集合的一个元素出现超过一次, 如{ 1, 3, 3, 3, 5, 5, 5, 5 }和集合{ 1, 3, 5 }, 它们是一样的集合, 因为它们有相同的元素. 空集是一个特别的集合, 没有元素. 用Ø表示. 空集也可以用{ }(即我们用一对大括号表示空集). 一个常见的错误是混淆空集Ø和集{Ø}. 集{Ø}这是一个单例集. 单一元素的集合{Ø}是空集本身. 用一个类比来记住这个区别: 在计算机文件夹里.空集可以被认为是一个空的文件夹, 单例集可以被认为是一个文件夹里面正好有一个空的文件夹.维恩图另外，可以使用维恩图以图形方式表示集合. 在1881年, 维恩图以英国数学家John Venn命名的, 其中介绍了维恩图的使用. 在维恩图的通用集U中, 包含所有的对象, 一般用一个矩形来表示.矩形、圆形或其他几何图形也被用来代表集合. 维恩图通常用于表示集合之间的关系. 如例7展示的就是一个维恩图.2例7 画一维恩图用V表示,在英文字母中集合用元音字母.解决方案:我们绘制一个矩形来表示通用集U, 这是组26个英文字母. 在这个矩形我们画一个圆代表V. 在这个圈子, 我们指示V点元素(见图1).图1维恩图元音集合.子集定义3 一个集合A是另一个集合B的子集;当且仅当A的每个元素也是B的元素. 我们使用符号AB表示B集合的子集A. 当AB时,有对于x(xA→xB)是正确的. 若A不是B的子集, 我们只需要找到一个元素xA与xB . 这样的一个x, 举出一个反例来.我们有这样一个有用的规则可以决定是否有一个集合是另一个集合的子集.例8 集合的正整数奇数不到10是正整数小于10的集合的一个子集. 有理数集合是的实数集合的一个子集, 在你学校的所有的计算机科学专业学生集合是在你的学校所有的学生集合的一个子集.图2 维恩图显示, 集合A是集合B的子集.定理1证明每个非空集S能保证至少有两个子集, 空集和其本身, 即Ø和S.定理1 对于任意一个非空集合S, (i)ØS 和 (ii)SS. 现在有A= {Ø,{a},{ b },{ a, b } }和b = { x | x是集合{ a, b } 的子集}. 请注意, 这两个集合相等, 即A= B. 还要注意, {a}A但aA. 幂集合 一些问题当考虑一些集合元素有一些特定的性质时候, 就可以知道得到一个含有3它的子集的集合. 定义6 给定一个集合S, S的幂集是S的子集的集合S所组成的集合. 用P(S).例14 什么是集合{ 0, 1, 2 } 的幂集?解 幂集P({ 0, 1, 2 })是集{ 0, 1, 2}的子集的元素集合组成的. 因此, P({ 0, 1, 2 })= {Ø,{ 0 },{ 1 },{ 2 },{ 0,1 },{ 0,2 }、{ 1,2 },{ 0、1、2 } }.注意, 空集和集合本身是这个集合子集的成员.例15 什么是空集的幂集吗?什么是集合{Ø}幂集 ?解 空集是空集的子集,即空集的子集是其本身. 因此,P(Ø)= {Ø}. 集合{Ø}正好有两个子集, 即Ø和集合{Ø}, 也就是它本身. 因此, P({Ø})= {Ø, {Ø} }. 如果有n个元素组成的集合, 那么它的幂集有个元素. 在后续部分的文章当中,将从好几个方面展n2示这个事实.1010 图图 10.1 图和图形图和图形我们首先定义一个图.定义1 设V和E是两个有限非空集合, V中的元素叫做节点（或顶点）, E中的元素叫做边, 且E中的每一条边恰好与V中的两个节点相对应, 就称G = (V, E)是一个图. 边是连接着它的顶点的. 注意: 顶点集合V在图G上可能是无限的. 一个图有无限的顶点的或无限数量的边, 这样的图被称为无限图. 相比之下, 一个图的顶点集与有限边的集合构成的图称为有限图. 在这本书中我们一般研究有限图.定义2 有向图(V, E)由一个非空的顶点集合V和一组定向边(或弧)集合E, 每个有向边都关联一个有序对顶点. 有向边关联有序端点(u, v), 也就是说当描述一个有向图和无向图时, 一般使用一个箭头从u →v指示方向表示有向图, 从u开始到v的结束. 一个有向图可能包含多重边, 也它可能包含多个定向边. 也就是说, 当一个有向图包含一个边, 它还可能包含一个或多个边. 这里可以获得一个有向图. 一般只要给一个无向图指定一个方向就可以成为一个有向图. 如果一个图没有自环, 并且每两个顶点之间最多只有一条边, 这样的图称为简单图.,我们称(u, v)为边.10.210.2 图的术语和特殊类型的图图的术语和特殊类型的图介绍基本术语首先, 我们给一些术语, 描述顶点和边的无向图.定义1 在无向图中, 若边e与节点(a, b)对应, 则称e与节点a关联, 同样, e与b关联. 4若节点a和b之间有边连接, 则称节点a与b相邻, 否则不相邻. 若两条边关联一个共同的节点, 则称这两个边相邻, 否则, 若两条边不同时与任何一个节点关联, 则称这两个边不相邻. 定义3 一个无向图的一个顶点的度,一般一个重边在一个顶点的度的贡献两次, 这里v顶点的度用deg(v)表示.例1 在G和H图中各个顶点的度是多少？ 解 在G图中, deg(a)= 2, deg(b)=deg(c)=deg(f)= 4, deg(d)= 1, deg(e)= 3, deg(g)= 0. 在H图中, deg(a)= 4, deg(b)=deg(e)= 6, deg(c)= 1, deg(d)= 5. 图1 一个顶点的度为零称为孤立点. 由此可见, 一个孤立的顶点是不相邻于任何顶点. 图G中的顶点g在图1中就是孤立的. 若顶点是悬挂点, 当且仅当它有一个度. 因此,一个悬挂点只有一条边与它关联. 图H的顶点c在图1中就是悬挂点. 在检查顶点的度的时候, 一个模型图可以很直观地提供有用的信息.定理1 现有G =(V,E)是一个无向图与m条边. 然后可以得到 Vvvmdeg2.(注意,即使多个重边这里也存在这样的关系. ) 例3 在一个有十个顶点, 每个顶点的度为6的图中有多少边呢? 解 因为6个顶点的度之和是6 * 10 = 60, 而2 m = 60, m是边数. 因此, m = 30. 有这个例题和定理1, 可以给出定理2。

定理2 一个无向图有偶数个奇节点.定义4 在图G上的(u, v)是边连接的两个顶点, 就说u与v相邻, v和u是相邻的两个顶点. u被称为初始顶点, v称为终端或结束顶点.定义5 在图G中, 定向边的一个v顶点的入度, 用deg-(v)表示, v作为他们的终端顶点. 这个顶点的出度, 用deg+(v)表示, v作为他们的初始顶点. (请注意, 一个重边在顶点处贡献1到2个入度或出度).5例4 在图G中找定向边到每个顶点的入度和出度. 如图2所示: 图2 解 在有向图G上, deg-(a)= 2, deg-(b)= 2, deg-(c)=3, deg-(d)= 2, deg-(e)= 3, deg-(f)= 0. deg+(a)= 4, deg+(b)= 1, deg+(c)= 2, deg+(d)= 2, deg+(e)= 3, deg+(f)= 0.因为在图上每个边有一个始点和一个终点. 度的总和所有顶点的出度与入度都是相同的.由此定理3得到.定理3: 图G =(V,E)；然后 EvvVvVv。