运筹学第六章图与网络分析(新)a管理精品资料

《运筹学第六章图与网络分析(新)a管理精品资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、作业：P170~1716.36.4(c)6.56.7(b)第六章图与网络分析哥尼斯堡七桥问题德国古城—哥尼斯堡—普雷格尔河—七桥问题：从任一桥头出发，依次走过每座桥，每座桥只走一次，最后回到出发点。——一笔画问题2.中国邮递员问题邮递员送信送报要走完全部所负责的街道，最后回到邮局，如何走路程最短？第一节图的基本概念一、图的概念1.图（无向图）图是由点与边组成的集合，记为：G=(V,E)，其中V≠Φ，表示图G中点的集合，E表示图G中边的集合。图中点的个数记为p，称为图的阶；图中边的条数记为q。2.端点、关联边、相邻若边e可以表示为e=（vi，vj)，则称vi和vj是

2、边e的端点；边e称为点vi和vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻。若边ei、ej有公共的端点，称边ei和ej相邻。3.环，多重边，简单图如果边e的两个端点相重，称该边为环。如果两个端点之间的边多于一条，称为多重边。无环、无多重边的图称为简单图。4.次，奇点，偶点，孤立点，悬挂点与某一个点vi相关联的边的数目称为点vi的次。记为d(vi)。次为奇数的点称为奇点，次为偶数的点称为偶点。次为0的点称为孤立点。次为1的点称为悬挂点。.v65.链，圈，连通图图中由相邻的点和互不相同的边组成的交替序列μ称为链。若链中的所有顶点也不相同，则该链

3、称为路。起点与终点重合的链称为圈。起点与终点重合的路称为回路。若图中任意两个顶点之间都至少存在一条链，则称该图为连通图。6.完全图，偶图若一个简单图中任意两点之间均有边相连，则称该图为完全图。对含有n个顶点的完全图，其边数有条。如果图的顶点能分成两个互不相交的非空集合V1和V2，使在同一集合中任意两个顶点都不相邻，则称该图为偶图（或二分图）。若偶图的顶点集合V1、V2之间的每一对不同顶点之间都有一条边相连，则称该图为完全偶图。在完全偶图中，V1若有m个顶点，V2有n个顶点，则其边数共有m×n条。7.子图，部分图对图G1=｛V1，E1｝和图G2=｛V2，E2｝

4、，若有，则称G1是G2的一个子图。若有，则称G1是G2的一个部分图。定理：在图G中，所有顶点次之和等于边数的两倍。即：定理：在任一图中，奇点的个数必为偶数。例：有八种化学药品，某些不能放入同一个仓库，用连线表示。见下图。（v1)（v2，v4，v7)（v3，v5)（v6，v8)例：四色问题。8.同构对图G1=｛V1，E1｝和图G2=｛V2，E2｝，如果顶点集合V1与V2之间以及边的集合E1与E2之间都建立了一一对应关系，并且图G1的两顶点之间的边对应于图G2对应顶点的边，则称图G1与图G2是同构的。9.赋权图：对一个无向图G的每一条边（vi，vj)，相应地有一个

5、数wij，则称这样的图G为赋权图（也称网络图，记为N)，wij称为边（vi，vj)上的权。10.一笔画问题欧拉链：给定一个连通图G,若存在一条链，过每边一次且仅一次，则称这条链为欧拉链。欧拉圈：若存在一个简单圈，过每边一次，则称这个圈为欧拉圈。欧拉图：有欧拉圈的图称为欧拉图。能一笔画的图一定是欧拉圈或含有欧拉链。定理：连通的多重图G是欧拉图的充要条件是G中无奇点。推论：连通的多重图G有欧拉链的充要条件是G中恰有两个奇点。第二节树图和图的最小部分树树图：无圈的连通图称为树图，记为T(V,E)。2-1树的性质性质1：任何树中必存在至少两个次为1的点（悬挂点）。性质

6、2：具有n个顶点的树的边数恰好为(n-1)条。性质3：任何具有n个顶点、（n-1)条边的连通图是树。2-2图的最小部分树（最短树）如果G1是G2的部分图，又是树图，则称G1是G2的部分树（或支撑树）。G2的树枝总长最小的部分树称为该图的最小部分树。定理1.图中任一个点i，若j是与i相邻点中距离最近的，则边(i,j)必含在该图的最小部分树内。推论：把图的所有点分成V和两个集合，则两集合之间连线的最短边一定包含在最小部分树内。2-3求最小部分树的破圈法和避圈法1.避圈法2.破圈法从网络图N中任取一回路，去掉这个回路中权数最大的一条边，得一子网络图N1。在N1中再任取一回

7、路，再去掉回路中权数最大的一条边，得N2。如此继续下去，一直到剩下的子图中不再含回路止。该子图就是N的最小部分树。例:某工厂内联结六个车间的道路网如图所示，已知每条道路的长，要求沿道架设联结六个车间的电话线网，使电话线的总长最小。第三节最短路问题3-1狄克斯特拉（标号）算法（dijkstra)：令：dij为相邻两点vi与vj的距离，若vi与vj不相邻，则令dij=∞，显然，dii=0。L1i为从v1到图中任一点vi的最短距离。狄克斯特拉（标号）算法步骤：（1）从v1点出发，将L11=0标在v1旁的小方框内，表