网络分析_科院经典.pptVIP

例、 求 到 最短路 用值迭代公式 表示至多经过 个中间点到达 的最短路 满足权值非负条件： 直接用值迭代法计算 停止 非负权值带来的一个有利结果： 理由： （ ） Dijkstra算法利用上述结果对值迭代法进行如下修改： 1）每次迭代后固定最小的最优函数值 2）每次迭代只利用刚固定函数值的点修改相邻的点 每步迭代后最小的最优函数值不再发生变化 用Dijkstra算法计算 不变 不变 修改 修改 修改 修改 不变 修改 修改 不变 修改 修改 不变 修改 修改 不变 修改 修改 不变 修改 不变 网络分析 基础知识 最大流 最小费用流（含运输问题） 指派问题（二分图对集问题） 主要内容 基础知识 图 点集 例 边集 图 丁 甲 乙 丙 戊 D A B C 乙 戊 丁 丙 甲 D A B C 乙 戊 丁 丙 甲 D A B C 无向图 乙 戊 丁 丙 甲 D A B C 有向图 始点 A 甲 甲 终点 简单图 不含自回路和多重边 自回路 多重边 所有点可分为两个子集， 各边端点分属两个子集 二分图 完全图 每对点都有一条边相连 子图 对于图 ，如果 是 的子集， 是 的子集，并且 中每条边的端点都属于 ，则 称 是 的子图，如果 ，则称 是 的支撑子图 子图 支撑子图 图 网络（赋权图） 每边赋有权（实数）的图称为网络，记为 ， 其中 是权的集合 例、 某物资供应站 与用户之间的公路网络 上图是无向网络，如果通过管道输送输油或气 体，每个边有方向，构成有向网络 链（路） 点、边交替（可重复）的序列，如 初等链 无重复点边的链 圈（初等圈） 始点和终点为同一点的链（初等链） 道路（回路） 有向图中各边方向相同的链（圈） 连通图 任何两点间有链相连的图 边割 对于图 ，任取 ，其补集为 ，若 和 都不是空集，称两个端点分属 和 的边 的集合为 的一个边割，记为 割集 不含更小边割的边割称为割集 是割集， 是边割不是割集， 是割边 例 割边 满足割集定义的边 树 1） 连通且无圈 2） 无圈且有 条边 3） 连通且有 条边 4） 连通且每条边都是割边 5） 的任意两点都有唯一的链连接 6） 无圈，但任意加上一个新边就构成唯一的圈 设 ，顶点个数 ，如果下述任何一条满足， 就是一个树（定理6.3.1，195页） 图的支撑树 如果 的支撑子图 是树，称其为 的支撑树， 中属于 支撑树的边称为树枝，不属于支撑树的 边称为弦 命题6.3.3 图 有支撑树的充要条件是 是 连通图 必要性是显然的，充分性的证明等价于对任意的连 通图给出确定支撑树的算法 确定支撑树的方法 1）深探法 从任意点开始，边标号边前进，只至标完所有点 支撑树 2）广探法 从任意点开始，把当前标号点附近标号完再前进 支撑树 网络 的任意一个支撑树 的所有树枝 上的权的总和，记为 ，称为这个支撑树的权， 具有最小权的支撑树称为最小支撑树，简称最小树 最小支撑树 求最小支撑树的Kruskal算法（避圈法） 将所有边按权值从小到大排序，从权值最小 的边开始选树枝，如果可能形成圈则跳过， 直至选够顶点数减1的树枝 例 所有边从小到大排列 从小到大顺序选择不构成圈的边形成右上支撑树 性质：加入任何弦形成的圈中，弦的权值最大 定理6.4.1（199页） T是最小支撑树的充要条件是：加 入任何弦形成的圈中，弦的权值最大 Kruskal算法产生的是最小支撑树 证明必要性： 等价于证明所有满足条件的支撑树有相同的总权值 证明充分性： 如果加入某个弦形