1、Chapter11 图与网络分析图与网络分析( Graph Theory and Network Analysis )图与网络的基本概念与模型最短路问题最小生成树问题最大流问题最小费用最大流问题本章主要内容：本章主要内容：图与网络的基本概念与模型图与网络的基本概念与模型长 江汉江武昌武昌汉口汉口汉阳汉阳您能从武汉理工大学出发走过每座桥且只走一次然后回到学校吗 ?近代图论的历史可追溯到 18世纪的七桥问题 穿过 Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的 “哥尼斯堡 7 桥 ”难题。 Euler1736年证明了不可能存在这样的路线。图与网络的基本概念与模型图与网
2、络的基本概念与模型Knigsberg桥对应的图桥对应的图图与网络的基本概念与模型图与网络的基本概念与模型 图论中图是由点和边构成，可以反映一些对象之间的关系。 一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义图的定义 (P230)若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：其中 : V 点集 E 边集 图 G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。图与网络的基本概念与模型图与网络的基本概念与模型(v1)赵(v2)钱 孙 (v3) 李(v4)周 (v5) 吴 (v6) 陈 (
3、v7)e2e1 e3 e4 e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1 e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。1 图与网络的基本概念 图与网络的基本概念6a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图 11-3如果我们把上面例子中的 “ 相互认识 ” 关系改为 “ 认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入 一个带箭头的联线，称为弧 。图 11-3就
4、是一个反映这七人 “ 认识 ” 关系的图。相互认识用两条反向的弧表示。图与网络的基本概念与模型图与网络的基本概念与模型 定义 : 图中的点用 v表示，边用 e表示。对每条边可用它所连接的点表示，记作： e1=v1,v1; e2=v1,v2; v3e7e4e8e5e6e1e2 e3v1v2v4 v5端点端点 ,关联边关联边 ,相邻相邻若有边 e可表示为 e=vi,vj，称 vi和 vj是边 e的 端点 ，反之称边 e为点 vi或 vj的 关联边 。若点 vi、 vj与同一条边关联，称点 vi和 vj相邻；若边 ei和 ej具有公共的端点，称边 ei和 ej相邻 。图与网络的基本概念与模型图与网络
5、的基本概念与模型环环 , 多重边多重边 , 简单图简单图如果边 e的两个端点相重，称该边为环 。如右图中边 e1为环。如果两个点之间多于一条，称为 多重边 ，如右图中的 e4和 e5，对无环、无多重边的图称作 简单图 。v3e7e4e8e5e6e1e2 e3v1v2v4 v5图与网络的基本概念与模型图与网络的基本概念与模型链，圈，连通图链，圈，连通图 (P231)图中某些点和边的交替序列，若其中各边互不相同，且对任意 Vi-1,Vi 和 vi+1均相邻称为 链 。用 表示： v3e7e4e8e5e6e1e2 e3v1v2v4 v5起点与终点重合的链称作 圈 。如果每一对顶点之间至少存在一条链，称这样的图为 连通图 ，否则称 图不连通 。图与网络的基本概念与模型图与网络的基本概念与模型网络（赋权图网络（赋权图 ） (P232)设图 G（ V， E），对 G的每一条边 (vi,vj)相应赋予数量指标wij， wij称为边 (vi,vj)的权 ,赋予权的图 G称为 网络 (或赋权图）。权 可以代表距离、费用、通过能力 (容量 )等等。端点无序的赋权图称为 无向网络 ，端点有序的赋权图称为 有向网络。 91020157 1419256
