图与网路分析报告探讨(ppt 45页)
所属分类:经营管理
文件大小:931 KB
下载要求:10 学币或VIP
点击下载图与网路分析报告探讨目录:
1、图与网路的基本概念
2、树图与最小生成树
3、最短路问题
4、网路的最大流和最小截
5、欧拉回路和中国邮递员问题
6、哈密尔顿回路及旅行推销员问题
7、选址问题
图与网路分析报告探讨内容提要:
树图与最小生成树
一般研究无向图
树图:倒置的树,根(root)在上,树叶(leaf)在下
多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图
1 树的定义及其性质
任两点之间有且只有一条路径的图称为树(tree),记为T
树的性质:
最少边的连通子图,树中必不存在回路
任何树必存在次数为 1 的点
具有 n 个节点的树 T 的边恰好为 n1 条,反之,任何有n 个节点, n1 条边的连通图必是一棵树
2 图的生成树
树 T 是连通图 G 的生成树(spanning tree),若 T 是 G的子图且包含图 G 的所有的节点;包含图 G 中部分指定节点的树称为 steiner tree
每个节点有唯一标号的图称为标记图,标记图的生成树称为标记树(labeled tree)
Caylay 定理:n (2)个节点,有nn2个不同的标记树
2 图的生成树
如何找到一棵生成树
– 深探法(depth first search):任选一点标记为 0 点开始搜索,选一条未标记的边走到下一点,该点标记为 1,将走过的边标记;假设已标记到 i 点,总是从最新标记的点向下搜索,若从 i 点无法向下标记,即与 i 点相关联的边都已标记或相邻节点都已标记,则退回到 i 1 点继续搜索,直到所有点都被标记
– 广探法(breadth first search):是一种有层级结构的搜索,一般得到的是树形图
3 最小生成树
有n 个乡村,各村间道路的长度是已知的,如何敷设光缆线路使 n 个乡村连通且总长度最短
显然,这要求在已知边长度的网路图中找最小生成树
最小生成树的算法:
Kruskal 算法:将图中所有边按权值从小到大排列,依次选所剩最小的边加入边集 T,只要不和前面加入的边构成回路,直到 T 中有 n1 条边,则 T 是最小生成树
Kruskal 算法基于下述定理
定理 3 指定图中任一点vi,如果 vj 是距 vi 最近的相邻节点,则关联边 eij 必在某个最小生成树中。
推论 将网路中的节点划分为两个不相交的集合V1和V2,V2=VV1,则V1和V2间权值最小的边必定在某个最小生成树中。
精品资料网 m.cnshu.cn
Copyright © 2004- 粤ICP备10098620号-1
风险管理 应急预案 研发管理 运营管理 内部管理 商业模式 执行力 连锁经营 公司治理 工厂管理 创新管理 家族企业 效率管理 名企案例 企业理念 价值管理 特许经营 瓶颈管理 调查问卷 策划方案 领导力 团队建设 企业变革 企业文化 战略管理 竞争策略 管理知识 危机管理 成本管理 项目管理 发展战略 年度计划 决策管理 企业上市 供应商 组织设计 产品管理 采购管理 品牌管理 企业诊断 企业咨询 商务谈判 物流管理 运作管理 管理制度 行业报告 经营管理 企划方案 MBA 流程管理 目标管理 招标投标 商务礼仪 管理表格 管理技能 管理案例 管理工具 管理手册 职业经理人 商业计划书 董事与股东 可行性报告