邻接矩阵的应用1

目录 前言    1 1. 邻接矩阵发展简史    3 2．基本概念及记号    4 3. 无向图的邻接矩阵    6 3.1 无向图的邻接矩阵定义及 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示    6 3.2  无向图的邻接矩阵的性质    8 4. 有向图的邻接矩阵    9 4.1 有向图的邻接矩阵的定义及表示    9 4.2 有向图的邻接矩阵的性质    10 5. 邻接矩阵的重要定理及应用    11 6. 邻接矩阵的应用    13 6.1 邻接矩阵生成图的遍历序列    13 6.2用邻接矩阵生成图的广度优先遍历序列    15 6.3 矩阵构造最小生成树    16 6.4 用邻接矩阵寻找关键路径    19 参考文献    21 致  谢    22 前言 图论最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题．这些古老的难题，当时吸引了很多学者的注意．在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿（环游世界）数学难题． 1847年，图论应用于 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，发挥出越来越大的作用．在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一，因此越来越受到数学家和实际工作者的喜爱．我们所学的这一章只是介绍一些基本概念、原理以及一些典型的应用实例，目的是在今后对工程技术有关学科的学习研究时，可以把图论的基本知识、方法作为工具 ． “图论”是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系. 图论是一门极有兴趣的学问，其广阔的应用领域涵盖了人类学、计算机科学、化学、环境保护、电信领域等等.严格地讲，图论是组合数学的一个分支，例如，它交叉运用了拓扑学、群论和数论.图论就是研究一些事物及它们之间关系的学科，现实世界中的许多事物能用图来表示其拓扑结构，把实际问题的研究转化为图的研究，利用图论的相关结论 对这些问题作分析或判断 . 图论是近二十年来发展十分迅速、应用比较广泛的一个新兴的数学分支，在许多领域，诸如物理学、化学、运筹学、信息论、控制论、计算机等方面甚至在生产生活中都有广泛的应用.因此受到全世界越来越广泛的重视。图论的内容十分丰富，涉及面也比较广. 研究节点和边组成的图形的数学理论和方法，为运筹学的一个分支。图 论的基本元素是节点和边（也称线、弧、枝），用节点表示所研究的对象，用 边表示研究对象之间的某种特定关系.因此，图论可用节点和边组成的图形及其有关的理论和方法来描述、分析和解决各种实际问题，诸如物理学、化学、生物学、管理科学、计算方法和工程技术等领域的有关问题。图论与组合数学、线性规划、群论、矩阵论、概率论、数值分析等数学分支有密切的关系.本文章所涉及的只是图论中的一些基本概念和理论，在方法上应用矩阵来研究的一些性质.用矩阵表示一个图的各种关系，不仅是给出图的一种表示方法，而且可以充分利用矩阵代数中的各种运算，来研究图的结构特征即性质，且便于计算机处理.用矩阵表示图，必须首先将图的顶点、边等分别按照某种顺序排列，然后并按照这种顺序依次给定唯一的标号，使其称为标号图，最后给出其矩阵表示 . 本文通过运用邻接矩阵和关联矩阵的特征，把图的运算转化称矩阵运算，运用图的一些性质，转化为矩阵，进而判断图是否具有其他性质，这就包括用邻接矩阵判断图的回路. 邻接矩阵能够简便和直观地表示一些实际意义的相应信息，在数学建模中有着非常广泛的应用. 在数学建模的过程中，经常会遇到一些可以借助图和图的邻接矩阵来处理的数学模型.用邻接矩阵来表示图具有简单、直观的特点，而且邻接矩阵能够表示图的一些实际意义的相应信息. 邻接矩阵是图的一种常用的存储结构, 具有描述简单、直观的特点, 在图的运算中, 有许多算法通常是采用邻接矩阵作为存储结构来处理的.对邻接矩阵的探讨，无疑会给图论和现实生活中许多问题的研究带来方便. 本文主要介绍了邻接矩阵的求法及其应用.首先，给出了邻接矩阵的基础定义及相关定理，并对其中定义给出解释，定理做出解释；接着，有前面的基础，探讨出邻接矩阵的求法，最后， 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 邻接矩阵的应用，系统地给出它的应用的多个方面，列出实例来充分 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 ，这是本文的主要特色. 1. 邻接矩阵发展简史 1736年瑞士数学家L.欧拉发表图论的第一篇论文,解决了著名的哥尼斯堡七桥问题,因此通常认为欧拉是图论的创始人.流经东普鲁士的柯尼斯堡的普莱格尔河上有七座桥，将河中的岛和河岸连接起来（图1）.长期以来人们在议论能否从A、B、C、D这四块陆地中的任何一块开始,经过所有的桥一次且仅一次，最后回到原来出发的这块陆地.当时，欧拉将每块陆地用一个点来代替，将每座桥用连接相应的两个点的一条边来代替,从而得到了一个“图” 图（1） 欧拉对于一般的图提出了一个普遍的判别法则：要从图中一点出发，经过所有的边一次且仅一次，能回到原来的出发点，则这个图必须是连通的，且每个点都必须与偶数条边相关联.显然,图(1)中的各点都是连通的，但每个点都不是与偶数条边相连接，因此七桥问题不可能有解.1845年，德国物理学家G.R.基尔霍夫为了解决一类线性联立方程组而创建“树”理论.他把电网络和其中的电阻、电容和电感等抽象化，用一个只有点和边组成的组合结构来代替电网络，而不指明每条边所代表的电器元件种类,这样就可以方便地对方程组进行求解 .1852年F.格思里在对地图着色时发现,无论多么复杂的地图,只要用四种颜色就能将相邻区域区分开来。这就是所谓“四色猜想” 经过百余年的努力，直到1976年才由K.阿佩尔和W.赫肯借助电子计算机证明了四色定理.1856年，W.R.哈密顿在给 R.L.格雷夫斯的信中提出一个游戏：用正十二面体上20个顶点表示20个城市，要求游戏者沿着各边行走，走遍每个城市一次且仅一次，最后回到原出发城市。这个游戏促使人们研究如何判断一个图有无这一性质，如果有，则又如何确定这样的路径。这是一个至今尚未完全解决的问题. 2．基本概念及记号 图　图论中所研究的图就是节点和边的集合，记作 ,其中 表示非空的节点集合， 表示边的集合 . 在图论的研究中常用到的概念有 : 节点数和边数  集合V的元素个数称为图 的节点数;集合 的元素的个数称为图 的边数. 端点和关联边  若 ,则称点 和 是e的端点，而称e是点 和 的关联边. 相邻点和相邻边  若 和 与同一条边相关联,则 与 是相邻点；若 与 有一个共同端点,则若 与 为相邻边. 环和多重边  若边的两个端点同属一个节点,则称该边为环；若两个端点之间多于一条边，则称多重边. 多重图和简单图  含有多重边的图称为多重图；无环无多重边的图称为简单图. 次 以点 为端点的边数称为这个点的次，记作 . 零图 一条边也没有的图. 子图  在研究和描述图的性质和图的局部结构中，子图的概念占有重要地位。 对于图 ， ，若 ，则称为 为 的子图. 连通图　如果图 的任意两点至少有一条通路连接起来，则图 称为连通图，否则称为不连通图. 树与图的生成树   若一个连通图中不存在任何回路，则称为树．由树的定义，直接得下列性质： （1）树中任意两节点之间至多只有一条边： （2）树中边数比节点数少1； （3）树中任意去掉一条边，就变为不连通图； （4）树中任意添加一条边，就会构成一个回路． 不难看出，任意一个连通图或者就是一个树，或者去掉一些边后形成一个树．一个连通图去掉一些边后形成的树称之为该连通图的生成树.一般来说，一个连通图的生成树可能不止一个． 求一个连通图的生成树有一个简单算法，这个算法就是在一个连通图中破掉所有的回路，剩下不含回路的连通图就是原图一个生成树，这个算法叫做“破圈法”． 图的矩阵  图的矩阵表示一个图可以用几何图形表示，这种表示有直观形象的优点.图还可以用矩阵表示，它给出一个代数结构，从而可以运用代数的技巧解决图论问题，而且有利于在计算机上进行运算. 特别应当提到的是，20世纪70年代出现了图的拟阵理论，它的发展对图的研究起到突出的促进作用.一个图由它的邻接性和关联性完全决定，这种信息可用矩阵表示.常用的有邻接矩阵和关联矩阵等.在无向图中前后相继连接的一串边的集合称为路．在有向图中，顺向的首尾相接的一串有向边的集合称为有向路．通常用顺次的节点或边来表示路或有向路，如图(2)中， 为一条路，该路也可用 来表示．起点与终点为同一节点的路称为回路（或圈）．如果一个图中，任意两个节点之间都存在一条路与之相连，称这种图为连通图． 图（2） 3. 无向图的邻接矩阵 3.1 无向图的邻接矩阵定义及表示 定义 ：设 是图 的结点，则称矩阵 为 的邻接矩阵，其中， 是使 邻接的边的条数 并且 是环时， ，否则 . 例如 则上图的邻接矩阵为: 再如： 它的邻接矩阵为： 3.2 无向图的邻接矩阵的性质 性质1   对角线元素全为0当且仅当图 没有环.此时 是对称矩阵. 性质2   在没有环的图中， 等于对应行或列中1的个数. 性质3   的第 行（或第 列）元素之和为结点 的度数 . 性质4   给定一个对称的元素0和1的 阶矩阵，则必可构造一个图 ,使 的邻接矩阵就是所给的. 性质5 零图的邻接矩阵为零矩阵. 例如图所示的图（3）和图（4）.请写出其所对应的邻接矩阵 图（4） 图（3） 则：图（3）的邻接矩阵为: ; 图（4）的邻接矩阵为: 4. 有向图的邻接矩阵 4.1 有向图的邻接矩阵的定义及表示 与无向图对应，有向图也有类似的表示： 定义 ： 设 是有向图 的结点，称矩阵 为 的邻接矩阵，其中 是以 为始点， 为终点的边的条数 . 我们再来看一个简单有向图 如图（5）： 图（5） 有向图 的邻接矩阵为： ； 4.2 有向图的邻接矩阵的性质 由定义知，有向图 的邻接矩阵 具有以下性质 . 性质1 简单图的邻接矩阵是一个0，1的矩阵：对角线元素为0，但不一定对称. 性质2  矩阵的各行和是相应顶点的出度，各个列和是相应顶点的入度.所有元素相加的和与边数相等. 性质3 矩阵 的 位置元素为由 到 的长度等于 的通路的数目，而 位置的元素为 到自身的回路的数目. 练习：分别画出给出的邻接矩阵 和 所对应的无向图 和有向图 . :           ; 图分别为: 5. 邻接矩阵的重要定理及应用 再观察4.1节 图（5）： 在图(5)中，我们可以计算出 , , 如下： ； ； 观察各矩阵不难看出， 中 到 长度为1,2,3,4的通路为别为0,12条。 到自身长度为1,2,3,4的回路分别为1,2,3,5条，其中有复杂回路。 中长度小于或等于4的通路有53条.