下载此文档

离散数学－网络模型.ppt

文档分类：通信/电子 | 页数：约24页举报非法文档有奖

1/ 24

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/ 24 下载此文档

文档列表 文档介绍

离散数学
黄晓宇
HuangSir@
本讲内容
网络模型的基本概念
最大流算法
最大流最小割
匹配
引例
b
c
码头a
炼油厂z
e
d
5
3
2
4
2
4
2
求出从码头到炼油厂的最大流量
定义
一个传输网络是一个满足下列条件的简单加权有向图
一个源
一个汇
有向边(i,j)的权 Cij 是非负数,称为容量
一个网络的流量是对每边赋流量值,该值不超过所在边的容量。
定义(二)
G是一个传输网络, Cij是(i,j)的容量。 G的一个流量F 赋予(i,j) 值Fij,满足:
Fij ≤ Cij
对非源点和收点i和j,有
中间节点的流出流量=流入流量
定义(三)
网络流量
起点a的流出流量=终点z的流入流量,这个流量称作流量F的值
网络流中的核心问题:最大流量
码头a
b
c
炼油厂z
e
d
5,3
3,2
2,2
4,2
2,2
4,3
2,1
超级源、汇
w1
b
A
B
d
3
6
4
c
4
3
2
3
w2
w3
2
w1
b
A
B
d
3
6
4
c
4
3
2
3
a
w3
w2
z
∞
∞
∞
∞
∞
使用网络流表示问题
P458:
P459:习题1~7
最大流算法
传输网络G的一个最大流量是具有最大值的流量,最大流可能存在多个;
基本思想:从初始流量开始,反复增加,直至不能再增大。
通路
p= (v0, v1, …, vn),v0=a,vn=z 是从a到z的一条通路;
如果在p中边e是从 vi-1 指向 vi 则称是定向的,否则称是非定向的

离散数学－网络模型来自淘豆网www.taodocs.com转载请标明出处.

离散数学－网络模型.ppt

2005计科04－1班离散数学试题B卷

2005计科04－1班离散数学试题A卷

2005计科04－1班离散数学试题AB卷答案

离散数学第一章命题逻辑基本概念

离散数学第六章集合代数

数学建模第1章建立数学模型

网络项目--离散数学

2012MBA数学MPA数学MPAcc数学-初数数学公式大全

第三章离散控制系统的数学模型

数学模型与数学建模