《运筹学第八章》PPT课件

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

1、主讲教师：联系电话：短号：E-mail:清华大学出版社《运筹学教程》（第三版）运筹学基础胡运权主编教材运筹帷幄之中决胜千里之外运筹学课件图与网络分析第八章一、图及其分类ABDEC甲已AB定义一一个图是有点集V={vi}和V中元素的无序对的一个集合E={ek}所构成的二元组，记G={V，E}，V中的元素vi称为顶点，E中的元素ek称为边。当V、E为有限集合时，称G为有限图；否则称G为无限图。第一节图与网络的基本知识v1v2v3v5v4e1e3e4e2e5e6e7e8e9v1v2v3v4e1e2e3e4相邻点，如

2、v1、v2，同时它们也称为边e1的端点边相邻，如e1、e2(有公共端点)，同时它们也称为点v1的关联边无向边——端点无序，如图1中e1、e2等有向边——端点有序，如图2中e1、e2等图1图2环（自回路）——边的各个端点相同，如图1中e9有向图——边是有向的，如图2无向图——边是无向的，如图1第一节图与网络的基本知识v1e1v3v2e2e3e4e5图3多重边，如图3中v2、v3，同时有两条边e4、e5定义二一个图既不含环、也不含多重边，则该图称为简单图；一个图含多重边，则该图称为多重图。第一节图与网络的基本知识

3、定义三每一对顶点都有且只有一条无向（有向）边相连的简单图称为完全图；定义四设G={V，E}，X、YV，且X∪Y＝V，X∩Y=φ，任意边ek=（ei，ej）∈E，有ei∈X，ej∈Y，称为二部图（偶图）；第一节图与网络的基本知识定义五以点v为端点的边数叫做点v的次（度），记d(v)定理1任何图中，顶点的次数的总和等于边数的2倍定理2任何图中，顶点的次为奇数的顶点数为偶数定义六有向图中，以v为起始的边数叫做点v的出次（度），记d+(v)以v为终点的边数叫做点v的入次（度），记d-(v)定义七设G={V，E}，X

4、V，E’E，如果ek=（ei，ej）∈E’，有ei、ej∈X，则；称G’={X，E’}为G的子图；如X=V，称G’为G的生成子图.定义八设G={V，E}，如果任意ek=（ei，ej）∈E，f是E到正实数集上的一个函数，则称G为加权图，其中f(ei)称为ei∈的权第一节图与网络的基本知识定义九设G={V，E}，如G中的某些边与点的交替序列可以排成（vi0,ei1,vi1,ei1……，vik-1,eik,vik），且eil=（vil-1,vil）(l=1,2……k),则称该序列为一条链，链长为k(注意，对于有

5、向图时不考虑边的方向)。定义十在无向图中，如果一条链的起始与终点相同时，称该链为圈。定义十一设G={V，E}，任意v1、v2∈V，都存在一条链，称该图为连通图。定义十在有向图中，如果一条链的所有边的方向相同时，称该链为路；同样圈中所有边的方向相同时，称该圈为回路。任意不连通的图，都可以分成若干个连通子图，每个子图称为原图的分图。第一节图与网络的基本知识二、图的表示类v1v2v3v4v5976548324A=aij=wij(vj,vj)∈E0其它0924790340230854480670560权矩阵令所有权为

6、1A=0111110110110111110110110邻接矩阵第一节图与网络的基本知识A=011000001000010010010001010101000010v1v2v3v4v5v6其邻接矩阵为：第一节图与网络的基本知识三、欧拉回路定义十二连通图G中，如存在一条路，经过每一边且仅一次，则称这条路为欧拉路，如该路为一条回路，称欧拉回路。定理3无向图G是欧拉图的充分必要条件为G中没有奇点。推论1无向图G是欧拉图，当且仅当G的边集可以划分成若干个初等回路。推论2无向图G有欧拉路，当且仅当G的中有两个奇点。定理

7、3有向图G是欧拉图的充分必要条件为G每个顶点的入次等于出次。第一节图与网络的基本知识定义十三无向图G中，如不存在一条回，则该图称为树记T。树中次为1的点称叶，否则称分支点定理6T是树T无圈且m=n-1(其中n为顶点数，m为边数，下同)T连通且m=n-1T无圈，但加一条新边即得唯一圈T连通，但舍去任一边则不连通T任意两点有唯一链相连定义十四无向图G中，如生成图为树，则该树为图G的生成树定理无向图G中有生成树充分必要条件为G连通树第一节图与网络的基本知识第二节树及其最小生成树最小生成树算法：1）Kruskal2）

8、破圈法避圈法（Kruskal）6445843557256vs6445843557256破圈法（Kruskal）ABFGECD例：从某供气站要向A、B、C、D、E、F、G小区供气，问如何铺设煤气管道，使得需要铺设管道的总长度最短第三节最短路问题及其算法最短路算法——DijKstra算法例：从油田铺设管道，把原油从A地运到G地，要求管道必须按照图中给定的道路铺设，问如何铺设煤气管道，使的需要铺设管道的长