第五章图论筒介 创始人 E Euler(瑞士数学家) 创立时间 18世纪 问题的提 歌尼斯堡七桥难题
E.Euler（瑞士数学家） 18世纪 创始人 创立时间 问题的提 出 歌尼斯堡七桥难题
※歌尼斯堡七桥难题 普莱格尔河
※歌尼斯堡七桥难题 普莱格尔河
七桥问题的数学模型: 用A、B表示两座小岛,C、D表示两岸, 连线AB表示A、B之间有一座桥。 C A B 问题简化为: 在该图中,从任一点出发,能否通过每条线段 次且仅仅一次后又回到原来的出发点 结论:不存在这样一种走法
结论：不存在这样一种走法。 用A、B表示两座小岛，C、D表示两岸， 连线AB表示A、B之间有一座桥。 问题简化为： A • • B • C • D 在该图中，从任一点出发，能否通过每条线段 一次且仅仅一次后又回到原来的出发点 七桥问题的数学模型：
类似的问题:一笔画问题 图的一笔画:可一笔画 不可一笔画 凶 字的一笔画:如“中、日、口、串”等可一笔画 而:“田、目”等不能一笔画
类似的问题：一笔画问题 字的一笔画：如“中、日、口、串”等可一笔画 而：“田、目”等不能一笔画 图的一笔画： 可一笔画 不可一笔画
图论的应用范围: 1、中国邮路问题: 邮递员如何选择适当的投递路线,使每条街道至 少走过一次且所走的总路程最短 2、最短路问题: 个乡有9个自然村,其间道路如下图所示, 要以村为中心ν建有线广播网,如要求沿道路 架设广播线,应如何架设使所用电线最短
图论的应用范围： 1、中国邮路问题： 邮递员如何选择适当的投递路线，使每条街道至 少走过一次且所走的总路程最短？ 2、最短路问题： 一个乡有9个自然村，其间道路如下图所示， 要以村为中心 建有线广播网，如要求沿道路 架设广播线，应如何架设使所用电线最短 0 v • • • • • • • • • 0 v 4 1 1 5 2 4 4 3 1 2 3 5 5 1 4 2 1 • • • • • • • • • 0 v 1 2 1 2 3 1 2
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）