第七章图与网络优化0.问题的提出1.图的基本概念2.树3.最短路问题4.网络最大流问题5.最小费用最大流问题6.中国邮递员问题
第七章 图与网络优化 0.问题的提出 1.图的基本概念 2.树 3.最短路问题 4.网络最大流问题 5.最小费用最大流问题 6.中国邮递员问题
O问题的提出图与网络问题是运筹学中一个有广泛应用的分支;关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在1736年发表的解决“哥尼斯堡(Konisberg)"七桥难题的论文;哥尼斯堡的一条河上七座桥接河中的两个小岛，人们如何才能只走过每座桥一次后达到原出发地
图与网络问题是运筹学中一个有广泛应用 的分支； 关于图的第一篇论文是瑞士数学家欧拉（ E.Euler）在1736年发表的解决“哥尼斯堡 (Konisberg)”七桥难题的论文； 哥尼斯堡的一条河上七座桥连接河中的两 个小岛，人们如何才能只走过每座桥一次 后达到原出发地。 0 问题的提出
哥尼斯堡(Konisberg)七桥问题-在图中找一条经过每边一次且仅一艺欧拉回路。一由点和边组成DDB-AB
D C B A 哥尼斯堡(Konisberg)七桥问题 -在图中找一条经过每边一次且仅一 次的路——欧拉回路。 D A B C 由点和边组成
一笔画问题下图1从A出发经过每条边一次且仅一次回到A点？下图2从A到B能否经过每条边一次且仅一次？BBAA图2图1
一笔画问题 图1 图2 A B A B 下图2从A到B能否经过每 条边一次且仅一次？ 下图1从A出发经过每条边 一次且仅一次回到A点？
欧拉链与欧拉圈若在连通图G中存在一条链（或一个圈）通过每条边一次且仅一次，则称这条链（或圈）为欧拉链（或欧拉圈）欧拉定理连通图G中存在欧拉圈的充分必要条件是G的每个顶点都是偶顶点：G中存在欧拉链充分必要条件是G中正好有两个奇顶点。福B
欧拉链与欧拉圈 若在连通图G中存在一条链（或一个圈）通过每条边一次 且仅一次，则称这条链（或圈）为欧拉链（或欧拉圈） 欧拉定理 连通图G中存在欧拉圈的充分必要条件是G的每个顶点都 是偶顶点；G中存在欧拉链充分必要条件是G中正好有两 个奇顶点。 D A B C
1.图的基本概念例1：铁路交通图例2：球队比赛图点：表示研究对象连线：表示两个对象之间的某种特定关系。关系的对称性：两对象之间的关系可互换
1.图的基本概念 例 1: 铁路交通图 例 2: 球队比赛图 点: 表示研究对象. 连线：表示两个对象之间的某种特定关系。 关系的对称性：两对象之间的关系可互换
边：不带箭头的联线，表示对称关系。弧：带箭头的联线，表示不对称关系。无向图：简称图，由点和边组成。表示为：G=（V，E)eV一点集合E一边集合ViV2eo例：右图e6V={Vi, V2, V3, V4]ese3E={ej, e2, ...,ef]Vee1=[V1,V2] e2=[Vi, V2],23en..,e,=[v4, 4]
边：不带箭头的联线，表示对称关系。 弧：带箭头的联线，表示不对称关系。 无向图：简称图，由点和边组成。 表示为： G=（V，E） V—点集合 E—边集合 例：右图 V={v1 ，v2 ，v3 ，v4 } E={e1 ，e2 ，.,e7 } e1 =[v1 ,v2 ] e2 =[v1 ,v2 ], .,e7 =[v4 ,v4 ] v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7
有向图：由点和弧组成。表示为D= (V, A)其中：V--点集合A--弧集合点数: p(G)或 p(D)边数: q(G)V弧数: q(D)例：右图V=-{Vi, V2...,Vs]1A=a1. a2....a7]ai={V1,Vs], a2={Vs,V4],..., a,={V1,V4]
例：右图 V={v1，v2 ,.,v5 } A={a1，a2 ,.,a7 } a1={v1 ,v5 }, a2={v5 ,v4 },., a7={v1 ,v4 } 有向图：由点和弧组成。表示为： D =（V，A） 其中：V-点集合 A-弧集合 点数: p(G) 或 p(D) 边数: q(G) 弧数: q(D) v1 v2 v3 v4 v5
无向图的有关概念端点：e=[u,]eE,则u,v是e的端点,称u,vV相邻。关联边：e是点u,v的关联边环：若u=v,e是环多重边：两点之间多于一条边简单图：无环无多重边的图多重图：无环允许有多重边的图
无向图的有关概念 端点: e=[u,v] E, 则u,v是e的端点, 称u,v 相邻. 关联边: e是点u,v的关联边. 环: 若u=v, e是环. 多重边: 两点之间多于一条边. 简单图: 无环,无多重边的图. 多重图: 无环,允许有多重边的图
次：以点v为端点的边的个数称为v的次表示为: d(v)悬挂点：次为1的点。悬挂边：悬挂点的关联边孤立点：次为0的点。e奇点：次为奇数的点悬挂边偶点：次为偶数的点VV4d(v) = 4,d(v2) = 3e6V孤立点e5V
v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 v5 次: 以点v为端点的边的个数称为v的次. 表示为: d(v) 悬挂点: 次为1的点. 悬挂边: 悬挂点的关联边. 孤立点: 次为0的点. 奇点: 次为奇数的点. 偶点: 次为偶数的点. 孤立点 悬挂边 d(v ) 4,d(v ) 3 1 2