图论与网络模型 图论与网络介绍 网络最大流问题
图论与网络模型 一 .图论与网络介绍 二.网络最大流问题
图的基本概念 1关系图:表示若干事物之间具有的某种关系的 例:若有ABc,D,E五个人,他们之间相互认识的情 况为A与C、D、E认识;B与C、E认识;C与A、D 认识;D与A、C、E认识;与A、B、D认识 我们用点分别表示人,相互认识用线连接就得到下 面的图:
一、图的基本概念 1.关系图:表示若干事物之间具有的某种关系的 图. 例:若有A,B,C,D,E五个人,他们之间相互认识的情 况为:A与C、D、E认识;B与C、E认识;C与A、D 认识;D与A、C、E认识;E与A、B、D认识. 我们用点分别表示人,相互认识用线连接,就得到下 面的图: A ° ° B E ° ° C D °
2图是由若干个点和连线构成的 记为 G=V,E) 其中:V-点集;E-边集 点v称为顶点;连线e称为边或弧 例:哥尼斯堡七桥问题(从某点出发经过 七座桥各一次后回到起点) B C A
2. 图是由若干个点和连线构成的. 记为: G = (V, E) 其中: V----点集; E----边集. 点v 称为顶点; 连线e 称为边(或弧). 例: 哥尼斯堡七桥问题 (从某点出发,经过 七座桥各一次后回到起点) A B C D ° A B° C° D °
若两个点Ⅵ,有边e连接则称e与v,v是关联的; 若两条边e,e有公共顶点v,则称el,e是相邻的 3点的度--与点关联的边的条数记为d(v) 奇点--度数为奇数的点 偶点--度数为偶数的点 结论:一个图中奇点的个数必为偶数 4连通图:在一个图中若任何两个顶点之间至少有 一条路线连接则称这个图为连通图 5圈Cn:一条封闭的路线称为圈
若两个点v1, v2 有边e 连接,则称e与v1, v2 是关联的; 若两条边e1, e2 有公共顶点v,则称e1, e2 是相邻的. 3.点的度---- 与点v关联的边的条数. 记为d (v) 奇点----度数为奇数的点 偶点----度数为偶数的点 结论: 一个图中奇点的个数必为偶数. 4.连通图: 在一个图中,若任何两个顶点之间至少有 一条路线连接,则称这个图为连通图. 5. 圈 Cn : 一条封闭的路线称为圈
6完全图Kn:n个点之间都有边相连的图 如图 K2 K3 K4 7网络当圈的边弧有方向且各弧给予一定的权的图
6.完全图 Kn: n个点之间都有边相连的图. 如图: ° ° K2 ° ° ° K3 ° ° ° ° K4 7.网络:当图的边(弧)有方向,且各弧给予一定的权的图
二、网络最大流问题 最大流问题就是在一定条件下,使网络系统中 的某种流的流量达到最大的问题 例如:公路系统中的车辆流;水利系统中的水流;电 力系统中的电流;服务系统中的顾客流,信息系统中 的信息流等等
二、网络最大流问题 最大流问题就是在一定条件下,使网络系统中 的某种流的流量达到最大的问题. 例如: 公路系统中的车辆流;水利系统中的水流;电 力系统中的电流;服务系统中的顾客流,信息系统中 的信息流等等
如图为某物资的运输网络问从v到v的最大运输流 量是多少?弧线边的数字表示路线的容量,即 该弧的能够容纳的最大流量
如图为某物资的运输网络,问从vs到vt的最大运输流 量是多少? 弧线边的数字表示路线的容量,即 该弧的能够容纳的最大流量. 1 vs 2 3 4 vt 9 5 3 4 3 5 2 7 6
1基本概念 对一个网络D=(V,4) (1)网络流指在一定条件下流过一个网络的某种流 在各弧上的流量的集合 一定条件指 ()有一个起点v和终点v; Gi流过网络的流量有一定的方向; (i每一弧都有一个容量表示容许通过该 弧的最大流量 (2弧(%)的容量记为r; (3弧(vp)的流量记为x;:流X{x引(vv∈A}
1.基本概念: (1)网络流:指在一定条件下流过一个网络的某种流 在各弧上的流量的集合. 对一个网络D=(V,A) 一定条件指: (i)有一个起点vs和终点vt ; (ii)流过网络的流量有一定的方向; (iii)每一弧都有一个容量,表示容许通过该 弧的最大流量. (2)弧(vi , vj )的容量记为rij ; (3)弧(vi , vj )的流量记为xij ;流X={xij| (vi , vj ) A}
(4)可行流满足下述条件的流X={(v∈A称为 可行流: 弧的流量限制0x;s,(以)∈A; f中间点v的平衡条件: ∑x-∑x1=0,i≠S,t 从v流出 流进v的 的总量 的量 ff表示可行流X从v到v的流量 ∑x-∑ f,当 3=-厂,当 (5)最大流:在网络中流量最大的可行流
(4)可行流:满足下述条件的流X={xij| (vi , vj ) A}称为 可行流: (i)弧的流量限制 0xijrij , (vi , vj ) A ; (ii)中间点vi 的平衡条件: x x 0, i s,t . j ji j ij − = f=f(X) 表示可行流X 从vs 到vt 的流量 i t i s f f x x j ji j ij = = − − = 当 当 , , (5)最大流: 在网络中,流量最大的可行流. 从vi流出 的总量 流进vi的 总量
最大流问题的数学模型 max ∫,i=S ∑xn≡0,i≠S,t S。t ∫,i 0sxsr,(,")∈A 这是一个特殊的线性规划问题由于它的特殊性用 网络分析的方法求解比较方便
最大流问题的数学模型 = = − − = x r v v A i t i s t i s f f x x s t f ij ij i j j ji j ij 0 ,( , ) , , 0, , . . max 这是一个特殊的线性规划问题,由于它的特殊性,用 网络分析的方法求解比较方便