Chapter6图与网络分析 Graph Theory and Network Analysis 本章主要内容： ·图的基本概念与模型 ●树与图的最小树 ·最短路问题 ●网络的最大流
Chapter6 图与网络分析 ( Graph Theory and Network Analysis ) 图的基本概念与模型 树与图的最小树 最短路问题 网络的最大流 本章主要内容：
图的基本概念与模型 Page 2 汉 汉阳 汉口 江 长 江 您能从武汉理工大学出发走过 每座桥且只走一次然后回到学 武昌 校吗？
图的基本概念与模型 Page 2 长 江 汉 江 武昌 汉阳 汉口 您能从武汉理工大学出发走过 每座桥且只走一次然后回到学 校吗?
图的基本概念与模型 Page 3 近代图论的历史可追溯到18世纪的七桥问题一穿过 KOnigsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不 可能存在这样的路线。 K6 nigsberg桥对应的图
Page 3 近代图论的历史可追溯到18世纪的七桥问题—穿过 Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡7 桥”难题。Euler1736年证明了不 可能存在这样的路线。 图的基本概念与模型 Königsberg桥对应的图
图的基本概念与模型 Page 4 图论中图是由点和边构成，可以反映一些对象之间的关系。 一般情况下图中点的相对位置如何、点与点之间联线的长短 曲直，对于反映对象之间的关系并不是重要的。 图的定义： 若用点表示研究的对象，用边表示这些对象之间的联系， 则图G可以定义为点和边的集合，记作： G=V,E 其中：V一点集E一边集 ※图G区别于几何学中的图。这里只关心图中有多少个点以 及哪些点之间有连线
图的基本概念与模型 Page 4 图论中图是由点和边构成，可以反映一些对象之间的关系。 一般情况下图中点的相对位置如何、点与点之间联线的长短 曲直，对于反映对象之间的关系并不是重要的。 图的定义： 若用点表示研究的对象，用边表示这些对象之间的联系， 则图G可以定义为点和边的集合，记作： G = {V,E} 其中: V——点集 E——边集 ※ 图G区别于几何学中的图。这里只关心图中有多少个点以 及哪些点之间有连线
图的基本概念与模型 Page 5 例如：在一个人群中，对相互认识这个关系我们可以用图来 表示。 (3)孙 赵 s)· 周 ()陈 e; g () v2)钱 李 (6)吴 e e3 e es 赵 (V2)钱孙(W3)李W4) 周v) 吴w)陈(v) 可见图论中的图与几何图、工程图是不一样的
图的基本概念与模型 Page 5 (v1 ) 赵 (v2 )钱 孙(v3 ) 李(v4 ) 周(v5 ) 吴(v6 ) 陈(v7 ) e2 e1 e3 e4 e5 (v1 ) 赵 (v2 )钱 (v3 )孙 (v4 ) 李 (v5 ) 周 (v6 )吴 (v7 )陈 e2 e1 e3 e4 e5 可见图论中的图与几何图、工程图是不一样的。 例如：在一个人群中，对相互认识这个关系我们可以用图来 表示