PPT《运筹学》

运筹学 图与网络分析

第十章?????? 图与网络 赵玮主要内容: 10.

1 基本概念10.2 最短路问题

(一)Bellman最优化原理

(二)Dijustra算法(双括号法)

(三)通信线路布施问题

(四)设备更新问题10.3 最小生成树

(一)基本概念与理论

(二)Kruskal算法(加边法、破圈法)

(三)丢边法(破圈法) 主要内容: 10.4 最大流问题

(一)基本概念

(二)双标号算法10.5 最小费用最大流

(一)基本概念

(二)求解算法 § 10.1 基本概念

1 图def1:一个无向图(简称为图)G是一个有序的二元组,记为G=(V, E).其中 V={V1…Vn}称为G的点集合,E=(eij)称为G的边集合,evj为连接VV与Vj的边. 若N和E均为有限集合,则称为G为有限图,否则称无限图.若G中既没有有限回路(圈),也没有两条边连接同一对点,则称G为简单图.如右图之(a),右图之(b)不是简单图.若G为简单图,且G中每个点对之间均有一条边相连,则称G为完全图.如图(a)是简单图,但不是完全图. 图a图bdef 2:一个有向图G是一个有序的二元组,记为G=(V, A),其中V=(V1V2…Vn)称为G的点集合,A={aij}称为G的弧(有向边)集合,aij是以Vi指向Vj的一条弧. |V|=n表示G中节点个数为n,此节点个数n也称为图G的阶|A|=m表示有向图G中弧的个数为m任一顶点相关联(连接)的边的数目称为该顶点的次数

2 连通图 def 3:在有向图G中,一个点和边的交替序列{Vi eij Vj…Vk ekl Vl} 称为G中从点Vi到Vl的一条路,记为A,其中Vi为此路A的起点,Vj为路A的终点;

若路A的起点与终点重合,则称A为回路;

又若G中点Vi与Vj间存在一条路,则称点Vi与Vj是连通的;

若G中任何二点都是连通的,则称G为连通图,或图G为连通的.在无向图中有对应的概念. 圈链无向图 回路 路 有向图

3 子图 def 4:设有两个图:G1= (V1, E1) ,G2= (V2, E2)若有 ,则称G1为G2的子图,记作 ;

若有 V1=V2而 ,则称图G1= (V1, E1) 是图G2= (V2, E2)的生成子图(支撑子图). 例:下示图G1是图G的子图,图G2是图G的生成子图. V1 V3 V2 V4 V1 V2 V4 V1 V3 V2 V4 (a)图G (b)图G1 (c)图G2

4 赋权图(加权图)与网路def 5:设G是一个图(或有向图),若对G的每一条边(或弧)eij都赋予一实数ωij,称其为该边(弧)的权,则G连同其他弧上的权集合称为一个赋权图,记作G= (V, E, W) 或G= (V, A, W),此中W={ωij},ωij为对应边(弧)eij的权.若G= (V, E, W) (或(V, A, W))为赋权图,且在G的V中指定一个发点(常记为Vs)和一个收点(记为Vt),其余点称为中间点,则称这样指定了发点与收点的赋权图G为网络. § 10.2 最短路问题 def 6:设G =(V, A, W)为一个赋权有向图,Vs为指定发点,Vt为指定收点,其余为中间点,P为G中以Vs到Vt的一条有向路,则称 为路P的长度,若有 则称 为G中从Vs到Vt的最 短路,为该最短路的长度(此中F为G中 所有从Vs到Vt的全体有向路的集合). 最短路问题在企业厂址上选择,厂址布 局,设备更新,网络线路安装等工程设计与 企业管理中有重要应用.

(一)Bellman最优化原理

1 命题1:若P是网络G中从Vs到Vt的一条最小路,Vl是P中除Vs与Vt外的任何一个中间点,则沿P从Vs到Vl的一条路P1亦必是Vs到Vl的最小路. Vs V1 Vl V2 Vt P2 P1 证明(反证): 若P1不是从Vs到Vl的最小路,则存在另一条 Vs 到Vl的路P2使W(P2)