第七章图与网络分析 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: 球队比赛图 点: 表示研究对象. 连线：表示两个对象之间的某种特定关 系。 关系的对称性：两对象之间的关系可互 换