英语原文共 42 页，剩余内容已隐藏，支付完成后下载完整资料
附录X 译文
图
本书的重点在于解决离散数学的问题。跟连续数学一样涉及某些基本结构组成如实数、向量和矩阵，离散数学研究的重心在于发展这些基本组合结构，其中最根本且最富有表现力的是图。
我们研究图越多发现用得也越来越多。因此我们首先从引入跟图有关的一些基本定义开始，并列出频谱不同的算法设置图表出现得自然的地方。然后我们讨论一些基本算法的原始图表用于解决一些基本图搜索技术在连通上的问题。
3.1基本定义及应用
回顾第一章讲到G图 是一种将一组对象的关系成对编码的简单方法，一组对象由一个结点集合V和一个边集合E组成，每个连接都有两个结点。由此我们用表示V的双元素的子集,我们称u和v是e的两个端点。
图的边表示两个端点之间的对称关系。我们经常需要表达不对称的关系，因此我们使用一个与有向图密切相关的概念。有向图G'由一个结点集合V和一个有向边集合E'组成。每个集合都是一个有序数对(u, v)；也就是说，u和v的作用是不可交替的，我们称u为边的结尾v为开头。我们将u称为e'的离开结点v称为进入结点。
我们将没有方向的图表称为无向图，一般我们将“图”默认为无向图。值得一提的是我们在使用图表术语时的两个注意点。第一点，尽管在无向图中的边e通常表示为一个结点集，另一种常见的是将它写成（本书也是）有序对的符号。第二点，图中的一个结点也经常作为顶点；在这种情况下，这两个词汇我们认为是完全相同的意思。
图的例子
图很容易定义：将一些数据的集合加上边缘。但是在这一层面上很抽象，我们很难观察到它们出现的典型情况。因此，我们将下列特定情况下的图表作为重要参考模型。下列举例涵盖的内容较多，我们并不需要完全记住上面的每样东西；相反，它将为我们提供很多有用的例子，用来对照基本定义和解决我们将在后面的章节遇到的算法问题。而且，在下列图表的学习过程中，有助于我们了解在相应的应用情况中结点的意义以及边的意义。在某些情况下结点和边相当于现实中的物理对象，在有些情况下结点是真实对象而边是虚拟对象，还有一些情况下结点和边都是抽象概念。
1.交通网络
航空运输的路线地图自然形成一个图表：结点就是机场，而从u到v的边是直达航班从点u飞到点v。在这种情况下图是有向的，但是在现实情况中，当有一个边也总有一个边，所以我们不会将航空路线图当作一个双机场每边都有直达航班的有界无向图。看着这样一个图表（通常你可以在机上的航空杂志上找到它的绘图)，我们需要注意一些东西：经常有少量的枢纽会附带大量的边，很可能会导致图表中任意两个节点之间很小部分的停止。
2.通信网络
可以用几种不同的方法把由通信网络连接而成的计算机看成一个图的模型。第一种方法，我们可以把每个电脑看成结点，如果存在一个直接的物理链路把u和v连接起来，就会有边与它们相交。另外一种方法，为了研究网络的大规模结构，人们常常定义一个结点因特网服务供应商控制的所有机器的集合，如果在u和v之间存在一个直接的对等关系---粗略的说，就是因特网路由的标准BGP协议下交换数据的协议，需要说明的是后一个网络比前一个网络更虚拟，因为这个链接表示了在一个物理连接上的前协议。
在无线网的研究中，我们一般定义的图，其中的结点是位于物理空间的计算机设备，如果v到u近到可以接收到信号，那么就从v到u存在一个边。需要注意的是，把这个图看成有向图常常是有用的，因为可能存在这种情况，v可以收到u的信号但是u不可能收到v的信号（例如，如果u有一个更强的发射机），从一个几何学的观点上看这个图是有趣的，因为它们大致对应于落在相应的平面上的点，相交的点很靠近。
3.信息网络
万维网可以自然地看成一个有向图，其中结点对应于网页，如果u到v有一个超链接，那么从u到v有一条边。这个图的有向性是严格的，例如，许多网页连接到流行网站，但是显然这些网站不会回应这些链接。所有的连接组成一个结构，某些利用这个结构尝试推算出Web上最重要的网页的算法，就是当前大多数搜索引擎使用的一种技术。
在因特网出现的数十年以前，已经有某些信息网络用到了Web的这种结构，其中包括百科全书或其他参考书中文章的交叉引用网络，还有科学论文中的目录引用网络。
路径与连通性
图的基本操作之一是沿着用一系列用边连接的结点旅行。在上面列出的例子中，这样一个旅行相当于一个用户浏览Web网页；一个谣言从你的口中传到世界某人的口中；或者一个飞机旅客由一系列航班从旧金山飞到罗马。
在心里有了这些概念，我们把无向图中的一条路径定义为具有以下性质的结点的序列P，其中每对连续的结点, 与G中的一条边相交。P常常被叫做从到的路径或者路径。例如，在图3.1中结点4,2,1,7,8构成一个路径。如果一条路径所有的结点都是互相不同的，就称为简单的。一个圈是路径，其中kgt;2,前K-1个结点都是不一样的，且---换句话说，结果就是结点的序列绕到它开始的地方。所有这些定义只有以下改变，就可以自然地成为有向图：在一条路径或圈中，每一对连续的结点都有一个边。换句话就是说，在路径或圈中的结点必须与边有关。
如果每对结点u和v都有一条路径从u到v我们就称无向图是连通的。如何定义一个有向图是否连通有一点复杂，因为很有可能对u有一条到v的路径而对v没有一条到u的路径。如果对每对结点u和v都有一条从u到v的路径和一条从v到u的路径我们则说一个有向图是强连通的。
图3.1 同一棵树的两种画法，右边这棵树的根在结点1
在简单的了解了一些结点对u和v之间存在路径的问题，我们也会想是否有一条短的路径。因此，我们把两个结点u和v之间的距离定义为最少边数。（我们可以指派某个符号，例如用表示没有被一条路径连接两个结点之间的距离）。这里的术语距离源自于把G想象成一个通信网络或者一个交通网络；如果想从u到v，我们很可能想要一条具有尽可能少有“跳”的路径。
树 一个无向图如果是连通的，且不包含一个圈，我们就说它是一棵树。例如，图3.1给出的两个图都是树。在某种更强的意义上，树是一种最简单的连通图：在树上删除任何一条边它都会不连通。
为了考虑树T的结构，把根放在一个特定的结点上使有用的。在物理上说，这就是在结点r抓住T并且让其余部分在重力作用下向下挂的一个操作，就像一个可变形的东西。更准确的说，我们从r向外“定向”T的每条边；对于其他结点，我们声明v的父母是在从r到它的路径上领先于结点u，我们声明如果v是w的父母那么w是v的孩子。更一般的说就是如果v在从根到w的路径上，那么w是v的一个后代（或者v是w的一个祖先）；如果一个结点x没有后代，我们就说它是一片树叶。例如，在图3.1中的两个图对应了同一棵树T---边与同样的结点对相交---但是在右边的图表示将T的根放在结点1的结果。
根树是计算机科学中的基本对象，因为它们把一种层次的概念形式化了。例如，我们可以把图3.1的根树想象一个有9个人的公司，雇员3和雇员4 向雇员2报告；雇员2，5和7想雇员1报告；等等。为了促进航行，许多Web网站按照一个树形结构进行组织。一个典型的计算机科学系的Web网站有一个登陆页面（例如课程页面）；标为教员和学生的页面都是人员页面的孩子；每个教授主页面都是教员页面的孩子等等。
我们这里的目的是，树T的根会使关于T的问题更容易被解决。例如，给定一个有n个结点的树T，它有多少边？除了根之外的每个结点有唯一的一条边“向上”通往它的父母，反过来，每条边正好从一个非根的结点向上。于是我们很容易证明了以下事实。
命题3.1 每棵有n个结点的树都有n-1条边。
事实上，下面更强的叙述是真的，尽管我们这里没有证明。
定理3.2 设G是一个有n个结点的无向图，下面任意两个语句都能得出第三条语句。
（i）G是连通的。
（ii）G不包含一个圈。
（iii）G有n-1条边。
现在我们回顾树在图遍历的基本算法中的作用。
3.2 图的连通性与图的遍历
在建立了与图相关的某些基本概念以后，我们转向一个非常基础的算法问题：结点到结点的连通性。假设给定一个图和两个特定的结点s和t。我们想要找到一种有效的方法来回答这个问题：在G中是否存在一条从s到t的路径？我们把它称为s-t连通性的确定问题。
对于很小的图来说，这个问题可以很简单地通过直观检查解决。但是对于很大的图来说，就需要通过一些工作来寻找一条路径。实际上，s-t的连通性问题也被称为迷宫求解问题。如果我们把G想象成一个迷宫，每个房间对应一个结点，一条通道对应两个结点相交在一起的边。那么这个问题就是找一条从房间s到房间t的路。
图3.2 在这个图里，结点1有路径通向结点2到
结点8，但是没有从结点9到结点13
在这一节，我们在高层次上描述两个自然算法：宽度优先搜索（BFS）和深度优先搜索(DFS)。在下一节，我们讨论怎样有效实现每个算法，建立一个数据结构代表一个图作为算法的输入。
宽度优先搜索
也许为了确定s-t连通性的最简单的方法就是宽度优先搜索（BFS），在这个算法中我们从s向外在所有可能的方向上探查，一次增加一“层”结点。于是，我们从s开始，包含所有通过一条边与s相交的结点---这是第一层搜索。然后我们通过一条边与第一层中任一结点相交的所有新增加的结点---这是第二层搜索。我们继续按照这种方法直到不会遇到新的结点为止。
在图3.2的例子中，开始以结点1作为s，搜索的第一层由结点2和3组成，第二层由结点4，5，7和8组成，并且第三层将仅由结点6组成。在这一点搜索将停止，因为再没有结点可以加进来（特别地，注意到这个搜索永远不能从结点9到结点13）。
作为对这个例子的补充，对于这个算法有一个自然的物理解释。本质上看，我们从s开始并且用一个扩张的波来“淹没”这个图，这个波向前访问它能到达的所有结点，这一层在某一刻包含某个结点表示某一刻包含某个结点表示此刻它到达这个结点。
我们可以更精确地将BFS算法构造的层定义如下。
层由s的所有邻居组成（为了符号上的缘故，有时候使用层表示仅由s组成的集合）。
假定我们已经定义了层,那么层由不属于前面得层并且有一条边通向层的某个结点的所有结点组成。
回顾我们关于两个结点的距离的定义，它是在与它们相交的一条路径上最少的边数。我们看到层是所有到s距离为1的结点的集合。更一般地，层恰好是所有到s距离为j的结点的集合。一个结点没有出现在任何一层当且仅当没有路径从s通到它。于是，BFS不仅确定了s可以达到的结点，它也计算了到它们的最短路径。我们把这些总结成下面的事实。
定理3.3 对每个j1,由BFS产生的层Lj恰好由所有到s距离j的结点组成，存在一条从s到t的路径当且仅当t出现在某个层中。
宽度优先搜索的另一种性质就是，它在从s可达的结点集合上以一种非常自然的方式产生一棵根在s的数T。明确地说，对每个这样的结点v（除s之外），考虑v被BFS算法第一次“发现”的时刻，这恰好发生在层的某个结点u正在被检查的时候，我们发现它有一条边通向以前没见过的结点v。就在此刻，我们把一条边加到这棵树T上---u变成了v的父母，这表示了下面的事实：u对于完通向v的路径“负责”。我们把以这种方式产生的树T叫做宽度优先搜索树。
对于图3.2中的图，图3.3描述了一棵根在结点1的BFS树的结构。实线边是T的边;虚线边是G中不属于T的边。产生这棵树的BFS算法的执行过程可以描述如下：
图3.3 对于图3.2中的图。一棵宽度优先搜索树的结构。
其中（a），（b）和（c）画出了不断加的层。实线
边是T的边；虚线边在G含结点1的连通分支中，
但是不属于T。
（a）从结点1开始，层由结点2，3组成。
（b）然后通过按顺序（比如说先是2，然后是3）考虑在层中的结点而产生层，于是，只要我们看到2，就发现结点4和5，2称为它们的父母。当考虑结点2的时候，我们也发现一条通向3的边，但是这条边并不加到BFS树中，因为我们已经知道了结点3。
当我们看结点3的时候首先发现结点7和8另一方面，从3到5的边是G中另一条不出现在BFS树中的边，因为在见到来自结点3的这条边的时刻，我们已经知道了结点5。
（c）然后我们按次序考虑在层的结点，但是当我们检查的时候，只有一个新的结点被发现，就是结点6，把它加到层注意边（4,5）与（7,8）不加到这棵BFS树中，因为它们没有导致对新的结点的发现。
（d）当检查结点6时没有发现新的结点，因此没有结点放在层，算法结束。整个的BFS树被画在图3.3（c）。
我们注意到当这个图运行BFS的时候，非树边或者连接了在同一层的结点，或者连接了在相邻层上的结点。我们现在证明这是一棵BFS树的一般性质。
定理3.4 设T是一棵宽度优先搜素树，设x和y是T中分别属于层和的结点，并且设
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[484294]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
