3、选址问题 已知一个地区的交通网络如下图所示,其中点代表 居民小区,边表示公路,问区中心医院应建在哪个 小区,可使离医院最远的小区居民就诊时所走的路 程最近? 即求图的中心 30 20 15 结论:把医院建在v,可使离医院最远的小区居民就 诊时所走的路程最近
已知一个地区的交通网络如下图所示，其中点代表 居民小区，边表示公路，问区中心医院应建在哪个 小区，可使离医院最远的小区居民就诊时所走的路 程最近？ 结论：把医院建在v6，可使离医院最远的小区居民就 诊时所走的路程最近 即求图的中心 3、选址问题 • • • •1 v 2 v 3 v 4 v 5 v 6 v • 60 • 30 15 18 25 15 20 • 7 v 20 30
旅客流、车流、货物流 4、网络流问题: 例:在一个输油管道网中,ν为起点,v,为终点 v为中转站(i=1,2,…,k边上的数表示该 管道的最大输油量,问应如何安排,才能 使从ν到ν,的总运输量最大? 最大 流问 题
例：在一个输油管道网中， vs 为起点， 为终点, t v 使从 到 的总运输量最大？ 管道的最大输油量，问应如何安排，才能 为中转站（ 边上的数表示该 s t i v v v i = 1,2,, k), 最大 流问 题 4、网络流问题： 旅客流、车流、货物流 • • • • 1 v 2 v 3 v 4 v 5 v 6 v • • 2 6 1 7 3 2 • t v 2 4 • s v 2 1 5 3 4 4
5.1基本概念 、图的概念 图 由若千个点和连接这些点的某些连 线所组成的图形/代表具 G一个图 体事物 代表事物 之间的联 v—图中的点,称为顶点 系 e图中的连线,称为边。ek=() 记V={V},E={e1}, G=(V, E m(G)=EG的边数,简记为m G n(G)=VG的顶点数,简记为n m=6.n=5
------由若干个点和连接这些点的某些连 线所组成的图形 vi——图中的点，称为顶点。 ei——图中的连线，称为边。 m(G)=|E|——G的边数，简记为m n(G)= |V|——G的顶点数，简记为n 一、图的概念 记V={vi}，E= {ei}, G=（V，E） 图 G——一个图 代表具 体事物 代表事物 之间的联 系 G 1 v 2 v 3 v 4 v 5 e1 v 2 e 3 e 4 e 5 • e • • • • 6 e m=6, n=5 ( ) k i j e v v = , ( ) 3 5 = v ,v 5.1 基本概念
有向图—边e=(v1v1)有方向 v为始点,v;为终点 图 此时(vv;)≠(v1,v;) 无向图—边e=(v,v)无方向 此时(v,vy)=(v,v2) 无 有 向 向 图 图 )≠(v V3)≠(v3
图 有向图 无向图 ——边e=（vi , vj）有方向 ——边e=（vi , vj）无方向 此时（vi , vj）= （vj , vi） e4 =（ v3， v4） ≠（ v4， v3） e4 =（ v3， v4）=（ v4， v3） e5 =（ v3， v4）=（ v4， v3） 此时（vi , vj）≠ （vj ,vi） vi为始点，vj为终点 • • • • 1 v 2 v 3 v 4 v 1 e 2 e 3 e 4 e 5 e 6 e • • • • 1 v 2 v 3 v 4 v 1 e 2 e 3 e 4 e 5 e 6 e 有 向 图 无 向 图 e5 =（ v4， v3）≠（ v3， v4）