第七章图与网络分析 1图的 今 2树 3最短路 4最大流问题 5最小费用最大流 6中国邮递员问题 合
第七章 图与网络分析 1.图的基本概念 2.树 3.最短路 4.最大流问题 5.最小费用最大流 6.中国邮递员问题
图与网络分析 问题提出 应用:生产组织,邮递员问题,通讯 网络等。 哥尼斯堡七桥问题
运筹学 图与网络分析 问题提出 应用：生产组织，邮递员问题，通讯 网络等。 哥尼斯堡七桥问题
哥尼斯堡七桥问题 在图中找一条经过每边一次且仅一次 的路\欧拉回路。 A 由点和边组成 BX D D B
运筹学 A B C D 哥尼斯堡七桥问题 在图中找一条经过每边一次且仅一次 的路——欧拉回路。 A D B C 由点和边组成
环球旅行”问题 在图中找一条经过每个点一次且仅 次的路哈密尔顿回路。 中国邮路问题” 在图中找一条经过每边的最短路 类似带权的欧拉回路。 “货郎担问题 在图中找一条经过每个点一次且仅一次 的最短路带权的哈密尔顿回路。國
运筹学 “环球旅行”问题 在图中找一条经过每个点一次且仅 一次的路——哈密尔顿回路。 “中国邮路问题” 在图中找一条经过每边的最短路— —类似带权的欧拉回路。 “货郎担问题” 在图中找一条经过每个点一次且仅一次 的最短路——带权的哈密尔顿回路
1图的基本概念 例1:铁路交通图 例2:球队比赛图 点:表示研究对象 连线:表示两个对象之间的某种特定关 系 关系的对称性:两对象之间的关系可互 换 □合
运筹学 1.图的基本概念 例 1: 铁路交通图 例 2: 球队比赛图 点: 表示研究对象. 连线：表示两个对象之间的某种特定关 系。 关系的对称性：两对象之间的关系可互 换
边:不带箭头的联线,表示对称关系。 弧:带箭头的联线,表示不对称关系。 无向图:简称图,有点和边组成。 表示为:G=(V,E) V-点集合E-边集合 例:右图 V={v1,v2,v3,V4 E={el,e2,,e7} el=lvl, v2]e2=vl, v2I ,e7=v4,v4] 脑O2
运筹学 边：不带箭头的联线，表示对称关系。 弧：带箭头的联线，表示不对称关系。 无向图：简称图，有点和边组成。 表示为： 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=(VA V-点集合A-孤集合 点数p(G)或p(D) 边数:q(G) 弧数:q(D) VI v4 例:右图 V={vl,v22,V5} v3 Afal, a2,..., a7) al={v1,v5},a2={v5,V4}2a7={vl,v4
运筹学 有向图：由点和弧组成。表示为： D=（V，A） V--点集合 A--弧集合 点数: p(G) 或 p(D) 边数: q(G) 弧数:q(D) v1 v2 v3 v4 v5 例：右图 V={v1，v2,…,v5} A={a1，a2,…,a7} a1={v1,v5},a2={v5,v4},…,a7={v1,v4}
无向图的有关概念 端点:e=[uv∈E则uV是e的端点称 uv相邻 关联边:e是点uv的关联边 环:若u=ve是环 多重边:两点之间多于一条边 简单图:无环无多重边的图 多重图:无环允许有多重边的图 □合
运筹学 无向图的有关概念 端点: e=[u,v]∈E, 则u,v是e的端点, 称 u,v相邻. 关联边: e是点u,v的关联边. 环: 若u=v, e是环. 多重边: 两点之间多于一条边. 简单图: 无环,无多重边的图. 多重图: 无环,允许有多重边的图
次:以点v为端点的边的个数称为v的次 表示为:dv) 悬挂点次为1的点 悬挂边:悬挂点的关联边 孤立点:次为0的点 奇点次为奇数的点 偶点:次为偶数的点 悬挂边 d(v)=4,d(v2)=3 孤立点
运筹学 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 v5 次: 以点v为端点的边的个数称为v的次. 表示为: d(v) 悬挂点: 次为1的点. 悬挂边: 悬挂点的关联边. 孤立点: 次为0的点. 奇点: 次为奇数的点. 偶点: 次为偶数的点. 孤立点 悬挂边 d(v1 ) = 4,d(v2 ) = 3
定理1:图G=(V,E)中所有点的次之和是 边数的两倍,即 ∑d()=2q v∈ 定理2:任意一图中,奇点的个数为偶数 证明;设v1-奇点的集合, V2-偶点的集合 ∑d()+∑4(v)=∑d()=2q v∈I v∈2 v∈ 偶数 偶数 偶数
运筹学 定理1: 图G=(V,E)中,所有点的次之和是 边数的两倍, 即: 定理2: 任意一图中, 奇点的个数为偶数. 证明:设 V1--奇点的集合, V2--偶点的集合 d v q v V ( ) = 2 d v d v d v q v V v V v V ( ) ( ) ( ) 2 1 2 + = = 偶数 偶数 偶数