数据挖掘--图与网络分析

1、燕山大学经济管理学院燕山大学经济管理学院运筹学课程教学课题组编制运筹学课程教学课题组编制5. 1 图的基本概念 本节主要是概念本节主要是概念 图 G（V，E）： V是顶点集合（vi , i=16） E是边的集合（ej , j=19） 顶点数 p (G) = 6 边数 q (G) = 9 对于边 e3 = v1, v4 ，v1, v4是 e3的端点e3 是v1, v4的关联边图的其他概念图的其他概念 ： 相邻点，相邻边，相邻点，相邻边， 环，多重边（平行边），环，多重边（平行边）， 简单图简单图端点的次d(v)：点点 v 作为边端点的次数；作为边端点的次数；奇点：d(v)=奇数；奇数； 偶点：d

2、(v)=偶数；偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边与悬挂点连接的边孤立点：d(v)=0；空图：E = ，无边图无边图。定理一：所有顶点次数之和等于所有边数的2倍。图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列；如：由两两相邻的点及其相关联的边构成的点边序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn ； v0 , vn分别为链的分别为链的起点和和终点 简单链：链中所含的边均不相同；链中所含的边均不相同；初等链：链中所含的点均不相同，也称通链中所含的点均不相同，也称通路；回路：若若 v0 vn ,称该链

3、为开链，否则称为称该链为开链，否则称为闭链或或回路；圈：除起点和终点外链中所含的点均不相同的闭链；除起点和终点外链中所含的点均不相同的闭链；连通图：图中任意两点之间均至少有一条通路，否则称作不连：图中任意两点之间均至少有一条通路，否则称作不连通图。通图。子图 设 G1 = V1 , E1 , G2 = V2 , E2 子图定义：如果如果 V2 V1 , E2 E1 称称 G2 是是 G1 的子图；的子图；真子图：如果如果 V2 V1 , E2 E1 称称 G2 是是 G1 的真子图；的真子图；部分图：如果如果 V2 = V1 , E2 E1 称称 G2 是是 G1 的部分图；的部分图；有向图：

4、关联边有方向关联边有方向弧：有向图的边有向图的边 a = ( u , v )，起点 u，终点 v；路：若有从若有从 u 到到 v 不考虑方向的链，且各方向一致，则称之为从不考虑方向的链，且各方向一致，则称之为从 u 到到 v 的的路；回路：起点与重点重合的路； 连通图：每一对顶点之间至少存在一条链每一对顶点之间至少存在一条链5、图 与 网 络 分 析（5.1续） 树：无圈连通图无圈连通图定理：六种等价描述。六种等价描述。 设：边数设：边数 q , 顶点数顶点数 p . 1、无圈连通图；无圈连通图； 2、边数、边数q = 顶点数顶点数p - 1； 3、连通，且连通，且 q = p - 1； 4、

5、无圈，但加一边则得到唯一的圈；无圈，但加一边则得到唯一的圈； 5、连通，但若去一边则图不连通；、连通，但若去一边则图不连通； 6、每对顶点之间有且仅有一条链。、每对顶点之间有且仅有一条链。部分树：若一个图若一个图 G 的部分图的部分图 T 是树，则称是树，则称 T 为部为部分树，又称生成树分树，又称生成树5、图 与 网 络 分 析（5.1续） 5. 3 最短树问题（最小树问题）依据树的特点（即无圈和连通），按照最短的要求构造求最短依据树的特点（即无圈和连通），按照最短的要求构造求最短树的方法。树的方法。结合例题学习、掌握求最小树的破圈法和生长法两个方法：结合例题学习、掌握求最小树的破圈法和生长

6、法两个方法： 1、破圈法、破圈法 在网络图中寻找一个圈。若不存在圈，则已经得到最在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；短树或网络不存在最短树； 去掉该圈中权数最大的边；去掉该圈中权数最大的边； 反复重复反复重复 两步，直到求出最短树。两步，直到求出最短树。 2、生长法、生长法 从网络图中任意节点开始寻找与该节点关联的权数最小的从网络图中任意节点开始寻找与该节点关联的权数最小的边，得到另一节点后，再从这个新节点开始寻找与该节点关联边，得到另一节点后，再从这个新节点开始寻找与该节点关联的权数最小的另一边的权数最小的另一边。注意寻找过程中，节点不得重复，。注意寻找过程

7、中，节点不得重复，即在找最小权数边时不考虑已选过的边。反复进行，直到得到即在找最小权数边时不考虑已选过的边。反复进行，直到得到最短树或证明网络不存在最短树。最短树或证明网络不存在最短树。5、图 与 网 络 分 析（5.3） 5、图 与 网 络 分 析（5.2）5. 2 网络最短路问题 网络：规定起点、中间点和终点的赋权图；规定起点、中间点和终点的赋权图；有向网络：网络中每个边都是有向边；网络中每个边都是有向边；无向网络：网络中每个边都是无向边；网络中每个边都是无向边；网络最短路线问题：寻找网络中从起点寻找网络中从起点 v1 到终点到终点 vn 的最短路线。的最短路线。 Min L( ) = l

8、ij 为从为从 v1 到到 vn 的通路；的通路； lij 其中，其中， lij为从为从 vi 到到 vj 的一步距离。的一步距离。结合例题学习、掌握求最短路的狄克斯拉、海斯和结合例题学习、掌握求最短路的狄克斯拉、海斯和福德三个方法：福德三个方法： 1、狄克斯拉方法：适用于满足所有权系数大于等、狄克斯拉方法：适用于满足所有权系数大于等于于0（lij0）的网络最短路问题，能求出起点的网络最短路问题，能求出起点 v1 到所到所有其它点有其它点 vj 的最短距离；的最短距离； 2、海斯方法：基本思想是在最短路线上任意两点、海斯方法：基本思想是在最短路线上任意两点间路线也是最短路线。利用间路线也是最短

9、路线。利用 vi 到到 vj 的一步距离求出的一步距离求出 vi 到到 vj 的两步距离再求出的两步距离再求出 vi 到到 vj 的四步距离的四步距离经经有限次迭代可求出有限次迭代可求出 vi 到到 vj 的最短距离；的最短距离； 3、福德方法：适用于有负权系数，但无负回路的、福德方法：适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点有向或无向网络的最短路问题，能求出起点 v1 到所到所有其它点有其它点 vj 的最短距离。的最短距离。5、图 与 网 络 分 析（5.2续） 5. 4 最大流问题（ p201-212 ）网络最大流问题网络最大流问题 * 在一定条件下，要求流过网

10、络的物流、能量流或信息流等流量在一定条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题。为最大的问题。 * 规定：规定： 一个起点和一个终点；有向网络；各弧上有权表示允许一个起点和一个终点；有向网络；各弧上有权表示允许的最大流量；除起点和重点外，各节点流入量总和等于流出量总和。的最大流量；除起点和重点外，各节点流入量总和等于流出量总和。最大流最小割定理（在理解割集和最小割集概念的基础上掌握此定理）最大流最小割定理（在理解割集和最小割集概念的基础上掌握此定理） 最大流最小割定理：流过网络的最大流量等于最小割集的容量。最大流最小割定理：流过网络的最大流量等于最小割集的容量。结合例题学习、

11、掌握求最大流的福德结合例题学习、掌握求最大流的福德 富克逊方法富克逊方法 在理解算法原理的基础上，掌握算法思想及过程。通过例题掌握在理解算法原理的基础上，掌握算法思想及过程。通过例题掌握此方法。此方法。5、图 与 网 络 分 析（5.4） 最小费用最小费用 最大流问题最大流问题 本节讨论的问题是在本节讨论的问题是在5.4节问题的基础上增加关于使费用节问题的基础上增加关于使费用最小的目标。最小的目标。对偶法原理对偶法原理 用用5.4节讨论的方法求出网络的最大流量，然后在原始的网络节讨论的方法求出网络的最大流量，然后在原始的网络中用中用5.2.4的福德算法找出从起点的福德算法找出从起点 vs 到终点到终点 vt 的最短路线的最短路线最短增广链，在该增广链上找出最大调整量，并调整流量得最短增广链，在该增广链上找出最大调整量，并