第六章网络分析 (一)目的与要求 1.理解图论中结点、边、链、弧、路径的概念 2.掌握最短路径的标号算法及网络选址中的应用 3.理解网络流的概念及其网络瓶颈的识别方法 4.理解最小费用流的调整与改进的思路和方法 (二)教学内容 第一节图论的概念 1.主要内容 (1)图的内涵 (2)路线类别 2.基本概念和知识点 图的定义和分类 3.问题与应用（能力要求） 学握图的内涵与路线类别 第二节最短路径问题 1.主要内容 (1)狄克斯特拉标号算法 (2)策略递推法 (3)最短路径应用 2.基本概今和知识点 标号法的基本思路、具体步骤，递推法基本思路、求解步骤，离散中心选 址法、离散重心选址法。 3.问题与应用（能力要求） 掌握最短路径问题的求解方法。 第三节最大流量问题 1.主要内容 (1)相关概念和定理 (2)求最大流标号法 (3)网络的瓶颈识别 2.基本概念和知识点 网络的最大流量问题，弧容量与容量网络，弧流量，前向弧与后向弧，饱 和肌与非询和弧，零那与非零那，流量可以扩东的路，网络流量与最大流： 标号过程，调整过程：截集、截量与最小截集，最大流-最小截量定理。 10 10 第六章 网络分析 （一）目的与要求 1.理解图论中结点、边、链、弧、路径的概念 2.掌握最短路径的标号算法及网络选址中的应用 3.理解网络流的概念及其网络瓶颈的识别方法 4.理解最小费用流的调整与改进的思路和方法 （二）教学内容 第一节 图论的概念 1.主要内容 （1）图的内涵 （2）路线类别 2.基本概念和知识点 图的定义和分类 3.问题与应用（能力要求） 掌握图的内涵与路线类别 第二节 最短路径问题 1.主要内容 （1）狄克斯特拉标号算法 （2）策略递推法 （3）最短路径应用 2.基本概念和知识点 标号法的基本思路、具体步骤，递推法基本思路、求解步骤，离散中心选 址法、离散重心选址法。 3.问题与应用（能力要求） 掌握最短路径问题的求解方法。 第三节 最大流量问题 1.主要内容 （1）相关概念和定理 （2）求最大流标号法 （3）网络的瓶颈识别 2.基本概念和知识点 网络的最大流量问题，弧容量与容量网络，弧流量，前向弧与后向弧，饱 和弧与非饱和弧，零弧与非零弧，流量可以扩充的路，网络流量与最大流； 标号过程，调整过程；截集、截量与最小截集，最大流-最小截量定理