最小支撑树-数控机床标准g代码及m代码

§6.11 最小支撑树 6.11.1 支撑树 如图6.18所示，连通图G的某一无环连通子图T若覆盖G中所有的顶点，则称作G的一棵支撑 树或生成树（spanning tree）。 图6.18 支撑树 就保留原图中边的数目而言，支撑树既是“禁止环路”前提下的极大子图，也是“保持连通” 前提下的最小子图。在实际应用中，原图往往对应于由一组可能相互联接（边）的成员（顶点） 构成的系统，而支撑树则对应于该系统最经济的联接方案。确切地，尽管同一幅图可能有多棵支 撑树，但由于其中的顶点总数均为n，故其采用的边数也均为n - 1。 6.11.2 最小支撑树 若图G为一带权网络，则每一棵支撑树的成本（cost）即为其所采用各边权重的总和。在G 的所有支撑树中，成本最低者称作最小支撑树（minimum spanning tree, MST）。 聚类分析、网络架构设计、VLSI布线设计等诸多实际应用问题，都可转化并描述为最小支 撑树的构造问题。在这些应用中，边的权重大多对应于某种可量化的成本，因此作为对应优化问 题的基本模型，最小支撑树的价值不言而喻。另外，最小支撑树构造算法也可为一些NP问题提供 足够快速、足够接近的近似解法（习题[6-22]）。正因为受到来自众多应用和理论领域的需求 推动，最小支撑树的构造算法也发展得较为成熟。