运筹学(OperationalResearch)第六章图与网络分析本章主要内容图论基础知识最短路问题最小生成树问题最大流问题网络计划一、哥尼斯堡七桥问题欧洲的普瑞格尔河流过哥尼斯堡市中心，河中有岛两座，筑有七座古桥，经常有人上岛散步，久而久之，人们就提出了如下的智力问题：能否过每座桥恰一次，再返回出发点。这就是七桥问题（如右图）现在将四块陆地看作四个点，若两块陆地之间有一座桥，则用一条线连起来，得到右图。这样就转化为一笔画问题（即是否是Euler图问题）即能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。二、四色问题1852年，伦敦一位学生Guthrie提出一个猜想：任意给定一张无色地图，把每国版图染上一种颜色，且使邻国异色，用四种颜色足矣。如右图将七个国家A,B,C,D,E,F,G收缩为7个点，若两个国家相邻则用一条线连起来，就得到下图。这实际是图论中的顶点着色问题。即用四种颜色就可使得任意相邻的两个顶点的颜色均不相同。ABCDEFG三、Ramsey问题1928年，英国数学家、哲学家、经济学家拉姆赛（Ramsey)提出了这样一个问题：任给n个人，其中必有p人彼此相识或者q人彼此不相识，问n至少是几？把上述最小的n记作r(p,q),到现在为止，只求出了9个数，比如r(3,3)=6,r(3,4)=9，r（3，5）=14任意6个人，其中必有3个人相识，或3个人不相识。这就是Ramsey问题中的一个结果。将每个人看作一个点，任意两人之间均用一条红线（表示二人相识）或蓝线（表示二人不相识）连起来（如下图）。B,C,F三人相识。ABCDEF§1图论基础知识图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物之间具有这种关系。一、图的基本概念图(Graph)是由一些点和连接一对点的若干条线段组成。点称为图的顶点（Vertex），线段称为图的边(Edge)。若记V={v1,v2,…vn},E={e1,e2,…em},则G=(V,E).连接顶点u,v的边e可记为e=[u，v]，并称u和v为边e的两个端点，边e与顶点u和v相关联，顶点u和v相邻。与同一个顶点相关联的两条边也称为相邻的。ueve2环（Loop)两个顶点重合的边。(如e1)多重边(multipleedge)两个顶点之间有多与一条边。(如e4和e5)简单图(simplegraph)无环和多重边的图。度（次degree）以点v为端点的边的个数。记为d（v）。（注意：算次时环算两条边）如d(v1)=4,d(v2)=2奇点(Oddvertex)度为奇数的点。(如v3,v5)偶点(Evenvertex)度为偶数的点。(如v1,v2)孤立点次为0的点。（如v6)悬挂点次为1的点。(如v5)v2v1v3v4v5v6e1e2e3e4e5e6e7链（chain）图中点、边的交错序列(v1e1v2e2…vt-1et-1vt),如果满足ek=[vk,vk+1]（k=1，2，…，t-1），则称为一条连接v1到vt的链。初等链(primarychain)点都不同链。圈(cycle)起点与终点重合的链（即v1=vt）。初等圈(primarycycle)除了起点和终点外，其它点均不同的圈。简单圈(simplecycle)边不相同的圈。连通图(connectedgraph)任意两点均存在链的图。支撑子图(SpanningSubgraph)：称G/=(V,E’)为G=(V,E)(其中E’是E的子集)的支撑子图。v3v2e2v1v4v5e1e3e5e6e7二、两个简单定理TheoremⅠ图G=(V,E)中，所有点的度之和是边数的两倍。证明：因为计算度时，每条边被它的端点各用了一次，所以所有点的度之和是边数的两倍。TheoremⅡ任一个图中，奇点的个数为偶数。证明：∵∑奇点的度（奇数)+∑偶点的度(偶数）=2×边数=偶数∴∑奇点的次=偶数∴奇点有偶数个三、有向图定义：一个有向图(DirectedGraph或Digraph)G是由点及含有箭头的边（称为弧）所构成，记为D=(V，A).其中V称为图G的顶点集(VertexSet)或节点集(NodeSet)，V中的每一个元素称为该图的一个顶点(Vertex)或节点(Node)；A称为图的弧集(ArcSet)，A中的每一个元素(即称为该图的一条从vi到vj的弧(Arc).一条方向是从vi指向vj的弧记为(vi,vj).设G=(V,A),称为G的子图(Subgraph)图的支撑子图(Spanni