图与网路分析报告探讨(ppt 45页)

图与网路分析报告探讨目录：
1、图与网路的基本概念
2、树图与最小生成树
3、最短路问题
4、网路的最大流和最小截
5、欧拉回路和中国邮递员问题
6、哈密尔顿回路及旅行推销员问题
7、选址问题

 

图与网路分析报告探讨内容提要：
树图与最小生成树
一般研究无向图
树图：倒置的树，根(root)在上，树叶(leaf)在下
多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图
1 树的定义及其性质
任两点之间有且只有一条路径的图称为树(tree)，记为T
     树的性质：
最少边的连通子图，树中必不存在回路
任何树必存在次数为 1 的点
具有 n 个节点的树 T 的边恰好为 n1 条，反之，任何有n 个节点， n1 条边的连通图必是一棵树
2  图的生成树
树 T 是连通图 G 的生成树(spanning tree)，若 T 是 G的子图且包含图 G 的所有的节点；包含图 G 中部分指定节点的树称为 steiner tree
每个节点有唯一标号的图称为标记图，标记图的生成树称为标记树(labeled tree)
Caylay 定理：n (2)个节点，有nn2个不同的标记树
2 图的生成树
如何找到一棵生成树
– 深探法(depth first search)：任选一点标记为 0 点开始搜索，选一条未标记的边走到下一点，该点标记为 1，将走过的边标记；假设已标记到 i 点，总是从最新标记的点向下搜索，若从 i 点无法向下标记，即与 i 点相关联的边都已标记或相邻节点都已标记，则退回到 i 1 点继续搜索，直到所有点都被标记
– 广探法(breadth first search)：是一种有层级结构的搜索，一般得到的是树形图
3 最小生成树
有n 个乡村，各村间道路的长度是已知的，如何敷设光缆线路使 n 个乡村连通且总长度最短
显然，这要求在已知边长度的网路图中找最小生成树
     最小生成树的算法：
Kruskal 算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集 T，只要不和前面加入的边构成回路，直到 T 中有 n1 条边，则 T 是最小生成树
Kruskal 算法基于下述定理
定理 3  指定图中任一点vi，如果 vj 是距 vi 最近的相邻节点，则关联边 eij 必在某个最小生成树中。
推论   将网路中的节点划分为两个不相交的集合V1和V2，V2=VV1，则V1和V2间权值最小的边必定在某个最小生成树中。

..............................