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 可见图论中的图与几何图、工程图是不一样的。 例如：在一个人群中，对相互认识这个关系我们可以用图来 表示
图的基本概念与模型 Page 6 定义：图中的点用v表示，边用表示。对每条边可用它所连 接的点表示，记作：ev1,V1e2v1,V2; ◇端点，关联边，相邻 若有边e可表示为e=[y,以，称v,和y 是边e的端点，反之称边e为点v,或y es 的关联边。若点yy,与同一条边关 e6 联，称点y和v相邻；若边e,和e,具 有公共的端点，称边e,和e相邻
图的基本概念与模型 Page 6 定义: 图中的点用v表示，边用e表示。对每条边可用它所连 接的点表示，记作：e1=[v1 ,v1 ]; e2=[v1 ,v2 ]; v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 端点,关联边,相邻 若有边e可表示为e=[vi ,vj ]，称vi和vj 是边e的端点，反之称边e为点vi或vj 的关联边。若点vi、vj与同一条边关 联，称点vi和vj相邻；若边ei和ej具 有公共的端点，称边ei和ej相邻
图的基本概念与模型 Page7 。环，多重边，简单图 如果边e的两个端点相重，称该边为 环。如右图中边e1为环。如果两个点 之间多于一条，称为多重边，如右图 中的e4和es,对无环、无多重边的图 称作简单图
图的基本概念与模型 Page 7 环, 多重边, 简单图 如果边e的两个端点相重，称该边为 环。如右图中边e1为环。如果两个点 之间多于一条，称为多重边，如右图 中的e4和e5，对无环、无多重边的图 称作简单图。 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5
图的基本概念与模型 Page 8 。次，奇点，偶点，孤立点 与某一个点v相关联的边的数目称为 点y的次（也叫做度），记作()。 右图中d(w1)=4,d(W3)=5,d(vs)=1。次 es 为奇数的点称作奇点，次为偶数的 es 点称作偶点，次为1的点称为悬挂点， 次为0的点称作孤立点。 图的次：一个图的次等于各点的次之和
图的基本概念与模型 Page 8 次，奇点，偶点，孤立点 与某一个点vi相关联的边的数目称为 点vi的次（也叫做度），记作d(vi )。 右图中d(v1 )＝４,d(v3 )=5,d(v5 )=1。次 为奇数的点称作奇点，次为偶数的 点称作偶点，次为1的点称为悬挂点， 次为0的点称作孤立点。 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 图的次: 一个图的次等于各点的次之和
图的基本概念与模型 Page9 。链，圈，连通图 图中某些点和边的交替序列，若其 中各边互不相同，且对任意v1和 v均相邻称为链。用μ表示： u=ivo2e,v,es,v es 起点与终点重合的链称作圈。如 果每一对顶点之间至少存在一条 链，称这样的图为连通图，否则 称图不连通
图的基本概念与模型 Page 9 链，圈，连通图 图中某些点和边的交替序列，若其 中各边互不相同，且对任意vi,t-1和 vit均相邻称为链。用μ表示： v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 { , , , , , } 0 1 1 k k = v e v e v 起点与终点重合的链称作圈。如 果每一对顶点之间至少存在一条 链，称这样的图为连通图，否则 称图不连通
图的基本概念与模型 Page 10 。二部图（偶图） 图G=(V,E)的点集V可以分为两各非空子集X,Y,集 XUY=V,X∩Y=O,使得同一集合中任意两个顶点均不 相邻，称这样的图为偶图。 V2 73 V4 V (a) (b) (a)明显为二部图，(b)也是二部图，但不明显，改画为(c) 时可以清楚看出
图的基本概念与模型 Page 10 二部图（偶图） 图G=(V,E)的点集V可以分为两各非空子集X，Y，集 X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不 相邻，称这样的图为偶图。 v1 v3 v5 v2 v4 v6 v1 v2 v3 v4 v1 v4 v2 v3 (a) (b) (c) (a)明显为二部图，(b)也是二部图，但不明显，改画为(c) 时可以清楚看出