《运筹学》-第八章图与网络分析习题及-答案(总5页).doc

运筹学第八章图与网络分析习题1.思考题() 解释下列名词，并说明相互之间的区别与联系：顶点，相邻，关联边；环，多重边，简单图；链，初等链；圈，初等圈，简单拳；回路，初等路；节点的次，悬挂点，孤立点；）连通图，连同分图，支撑子图；有向图，基础图，赋权图。子图，部分图，真子图() 通常用记号（，）表示一个图，解释及的涵义及这个表达式的涵义() 通常用记号（，）表示一个有向图，解释及的涵义及这个表达式的涵义() 图论中的图与一般几何图形的主要区别是什么？() 试述树与图的区别与联系() 试述 求最短路问题的ijkstra算法的基本思想及其计算步骤() 试述寻求最大流的标号法的步骤与方法() 简述最小费用最大流的概念及其求解的基本思想和方法() 通常用记号（，）表示一个网络，试解释这个表达式的涵义(10) 在最大流问题中，为什么当存在增广链时，可行流不是最大流？(11) 试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题