运筹学胡运权第08章

《运筹学胡运权第08章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章图与网络分析(GraphTheoryandNetworkAnalysis)本章内容图与网络的基本知识树最短路问题最大流问题最小费用流问题BDACABCD哥尼斯堡七空桥一笔画问题§1图与网络的基本知识环球旅行问题一个图是由点集V={vj}和V中元素的无序对的一个集合E={ek}构成的二元组，记为G=(V,E),其中V中的元素vj叫做顶点，V表示图G的点集合；E中的元素ek叫做边，E表示图G的边集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例图1定义1图及其分类如果一个图是由点和边所构成的

2、，则称其为无向图，记作G=(V,E)，连接点的边记作[vi,vj],或者[vj,vi]。如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}图2图及其分类一条边的两个端点是相同的,那么称为这条边是环。如果

3、两个端点之间有两条以上的边，那么称为它们为多重边。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。定义2定义3图及其分类定义4图G=(V,E)的点集V可以分为两个非空子集X，Y，即X∪Y=V,X∩Y=，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图(偶图)，有时记作G=(X,Y,E)。X:{v1,v3,v5}Y:{v2,v4,v6}v1v3v5v6v4v2图及其

4、分类v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。以点v为端点的边的个数称为点v的度（次），记作。图中d(v1)=4，d(v6)=4（环计两度）定义5顶点的次有向图中，以vi为始点的边数称为点vi的出次，用表示；以vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。所有顶点的入次之和等于所有顶点的出次之和。定理1定理2所有顶点度数之和等于所有边数的2倍。在任一

5、图中，奇点的个数必为偶数。定义6顶点的次图G=(V,E)，若E′是E的子集，V′是V的子集，且E′中的边仅与V′中的顶点相关联，则称G′=(V′,E′)是G的一个子图。特别是，若V′=V，则G′称为G的生成子图(支撑子图)。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图定义7子图在实际应用中，给定一个图G=（V,E）或有向图D=（V,A）,在V中指定两个点，一个称

6、为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。定义8无向图G=(V,E)，若图G中某些点与边的交替序列可以排成(vi0,ei1,vi1,ei2,…,vik-1,eik,vik)的形式，且eit=(vit-1,vit)(t=1,…,k)，则称这个点边序列为连接vi0与vik的一条链，链长为k。点边列中没有重复的点和重复边者为初等链。连通图连通图无向图G中，连结vi0与vik的一条链，当vi0与vik是同一个

7、点时，称此链为圈。圈中既无重复点也无重复边者为初等圈。定义9定义10一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的一个分图。对于有向图可以类似于无向图定义链和圈，初等链、圈，此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同。对于网络（赋权图）G=（V,E）,其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。设图G=（V,E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵

8、。定义11定义12图的矩阵表示当G为无向图时，邻接矩阵为对称矩阵。例权矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437图的矩阵表示欧拉回路与中国邮路问题定义13连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图(E图)。