大工《运筹学》21春在线作业2参考答案.docx.docx

运筹学网络图和图论知识点总结 本文总结了《运筹学》中的网络图和图论知识点，涵盖了网络图的概念、关键路径、图的定义、树和森林、最大流问题、最小支撑树问题等方面的知识。 一、网络图的概念 * 网络图是由一些点及点间的连线所组成的图，用于描述项目的进度计划和资源分配。 * 网络图中，路径是从始点到终点之间相连节点的序列。 * 关键路径是整个项目中的关键环节，决定了完成整个项目所需要的最长时间。 二、图的定义 * 图是由点及弧所构成的图，可以是有向图或无向图。 * 无向图是由点及边所构成的图。 * 环是指一条边的两个端点相同的边。 * 多重边是指两个端点之间不止一条边。 * 简单图是指一个无环也无多重边的图。 三、树和森林 * 树是一个连通无圈简单图。 * 森林是一组树的集合。 * 最小树是指树枝总长为最短的部分树。 四、最大流问题 * 最大流问题是一个特殊的线性规划问题，旨在找到网络中的最大可行流。 * 最大流问题的应用场景包括交通网络、通讯网络、生产流程等领域。 五、最小支撑树问题 * 最小支撑树问题是指在给定图中，寻找树枝总长为最短的部分树的过程。 * 最小支撑树问题的应用场景包括计算机网络、交通网络、能源供应等领域。 六、网络分析 * 网络分析是指对网络图进行分析、评估和优化的过程。 * 网络分析包括最小支撑树问题、最短路问题、最大流问题，以及网络计划评审与优化问题等。 七、关键路径法 * 关键路径法是指确定关键路径的方法，旨在找到项目中的关键环节。 * 关键路径法的应用场景包括项目管理、生产计划、资源分配等领域。 八、自由时差 * 自由时差是指在不影响各项紧后作业最迟开工的条件下，该作业可以推迟开工的最大限度。 * 自由时差的应用场景包括项目管理、生产计划、资源分配等领域。 九、其他知识点 * 作业的最早结束时间是指它的最早开始时间加上该项作业的计划时间。 * 图是由一些点及点间的连线所组成的，可以是有向图或无向图。 * 连通图是指任意两点之间至少存在一条链的图。 本文总结了《运筹学》中的网络图和图论知识点，涵盖了网络图的概念、关键路径、图的定义、树和森林、最大流问题、最小支撑树问题等方面的知识。