图论模型讲义

《图论模型讲义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录目录1第8章图论模型18.1图的基本知识28.1.1图的相关定义28.1.2图的顶点的度38.1.3子图及运算48.1.4图的连通性58.1.5一些特殊图78.2图的矩阵表示78.2.1邻接矩阵78.2.2关联矩阵88.3图的方法建模98.3.1图的最小生成树问题及算法101．树及最小生成树102．克鲁斯卡尔算法113．普利姆算法138.3.2图的最短路问题及算法151．迪克斯特拉算法158.3.3图的匹配及应用201.图的匹配202．指派问题：233．最优指派278.3.4图的覆盖及应用331.逻辑算法352．启发式算法：353．利用关联矩阵求

2、极小覆盖：378.3.5图的遍历问题391．边的遍历-中国邮差问题392．点的遍历-旅行商问题418.3.6竞赛图问题491．竞赛图的定义492．循环比赛排名508.4实战篇51第8章图论模型图论（GraphTheory）18世纪起源于欧洲。瑞士著名数学家欧拉(Euler）于173651年发表的第一篇图论论文—“哥尼斯堡七桥问题”，不但解决了曾经困扰了人们多年的难题，同时它宣告了图论这门学科的诞生。在普鲁士的小镇哥尼斯堡，一条河穿城而过，河中央有两个小岛，小岛之间及岛与河岸共有七座桥连接。能否从四块陆地中的任何一处出发，恰好通过每座桥一次再回到起点，

3、这就是著名的“哥尼斯堡七桥问题”。人们曾经做过很多尝试，但是都没有获得成功。为了解决这个问题，欧拉将问题进行几何抽象：将陆地分别用“点”代替，将桥用连接这些点的“线”来代替，得到一个包含四个“点”，七条“线”的“图”，将问题转化为“如何从一点出发一笔画出这个图，最后回到起点”的问题。因为每次经过一个点必须消耗掉两条与该点相关联的边（从一边进入，另一条边离开），所以和每个点相关联的边的数量应该是一个偶数，此问题显然是无解的。BADCABCD图1七桥问题图论中的“图”是指某类具体事物和这些事物之间的联系的一个集合。如果我们用点表示这些具体事物，用连接两点

4、的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为包含二元关系的离散系统提供了数学模型，借助于图论的概念、理论和方法，可以对该模型求解。随着相关理论和方法的不断完善和计算机技术的促进，图论渗透到物理、化学、通信科学、建筑学、生物遗传学、心理学、经济学、社会学等许多学科当中，并且得到广泛应用。图论这门学科涉及的问题多且广泛，看似朴实无华，本质上却十分复杂深刻，解决问题的方法也千变万化，灵活多变。8.1图的基本知识8.1.1图的相关定义图（Graph）是由一个表示对象的非空集合和一个表示这些对象之间关系的非空集合所构成

5、的二元组，通常用大写字母等表示。定义1：一个无向图(UndirectedGraph)是由一个非空点集和其中元素的无序关系集合构成，记为,简记为。称为无向图的顶点集（vertexset）或节点集(nodeset)，每一个元素称为图的一个顶点（vertex）或节点（node）；称为无向图的边集(edgeset)，每一个元素（即中某两个元素的无序对）记为或，称为无向图的一条边（edge）。当一条边可表示为时，称为边的端点，并称与（与）相邻（adjacent）；边称为与顶点关联（incident）。如果某两条边至少有一个公共顶51点，则称这两条边在图中相邻，

6、没有公共顶点的边称为相互独立的（independent）。定义2：一个有向图（digraph）是由一个非空点集和其中元素的有序关系集合构成，记为，简记为。称为有向图的顶点集或节点集，中的每一个元素称为该图的一个顶点或节点；称为有向图的弧集（arcset），中的每一个元素(即中某两个元素的有序对) 记为或，被称为该有向图的一条从到的弧（arc）。当一条弧可表示为时，称为的头（head），为的尾（tail），或者说到相邻，从相邻；称弧为的出弧（outgoingarc），为的入弧（incomingarc）。图的点集中点的数量称作图的阶（order），边集中

7、边的数量称作图的边数(size).当一个图的顶点集和边集都是有限集，则称该图为有限图。定义3：给一个图的每一条边（弧）赋予一个数字，则得到一个赋权图（weightedgraph）。这些数字可以表示距离，花费，时间等，统称为权重(weight)。无向图和有向图都可以赋权。例1．下面两个图分别是无向图，有向图和赋权图。Ge1v1e5e2e3e3v2v4v3v1Da1v4v2v3a6a2a4a5a32345Wv1v2v3v46图2无向图、有向图和赋权图只有一个顶点的图称为平凡图（trivialgraph），除平凡图外所有图都被称为非平凡图。如果图的一条边（

8、或者弧）的端点为同一个点，则称这条边为环（loop）。在无向图当中，如果两条边的端点相同，则称这两条边为关联