第三章图与网络分析系统工程南京农业大学工学院 陈青春制作
南京农业大学工学院 陈青春 制作 系 统 工 程 第三章 图与网络分析
主要内容第三章图与网络分析图的基本概念s1一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树s2有向图s3图的矩阵表示S4最短路问题2s1图的基本概念
2 主要内容 §1 图的基本概念 §1 图的基本概念 第三章 图与网络分析 一、图、连通图、赋权图 二、一笔画问题 三、中国邮路问题 四、子图和树 §2 有向图 §4 最短路问题 §3 图的矩阵表示
S1图的基本概念s1图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树3、图、连通图、赋权图
3 §1 图的基本概念 一、图、连通图、赋权图 §1 图的基本概念 一、图、连通图、赋权图 二、一笔画问题 三、中国邮路问题 四、子图和树
概述S1图的基本概念概述生产实际中的许多问题虽然多属于不同领域，但其中相当一部分问题都可以(1）由来用图与网络的形式进行描述不仅本身具有重要的理论意义，更重要的是作为其它学科的公共基础而被广（2）意义泛应用物理学、控制论、信息论、交通运输、经济管理、计算机科学等（3）应用项目管理、通信线路的架设、输油管道的铺设、公路或铁路交通网络的合理（4）用例布局等4兰德公司简介
4 §1 图的基本概念 概述 兰德公司简介 概述 （1）由来 生产实际中的许多问题虽然多属于不同领域，但其中相当一部分问题都可以 用图与网络的形式进行描述 （2）意义 不仅本身具有重要的理论意义，更重要的是作为其它学科的公共基础而被广 泛应用 （3）应用 物理学、控制论、信息论、交通运输、经济管理、计算机科学等 （4）用例 项目管理、通信线路的架设、输油管道的铺设、公路或铁路交通网络的合理 布局等
S1图的基本概念图、连通图、赋权图1图一、图、连通图、赋权图1.图与以前在数学中学的几何图形不完全相同欧拉将此问题归结为一个“哥尼斯堡七桥问题：笔画问题，并证明了是不可能的，因为图中的每个点都与奇数条边相关联，不可能将这个图不重复地一笔画成，这是古典图论中一个著名问题38esete2eCDere3esBB图论中的图示意图5图论中的图与几何图形的区别
5 §1 图的基本概念 一、图、连通图、赋权图 1. 图 图论中的图与几何图形的区别 一、图、连通图、赋权图 1. 图 与以前在数学中学的几何图形不完全相同 哥尼斯堡七桥问题： A B C D 示意图 图论中的图 B C D e1 e2 e6 e5 e7 e3 e4 A 欧拉将此问题归结为一个 “一 笔画”问题，并证明了是不可 能的，因为图中的每个点都与 奇数条边相关联，不可能将这 个图不重复地一笔画成，这是 古典图论中一个著名问题