运筹学图与网络优化

《运筹学图与网络优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章图与网络优化图论概述图论(GraphTheory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。网络规划概述网络规划(NetworkProgramming)是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。七桥问题七桥问题图形原理及方法七桥问题是图论中的著名问题。1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并

2、证明了该问题不存在肯定回答。原因在于该图形有顶点连接奇数条边。§10.1图的基本概念一个图(Graph)定义为三元有序组V(G)是图的顶点集合E(G)是图的边集合记Ψ是关联函数图的端点设G是一个图(Graph)G=(V(G),E(G))，则称e连接u和v，称u和v是e的端点。若称端点u，v与边e是关联的，称两个顶点u，v是邻接的。设G是一个图，图10－３G的几何实现图的几何实现一个图可用一个几何图形表示,称为图的几何实现，其中每个顶点用点表示，每条边用连接端点的线表示。图的几何实现有助与我们直观的了解图的许多性质。说明

3、一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自身.并称图形的点为顶点，图形的线为边。图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。几何实现图例在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下图中，它共有4个顶点，6条边；而e3与e4的交点不是这个图的顶点。平面图一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图。基本概念端点重合为一

4、点的边称为环。连接同一对顶点的多条边称为多重边。在右图中，e5是一个环，e1与e2是多重边，v1和e1,e2,e3是关联的，v1与v2,v3是邻接的。邻接矩阵设G是一个图，G=(V(G),E(G))，定义图G的邻接矩阵A(G)=(aij)为m×m矩阵,aij是顶点vi与边vj相邻接的边数。其中关联矩阵设G是一个图，G=(V(G),E(G))定义图G的关联矩阵M=(mij)为m×n矩阵；其中mij是顶点vi与边ej相关联的次数，取值可能为0、1、2。注图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计

5、算机中。关联矩阵和邻接矩阵统称图的矩阵表示。顶点的度设G是一个图，G=(V(G),E(G))，定义图G的顶点v的度为与顶点v相关联的边数，记作d(v)例称度为奇数的顶点为奇点；称度为偶数的顶点为偶点。例22222224+3+3+4=14=2×7关联矩阵性质图G的关联矩阵M=(mij)为m×n矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于2。因此，图G的关联矩阵M所有元素之和既等于所有顶点的度之和，又等于边数的2倍。定理　设G是一个图，则推论图中奇点的数目为偶数。证明记简单图一个图称为简单图，如果它既没有环也没有

6、多重边。下图是简单图。本书只限于讨论有限简单图，即顶点集与边集都是有限集的图。u1u2u3u4f1f2f6f3f5f4只有一个顶点的图称为平凡图；边集是空集的图称为空图。同构称G和H是同构的，记为　　　，使得给定两个图如果存在两个一一对应同构图例图G与图H是同构的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4完全图Kn完全图是每一对不同顶点都恰有一边的简单图；具有n个顶点的完全图记为Kn.K5二分图二分图是一个简单图，其顶点集合可分划成两个子集X与Y，使得每条边的一个端点在X，另

7、一个端点在Y;(X,Y)也称为图的二分划。x1x2x3y1y2y3完全二分图完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连；记为Km,n，其中K3,3特殊图例K5K3,3都是极小的非平面图子图称图H是图G的子图，图G及其基本图称H是G的支撑子图，如果称H是G的真子图，若如果表示关联函数记为在H的限制。顶点导出子图设W是图G的一个非空顶点子集,以W为顶点集，以二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为G[W]。导出子图G[V-w]记为G-W，即它是从G中

8、删除W中顶点以及与这些顶点相关联的边所得到的子图。如果W仅含一个顶点v，则把　简记为　　　。边导出子图设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为G[F]。记G-F表示以E(G)F为边集的G的支撑子图，它是从G中删除F中的边所得到的子图。如F={e}，