图论知识及运用举例

《图论知识及运用举例》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图论知识及运用举例1概论图论中的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。图是运筹学（OperationsResearch）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论最短路问题、最

2、大流问题、最小费用流问题和匹配问题等。2图的基本概念2.1无向图一个无向图(undirectedgraph)是由一个非空有限集合和中某些元素的无序对集合构成的二元组，记为。其中称为图的顶点集（vertexset）或节点集（nodeset），中的每一个元素称为该图的一个顶点（vertex）或节点（node）；称为图的边集（edgeset），中的每一个元素(即中某两个元素的无序对) 记为或，被称为该图的一条从到的边（edge）。当边时，称为边的端点，并称与相邻（adjacent）；边称为与顶点关联（i

3、ncident）。如果某两条边至少有一个公共端点，则称这两条边在图中相邻。边上赋权的无向图称为赋权无向图或无向网络（undirectednetwork）。我们对图和网络不作严格区分，因为任何图总是可以赋权的。一个图称为有限图，如果它的顶点集和边集都有限。图的顶点数用符号或表示，边数用或表示。当讨论的图只有一个时，总是用来表示这个图。从而在图论符号中我们常略去字母，例如，分别用和代替和。端点重合为一点的边称为环(loop)。一个图称为简单图(simplegraph)，如果它既没有环也没有两条边连接同

4、一对顶点。2.2有向图定义一个有向图（directedgraph或digraph）是由一个非空有限集合和中某些元素的有序对集合构成的二元组，记为。其中称为图的顶点集或节点集，中的每一个元素称为该图的一个顶点或节点；称为图的弧集（arcset），中的每一个元素(即中某两个元素的有序对) 记为或，被称为该图的一条从到的弧（arc）。当弧时，称为的尾（tail），为的头（head），并称弧为的出弧（outgoingarc），为的入弧（incomingarc）。对应于每个有向图，可以在相同顶点集上作一个图

5、，使得对于的每条弧，有一条有相同端点的边与之相对应。这个图称为的基础图。反之，给定任意图，对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这样的有向图称为的一个定向图。以下若未指明“有向图”三字，“图”字皆指无向图。2.3完全图、二分图每一对不同的顶点都有一条边相连的简单图称为完全图(completegraph)。个顶点的完全图记为。若，，（这里表示集合中的元素个数），中无相邻顶点对，中亦然，则称为二分图(bipartitegraph)；特别地，若，则，则称为完全二分图，

6、记成。2.4子图图叫做图的子图（subgraph），记作，如果，。若是的子图，则称为的母图。的支撑子图（spanningsubgraph，又成生成子图）是指满足的子图。2.5顶点的度设，中与关联的边数（每个环算作两条边）称为的度(degree)，记作。若是奇数，称是奇顶点(oddpoint)；是偶数，称是偶顶点(evenpoint)。关于顶点的度，我们有如下结果：(i)(ii)任意一个图的奇顶点的个数是偶数。2.6图与网络的数据结构网络优化研究的是网络上的各种优化模型与算法．为了在计算机上实现网络

7、优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设是一个简单有向图，，并假设中的顶点用自然数表示或编号，中的弧用自然数表示或编号。对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。（i）邻接矩阵表示法邻接

8、矩阵表示法是将图以邻接矩阵（adjacencymatrix）的形式存储在计算机中。图的邻接矩阵是如下定义的：是一个的矩阵，即，也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有个元素中，只有个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。（ii）关联矩阵表示法关联矩阵表示法是将图以关联矩阵（incidencematrix）的形式存储在计算机中．图的关联矩阵是如