管理运筹学 第九章图与网络模型
管理运筹学 第九章 图与网络模型
本章内容 图与网络的基本概念 2 最短路问题 3 最小生成树问题 最大流问题 最小费用最大流问题
1 图与网络的基本概念 2 最短路问题 3 5 4 最小生成树问题 最大流问题 最小费用最大流问题 本章内容
§1 图与网络的基本概念 图论中图是由点和边构成，可以反映一些对象之间的关 系。例如：一个人群中，相互认识关系可以用图表示，如 图9-1所示。 赵(w e2 孙(3) 周(Ns) e e e3 ·李(v 钱(v) ·吴(v6) es 陈(v7) 图9-1
图论中图是由点和边构成，可以反映一些对象之间的关 系。例如：一个人群中，相互认识关系可以用图表示，如 图9-1 所示。 11.1 图与网络的基本概念 图 9-1 § 1
§1 图与网络的基本概念 图论不仅描述对象之间关系，还研究特定关系之间的内在规律，一般 情况下图中点的相对位置如何、点与点之间连线的长短曲直，对于反映对 象之间的关系并不重要，如对赵等七人的相互认识关系可用图9-2表示， 可见图论的图与几何图、工程图是不一样的。 e e, es ● 赵)钱(2)孙)李(4) 周) 吴() 陈v) 图9-2
11.1 图与网络的基本概念 图 9-2 § 1 图论不仅描述对象之间关系，还研究特定关系之间的内在规律，一般 情况下图中点的相对位置如何、点与点之间连线的长短曲直，对于反映对 象之间的关系并不重要，如对赵等七人的相互认识关系可用图 9-2 表示， 可见图论的图与几何图、工程图是不一样的
§1 图与网络的基本概念 如果把上例中的“相互认识”关系改为“认识”关系，那么用两 点之间的连线很难刻画他们之间关系，这时引入一个带箭头的连线， 称为孤。图9-3就是一个反映这七人“认识”关系的图。相互认识 用两条反向的孤表示。 a 钱V a g (v) 李(V4) 赵 a a 孙(V) 陈(V) as a10 吴(N) N5) 图9-3
如果把上例中的“相互认识”关系改为“认识”关系，那么用两 点之间的连线很难刻画他们之间关系，这时引入一个带箭头的连线， 称为弧。图 9-3 就是一个反映这七人“认识”关系的图。相互认识 用两条反向的弧表示。 11.1 图与网络的基本概念 图 9-3 § 1