《论文答辩幻灯片模板》由会员分享，可在线阅读，更多相关《论文答辩幻灯片模板（37页珍藏版）》请在金锄头文库上搜索。
1、图与矩阵Graph and matrix答辩人： 汪应根指导教师：王龙芹,2011届毕业论文(设计)答辩,内容提要,一、背景和基本概念 二、邻接矩阵与其应用 三、关联矩阵与其应用 四、图论中的其一些常见矩阵,一、背景和基本概念,图论的产生和发展经历了二百年的历史，大体上可以划分为三个阶段。第一个阶段是从1736年到19世纪中叶。这时的图论处于萌芽阶段，多数问题是围绕着游戏产生的，最有代表性的工作是著名的瑞士数学家L.Euler于1736年的Konigsberg七桥1,2问题。他的那篇论文被公认为图论史上第一篇论文。第二阶段从19世纪中叶到1936年。这个时期中图论问题大量出现，如四色问题（18
2、52年）和Hamilton问题2,3,4（1856年）。同时出现了以图为工具去解决其他领域中一些问题的成果。最有代表性的工作是Kirchhoff和Cayley5,6,11分别用树的概念去研究电网络工程组问题和有机化合物的分子结构问题。“图（Graph）”这个词第一次出现在1878年的英国自然杂志中。进入本世纪30年代，出现了一大批精彩的新理论和结果，如Menger定理6,7，Kutatowski定理7,8和Ramsey定理8等等。这些理论和结果为图论的发展奠定了基础。1936年，匈牙利数学家D.Konig写出了第一本图论专著有限图与无限图的理论。,图论作为数学的一个新的分支已基本形成。1936
3、年以后是第三阶段。由于生产管理、军事、交通运输、计算机和通讯网络等方面许多离散性问题的出现，大大促进了图论的发展。进入70年代以后，特别是大型电子计算机的出现，使大规模问题的求解成为可能。图的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中方面应用的研究都得到“爆炸性发展”。总之图论内容之丰富和应用之广泛，是很难尽述的。本文重点研究图的关联矩阵和邻接矩阵以及在生活中的简单应用。,定义1.1 一个无向图 定义为一个偶对 , 记作,其中（1） 是一个集合，其中的元素称为顶点；（2） 是无序组集合 中的一个子集合，其元素称为边；集合
4、中的元素可在 中出现不止一次。我们分别 用表示图G的顶点集合与边的合边集合。如果 它们都是有限的集合，则称G为有限图；否则称为无限图。 一个有个p顶点和q条边的图称为图 ，一个 图，若它的p个顶点以不同的名称，则称为标定的，否则称为非标定。没有任何边的图称空图。只有一个顶点的图叫做平凡图。图中的顶点的个数叫做图的阶，如果连接同一对顶点的边数大于1，则称这样的边为多重边，其边数称边的重数。图论中大多数定义和概念是根据图的表示形式提出的。一条边的端点称为与这条边关联，反之，一条边称为与它的端点关联。与同一条边关联的两个端点称为邻接。如果两条边有一个公共的顶点，则称这两条边邻接。,定义1.2设 ,G
5、中与顶点 关联的边的数目，称 为（在G中）的度（degree），记作 或者简记为 。 定理1.1设G是一个 图，那么G的各个顶点度的和是边的两倍。证明 因为每一条边与二个顶点关联，所以加上一条边就使得各点度的和增加2。,推论1.1(7)在任何一个图G中，度为奇数的顶点的数目是偶数. 证明:设和分别是中度数为奇数和偶数的顶点集。由定理1.1有由于 和 均为偶数，故得证。,例 如下面所示图的边为 边为,它们的度分别为,4,4,2,1,3。,奇数顶点为2个。,v1,v2,v3,v4,v5,e1,e2,e3,e4,e5,e6,e7,定义1.3 一个有向图定义为一个偶对，其中 1.V是个非空集合，其元素
6、称为顶点； 2.U是有序积 的一个子集，其元素称为弧。 根据有向图的定义，与一条弧关联的两个端点具有一定的次序关系 即弧 是顶点u和v的有序对。我们称u是为弧a的起点，v为终点。 定义1.3 有向图D中，以顶点v为起点的弧的数目，叫做v的出度，记作 ，以顶点v为终点的弧的数目，叫做v的入度，记作 显然，对有向图D中的任一顶点v，有,如下面的有向图，顶点1的出度为1，入度为1,顶点1的度=2,1,2,3,5,4,二、邻接矩阵与其应用,定义2.1设无向图G的顶点集 ,令 则称由元素 构成的p阶矩阵为图G的邻接矩阵，记作A(G)，无向图的邻接矩阵都是对称的。,例如：如下图的邻接矩阵为,定义2.2设有
7、向图D的顶点集 的邻接矩阵，这里 表示有向图D中以 为起点 为终点的有向边的数目。 例如：如下面有向图的邻接矩阵为,V1,V2,V3,V4,7,1,5,7,5,3,5,1,2,5,3,2,邻接矩阵的应用应用例子1（最优化、最短路问题）从油田铺设管道，把原油由油田送到石油炼油厂。要求管道必须沿图所给定的路线铺设。设图中的 点为油田所在地， 点为石油炼油厂 ，每个弧旁的数字表示这条道路的长度，求使管道总长度最短的铺设方案。,v1,v2,v3,v4,v5,v6,v7,用图的术语这个问题，就是在给定的有向图中，寻求一条从v1点v7点到的路，并使其是该两点之间距离最短的路。这种在一个有向图（或无向图）中
8、规定了一个发点（始点）和一个收点（终点）的赋权图称之为网络。一般而言，最短路问题，就是要求始点到终点的一条路，使其在所有从到的路中，它是总权数最小的一条路。所谓邻接矩阵求最短路，就是描述一个网络图中点与点之间邻接状态的矩阵，通过这一矩阵的运算得到网络图中任意两点之间的最短路。邻接矩阵的求法的步骤： (1)令， 表示一步步长为各项点之间的路长，其中为邻接矩阵。 (2) 表示k步步长内各项顶点之间的路长。注意到这里的矩阵乘法是借用来的，它是指第一个矩阵的行与第二个矩阵的列对应数值相加后取其最小值，即： （3） 当时，就是任意两顶点之间的最短距离。,求解上面的例题 所以， 就是例子中任意两点间的距离
9、。,应用例子2（配对问题）某厂生产一种弹子锁具,每个锁具的钥匙有 5个槽,每个槽的高度从 1, 2, 3, 4, 5, 66个数 (单位略 )中任取一数由于工艺及其他原因,制造锁具时对 5个槽的高度还有两个限制:至少有 3个不同的数,相邻两槽的高度之差不能为 5,满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每 60个装一箱出售。问每一批具有多少个,装多少箱。分析：锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。每把锁都有 5个槽,每个槽有 6个高度,至少有三个不同高度的槽。且相邻槽高差不为 。我们先求出无相邻高差为
10、5的锁具数量,再减去仅有一个、两个槽高的锁具数目。,先计算由 1, 2, 3, 4, 5, 6构成无 1, 6相邻的情况的数目。为此,构造一个 6节点的图:将 1, 2, 3, 4, 5, 6这 6个数作为 6个节点,当两个数字可以相邻时,这两个节点之间加一条边,每个节点有自己到自己的一条边。我们得到了锁具各槽之间的关系示意图 (见图 1)。,由图我们可以试着画出这个图的邻接矩阵来：邻接矩阵 A的所有元素之和表示两个槽高无 1, 6相邻的锁具的个数,每个无 1, 6相邻的 5位数与图 1中长度为 4的一条链 1 - 1对应,如 12345, 11111, 22335等。,A的 k次方中各元素之
11、和就是长度为 k的链的个数。事实上,从这2个具体问题可以看出, A 中第 i行第 j列的元素指从 i开始经过两条边到达 j的链数,即从 i开始经过一条边到 k,再从k经过一条边达到 j, i和 j就决定了中间顶点 k的数目。于是,利用 Matlab就很容易得到。,将该矩阵中的元素求和可得相邻高差不为 5的锁具数为 6306把。把。但这 6306把锁具中包含了仅有一个、两个槽高的锁具,需要从其中减去。需减去的锁具的个数为6+( -1)( -2)=426 其中,第一个 6仅有 1个槽高的锁具; 为 1, 2, 3, 4, 5, 6这 6个数中取两个的取法,但扣除 1, 6这一种取法。最后得到一批锁
12、具的个数为 6306 - 426 =5880,总共装98箱。这样,就用图论的知识成功地解决了一批锁具的数量问题,这个方法比用别的方法简单,且容易推广。,三、关联矩阵与其应用,定义3.1 设无向图G为 图。令 为顶点 与边 的关联次数，则称 为的关联矩阵，记作 。 定义3.2 设有向图 无环， ， 则称 为有向图D的关联矩阵，记作 M(D),关联矩阵的应用 例1（分配问题的简便记法）某单位有6位工人，用X1,X2,X6表示，现有6项工作需要做，用y1,y2,y6表示这6项工作，假设在同一时间内只能安排工作一件工作，每件工作也只需要一个人做，由于受的训练不同，每个工人只能做这6项工作中的几项，其中
13、工人X1只能做y1,y4,y5这三项工作，工人X2只能做y4,y6两项工作，X3只能只能做y2,y3两项工作，X4只能做y2这项工作，X5只能做y3这一项工作，X6只能做y1,y3这两项工作。问怎么分配,解：利用关联矩阵建立数学模型，令 于是有下面的关联矩阵 矩阵第i行中有几个1表示工人，能做几项工作，第列中有几个1表示这项工作有几个人做。从上面关联矩阵中很清楚的看到这三项工作只有两工人能做，因此如果每件工作只需要一个人做，那么不管怎么安排都不能使得每项工作都有人做。,例2 校友会有7人参加，已知他们每个人至少认识其中一个人，试证明必有一个人至少认识其中两个人。 解：用用 表示这7 个人 ,
14、表示与认识的人，显然 由于他们中每个人至少认 识其中的一个人，不防设a1与a2，a3与a4，a5与a6于是可得下面的关联矩阵,未写的元素为0（或其他假设下的1），面考虑a7，由于至少与其余人中的某一个人认识，不论a7与谁认识，除第7行与第7列外其余列（或行）中至少有一列（或行）含有三个1，即这行对应的人，除他本人外至少还有认识另外两个人，不妨设a7与a2认识，则上面矩阵第二列为 ，即a2除认识他本人以外，还认识 。,四、图论中的其他一些常见矩阵,圈矩阵 预备知识：环路是圈与圈的边不重并。显然圈是环路。圈是连通的，环路不一定连通。如下图，边集 构成一个环路，它是圈abc和圈fgh的边不重并。环路 是连通的，而环路不连通。,h,定理4.1连通图 图G的所有环路和空间的集合构成一个 维空间 定理4.2连通图 的圈空间中元素的个数为 定义4.3 设连通图 图G，这称由元素 构成 矩阵为图G的完全圈矩阵记作,定义4.4 图G的完全圈矩阵 中秩 为的 矩阵，叫做图G圈矩阵，记作B。 定义4.5 设 是连通图G关于生产树的基本圈组，令则称由元素 组成的 的矩阵为图G的基本圈图矩阵。记作,
