图与网络分析资料讲解.ppt

图与网络分析图与网络分析引 言 第一节 图与网络的基本概念第二节 树第三节 最短路径问题第四节 网络最大流问题 第五节 最小费用最大流问题 引 言第一阶段第一阶段从十八世纪中叶从十八世纪中叶到十九世纪中叶到十九世纪中叶游戏产生, 代表工作Konigsber七桥问题第二阶段第二阶段从十九世纪中叶从十九世纪中叶到二十世纪中叶到二十世纪中叶问题大量出现, Hamilton问题;地图四色问题;36年, Konig第一本图论问世第三阶段第三阶段二十世纪中叶以后二十世纪中叶以后Ford和Fulkerson建立的网络流理论图论发展的三个阶段图论发展的三个阶段图论(Graph Theory)是研究图的理论, 是运筹学中一重要的分支. 有200多年历史, 大体可划分为三个阶段.目前图论与网络流理论被广泛应用于管理科学、计算机科学、信息论、控制论、物理、化学、生物学、心理学等各个领域.A AB BC CD DKonigsberKonigsberPregei Pregei RiverRiver图1有没有办法从某处(如A)出发, 经过各桥一次且仅一次最后回到原地呢？1235467Euler在1736年发表了一篇题为“依据几何位置的解题方法”论文,有效解决了Konigsber七桥难题,这是有记载的第一篇图论论文,Euler也被公认为图论的创始人.C CD DA AB B给出一个正12面体图形,共有20个顶点,分别表示全球20个主要城市,要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次,最后回到原处的周游世界线路(并不要求经过每条边).环球旅行问题.例2: Hamilton回路是19世纪英国数学家Hamilton提出图4伦敦伦敦例3:一个班级的学生共计选修A、B、C、D、E、F六门课程,其中一部分人同时选修A、C、D,一部分人同时选修B、C、F,一部分人同时选修B、E,还有一部分人同时选修A、B,期终考试要求每天考一门课,六天内考完,为了减轻学生负担,要求每人都不会连续参加考试, 试设计一个考试日程表.A A、C C、D DB B、C C、F FB B、E EA A、B BA AF FE ED DC CB B图5解:以每门课程为一个顶点,共同被选修的课程之间用边相连, 得图5.按题意, 相邻顶点对应课程不能连续考试,不相邻顶点对应课程允许连续考试,因此作图5的补图(图-6).A AF FE ED DC CB B图6图7问题是在图7中寻找一条经过每个顶点一次且仅一次的路线(Hamilton回路).A AF FE ED DC CB B如如CEAFCEAFDB CDB C是一是一HamiltonHamilton回路回路A AF FE ED DC CB BCEAFDB C,就是一个符合要求的考试课程安排.图8第一节第一节 图与网络的基本概念图与网络的基本概念一、图与网络的基本概念一、图与网络的基本概念1 1、图及其分类、图及其分类定义1:由点集V=vi和V中的元素的无序对的一个集合E=ek所构成的二元组称为图(Graph),记为G=(V,E).V中的元素vi叫做顶点, E中的元素叫做边.当V,E为有限集合时, G称为有限图, 否则, 称为无限图.图是由一些点及一些点之间的联线(不带箭头或带箭头)的组成的.例4 在图9中, V=v1, v2, v3,v4, v5, v6, E=e1, e2, e3, e4, e5, e6 , e7, e8.其中:e1=v1,v2 e2=v1,v2 e3=v2,v3 e4=v3,v4 e5=v4,v1 e6=v1,v3 e7=v3,v5 e8=v4,v4 图9v v1 1v v3 3v v2 2v v4 4v v6 6v v5 5e e1 1e e3 3e e5 5e e6 6e e4 4e e8 8e e7 7e e2 2定义4: 若图G=(V,E)的点集V可分为两个非空子集X, Y, 满足: XY=V, XY=, 使得E中的每条边的两上顶点必有一个端点属于X,而另一个端点Y,则称G为二部图(偶图)v v1 1v v3 3v v2 2v v4 4e e1 1e e2 2e e4 4e e3 3v v1 1v v2 2v v3 3v v4 4v v5 5U U1 1U U2 2U U3 3U U4 4图113 3、子图、子图定义7 设G=(V, E)和G1=(V1, E1).若V1V, E1 E则称G1为G的子图; 若G1=(V1, E1)是G=(V, E)的子图, 且V1=V, 则称G1为G的生成子图(支撑子图)若G1=(V1,E1)是G=(V,E)的子图,且V1V, E1是E中所有端点属于V1的边组成的集合,则称G1是G的关于V1的导出子图v v2 2e e6 6v v1 1v v5 5v v4 4v v3 3e e1 1e e8 8e e7 7e e5 5e e4 4e e3 3e e2 2图图G=(VG=(V, , E E) )v v1 1v v5 5v v4 4v v2 2e e1 1e e5 5e e3 3( (a) Ga) G的子图的子图v v1 1v v5 5v v4 4v v2 2v v3 3e e8 8e e6 6e e5 5e e2 2GG的生成子图的生成子图v v1 1v v5 5v v2 2e e1 1e e6 6e e5 5GG的导出子图的导出子图4 4、网络、网络定义 由点或边带有某种数量的指标的图称为网络与无向图相对应的网络称为无向网络与有向图相对应的网络称为有向网络二、连通图二、连通图定义8 无向图G=(V, E), 若图G中某些点与边的交替序列可以排成 的形成, 且 , 则称这个点边序列为连接 的一条链(chain), 链长为k.若点边列中没有重复的点与重复边者称为初等链定义9 无向图G=(V, E), 连接 的一条链是同一个点时, 称为圈(circle).若圈中没有重复的点与重复边者称为初等圈定义(链) 如果图中的某些点、边可以排列成点和边的交错序列, 则称此为一条链.定义(圈) 如一条链中起点和终点重合,则称此为一条圈. .p258p258v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8v v8 8e e1 1e e2 2e e4 4e e5 5e e6 6e e9 9e e1010e e8 8e e7 7e e3 3v v1 1v v5 5v v4 4v v2 2v v3 3e e1 1e e7 7e e6 6e e5 5e e4 4e e3 3e e2 2有向图v v1 1v v5 5v v4 4v v2 2v v3 3e e1 1e e8 8e e7 7e e6 6e e5 5e e4 4e e3 3e e2 2有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图v1v1v5v5v4v4v2v2v3v3e1e1e7e7e6e6e5e5e4e4e3e3e2e2有向图v1v1v5v5v4v4v2v2v3v3e1e1e7e7e6e6e5e5e4e4e3e3e2e2有向图v1v1v5v5v4v4v2v2v3v3e1e1e7e7e6e6e5e5e4e4e3e3e2e2链v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3v v1 1v v5 5v v4 4v v2 2e e1 1e e7 7e e6 6e e3 3v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3圈第二节第二节 树树树是一类极其简单而很有用的图, 在自然和社会科学中的许多领域中均有广泛的应用.例:乒乓球单打比赛抽签后,可用如下的图来表示相遇情况.一、树的概念与性质一、树的概念与性质定义14 连通且不含圈的无向图称为树.树中次为1的点称为树叶, 次大于1的点称为分枝点.如果一个无圈的图中每一个分支都是树,则称图为森林.树的性质: 1 在图中任意两点之间必有一条而且只有一条通路.2 在图中划去一条边, 则图不连通.3 在图中不相邻的两个顶点之间加一条边,可得一 个且 仅得一个圈.4 图中边数有p-1(p为顶点数)a ab bc cf fe ed dh hg g例b bf fe ed db bf fd dg gb bc ce ed da ab bc ch ha af fd dg g二、图的生成树二、图的生成树定义15 如果图T是G的一个生成子图, 而且T又是一棵树, 则称图T为一棵生成树(支撑树).图G中属于生成树的边称为树枝, 不在生成树中的边称为弦(chord)一个子图与生成树的区别是: 子图与原图相比少弦又少点, 生成树与原图相比少弦不少点. 图图 ( (a) a) 图图 ( (b)b) 例如, 图(b)是图(a)的一个支撑树 v1v1v4v4v3v3v2v2v5v5v6v6图图v1v1v4v4v3v3v2v2v5v5子图子图v1v1v4v4v3v3v2v2v5v5v6v6生生成成子子图图v1v1v4v4v2v2v5v5v6v6树树v1v1v4v4v3v3v2v2v5v5v6v6生生成成树树三、最小生成树问题三、最小生成树问题定义16 若连通图G=(V,E),每条边上有非负权L(e),则一棵生成树所有树枝上权的总和, 称为这个生成树的权.具有最小权的生成树称为最小生成树(最小支撑树)简称最小树.许多网络问题都可以归结为最小树问题.如设计长度最小的公路网把若干城市联系起来;设计用料最省的线网把有关单位联系起来等等.求最小生成树问题的两种算法求最小生成树问题的两种算法1、破圈法:在连通图中取一圈,去掉一条权数最大边, 在余下图中重复上述步骤,直到无圈为止,即得最小生成树.【例7】 一个镇有7个自然村,其间道路及各道路长度如下图所示,各边上的数字表示距离,问题如何拉线才能使用线最短.v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636破圈法破圈法v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323总线长总线长=1+4+9+3+17+23=57=1+4+9+3+17+23=572、避圈法: 将连通图所有边按权数从小到大排序,每次从未选的边中选一条权数最小的边(如果有几条都是最小权数的边,则可从中任选一条),并使之与已选取的边不能构成圈,直到得到最小生成树。