《最小生成树问题的数学模型及其证明.docx》由会员分享，可在线阅读，更多相关《最小生成树问题的数学模型及其证明.docx（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最小生成树问题的数学模型及其证明龙源期刊网httpdocsj/doc/e6a35fdd6394dd88d0d233d4b14e852458fb39f6.最小生成树问题的数学模型及其证实孙培刘凯来源：（电脑知识与技术）2021年第28期摘要：对图论中赋权无向图中最小生成树问题的数学模型，分析了建立的经过，并证实了各边不构成圈的一个等价条件，最后推广到有向图中，为用数学软件求解图论问题打下基础。关键词：最小生成树；赋权无向图；赋权有向图中图分类号：O221.4文献标识码：A文章编号：1009-3044202128-6682-031概述迄今为止，很多学者对赋权无向图中的最小生成树问题已经进行了研究，
2、提出了很多有效地求解算法，例如破圈法、避圈法等。其实最小生成树问题可以以用整数规划来表示，谢金星教授已给出了最小生成树问题的数学表达式1，但其中的无圈等价条件没有证实，并且无圈的等价条件还有很多种表示方法2-9，这些表示方法固然数学表达式不同，但本质上是一样的。因而，该文将对无圈的等价条件给出证实，并给出赋权有向图中最小生成树问题的数学模型。2赋权无向图中最小生成树问题的数学模型对一赋权无向图G，我们假定G无重边和环，即G为简单图，事实上，若G不是简单图，则有下面引理保证可以以求G的最小生成树。引理：给定赋权无向图G，若G有重边和环，则去掉后结果不会比原来的差。证实：若G有环，直接去掉，若G有重边，则将重边按权从大到小排列，只留下边权最小的边，其余的重边全去掉，得到新图G*。由于最小生成树问题是要求权最小的生成树，故由G*的生成方式知，G*的最小生成树就是G的最小生成树。我们用有向图的思想来解决无向图的最小生成树问题。事实上，我们把无向图中的边加倍，看成是不同方向的双弧，这样，就把无向图转化成了有向图。我们首先给出有向树及其相关概念。定义1假如有向图在不考虑边的方向时，是一棵树，那么这个有向图称为有向树。进一步，假如有一颗有向树T，恰有一个顶点的入度为0，其余顶点的入度都为1，则称T为根树。定义2在有向树T=V，A中，当u，vA时，称u是v的父亲，v是u的儿子。