图论在计算机科学中应用.ppt

图论是一门古老的数学分支，它起源于游戏难题的研究，如1736年欧拉所解决的哥尼斯堡七桥问题，以及迷宫问题、博弈问题、棋盘上马的行走路线问题等。同时，图论又是近年来发展迅速且应用广泛的一门新兴学科，已渗透到诸如语言学、物理学、化学、电讯工程、计算机科学以及数学的其它分支中，特别在计算机科学中，如形式语言、数据结构、分布式系统、操作系统等方面均扮演重要的角色。,欧 拉 图,欧拉图的概念是瑞士数学家欧拉（LeonhardEuler）在研究哥尼斯堡（K nigsberg）七桥问题时形成的。在当时的哥尼斯堡城，有七座桥将普莱格尔（Pregel）河中的两个小岛与河岸连接起来（见图3.1（a），当时那里的居民热衷于一个难题：一个散步者从任何一处陆地出发，怎样才能走遍每座桥一次且仅一次，最后回到出发点？,这个问题似乎不难，谁都想试着解决，但没有人成功。人们的失败使欧拉猜想：也许这样的解是不存在的，1936年他证明了自己的猜想。为了证明这个问题无解，欧拉用A，B，C，D四个顶点代表陆地，用连接两个顶点的一条弧线代表相应的桥，从而得到一个由四个顶点、七条边组成的图（见图3.1（b），七桥问题便归结成：在图3.1（b）所示的图中，从任何一点出发每条边走一次且仅走一次的通路是否存在。,欧拉指出，从某点出发再回到该点，那么中间经过的顶点总有进入该点的一条边和走出该点的一条边，而且路的起点与终点重合，因此，如果满足条件的路存在，则图中每个顶点关联的边必为偶数。图3.1（b）中每个顶点关联的边均是奇数，故七桥问题无解。欧拉阐述七桥问题无解的论文通常被认为是图论这门数学学科的起源。,图 3.1,计算机鼓轮设计问题,图 3.4,计算机鼓轮设计问题 设计旋转鼓轮，要将鼓轮表面分成16个扇区，如图3.4（a）所示，每块扇区用导体（阴影区）或绝缘体（空白区）制成，如图3.4（b）所示，四个触点a、b、c和d与扇区接触时，接触导体输出1，接触绝缘体输出0。鼓轮顺时针旋转，触点每转过一个扇区就输出一个二进制信号。问鼓轮上的16个扇区应如何安排导体或绝缘体，使得鼓轮旋转一周，触点输出一组不同的二进制信号？,显然，图3.4（b）所示，旋转时得到的信号依次为0010，1001，0100，0010，在这里，0010出现了两次，所以这个鼓轮是不符合设计要求的。按照题目要求，鼓轮的16个位置与触点输出的16个四位二进制信号应该一一对应，亦即16个二进制数排成一个循环序列，使每四位接连数字所组成的16个四位二进制子序列均不相同。这个循环序列通常称为笛波滤恩（DeBruijn）序列。如图3.4（c）所示，16个扇区所对应的二进制循环序列正是笛波滤恩序列。,图 3.4,我们构造一个有8个顶点的有向图，顶点为8个三位二进制数000,001,010,011,100,101,110,111，可分别记为v0,v1,v2,v3,v4,v5,v6,v7，下标正好是顶点的十进制表示。如果某个顶点vi的二进制表示的后两个数字与另一个顶点vj的二进制表示的前两个数字相同，则由向引一条有向边ek，k是十进制数，对应i和j二进制表示将重合的数字只算一次的四位二进制数。例如，e1=0001，e7=0111,。这样构造出一个连通有向图G，如图3.5所示。,图 3.5,图3.5每个顶点的出席均与入度相同，故为有向欧拉图，含有一条有向欧拉回路，回路中每条边均标记着一个不同的四位二进制数，可见，对应于图的欧拉回路，存在一个16个二进制数组成的循环序列，其中每4个接连的二进制子序列均不相同。,e6=0110,图 3.5,例如，对应于欧拉有向回路:e0e1e3e7e15e14e12e9e2e5e11e6e13e10e4e8e0,e6=0110,对应于上述的欧拉有向回路的16个二进制数组成的循环序列是：把这个序列排成一个圆圈，与所求的鼓轮相对应，就得到鼓轮设计。,用类似的方法，我们可以证明：存在一个2n个二进制数组成的循环序列，其中2n 个由n个接连的二进制数组成的子序列均不相同。这个序列对应的欧位有向图称为笛波滤恩图，记作G2,n.图3.5中的图记为G2,4。,