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

第六章 图与网络分析 图 与 网 络 分 析（1） 图 与 网 络 分 析（1续） 端点的次d(v)：点 v 作为边端点的次数； 奇点：d(v)=奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1；悬挂边：与悬挂点连接的边 孤立点：d(v)=0；空图：E = ?，无边图。 定理一：所有顶点次数之和等于所有边数的2倍。 5、图 与 网 络 分 析（1续） 图的连通性： 链：由两两相邻的点及其相关联的边构成的点边序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , … , vn-1 , en , vn ； v0 , vn分别为链的起点和终点 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同，也称通路； 回路：若 v0 ≠ vn ,称该链为开链，否则称为闭链或回路； 圈：除起点和终点外链中所含的点均不相同的闭链； 连通图：图中任意两点之间均至少有一条通路，否则称作不连通图。 5、图 与 网 络 分 析（5.1续） 子图 设 G1 = [ V1 , E1 ] , G2 = [ V2 , E2 ] 子图定义：如果 V2 ? V1 , E2 ? E1 称 G2 是 G1 的子图； 真子图：如果 V2 ? V1 , E2 ? E1 称 G2 是 G1 的真子图； 部分图：如果 V2 = V1 , E2 ? E1 称 G2 是 G1 的部分图； 5、图 与 网 络 分 析（5.1续） 有向图：关联边有方向 弧：有向图的边 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、连通，但若去一边则图不连通； 6、每对顶点之间有且仅有一条链。 部分树：若一个图 G 的部分图 T 是树，则称 T 为部分树，又称生成树 5、图 与 网 络 分 析（5.3） 5. 3 最短树问题（最小树问题） 依据树的特点（即无圈和连通），按照最短的要求构造求最短树的方法。 结合例题学习、掌握求最小树的破圈法和生长法两个方法： 1、破圈法 ① 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树； ② 去掉该圈中权数最大的边； 反复重复 ① ② 两步，直到求出最短树。 2、生长法 从网络图中任意节点开始寻找与该节点关联的权数最小的边，得到另一节点后，再从这个新节点开始寻找与该节点关联的权数最小的另一边……。注意寻找过程中，节点不得重复，即在找最小权数边时不考虑已选过的边。反复进行，直到得到最短树或证明网络不存在最短树。 5、图 与 网 络 分 析（5.2） 5. 2 网络最短路问题 网络：规定起点、中间点和终点的赋权图； 有向网络：网络中每个边都是有向边； 无向网络：网络中每个边都是无向边； 网络最短路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。 Min L(?) = ? lij ?为从 v1 到 vn 的通路； lij?? 其中， lij为从 vi 到 vj 的一步距离。 5、图 与 网 络 分 析（5.2续） 结合例题学习、掌握求最短路的狄克斯拉、海斯和福德三个方法： 1、狄克斯拉方法：适用于满足所有权系数大于等于0（lij≥0）的网络最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离； 2、海斯方法：基本思想是在最短路线上任意两点间路线也是最短路线。利用 vi 到 vj 的一步距离求出 vi 到 vj 的两步距离再求出 vi 到 vj 的四步距离……经有限次迭代可求出 vi 到 vj 的最短距离； 3、福德方法：适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离。 5、图 与 网 络 分 析（5.4） 5. 4 最大流问题（ p201--212 ） 网络最大流问题