最小生成树的模型数学公式

实验五 得到最小生成树

实验五

实验名称：

得到最小生成树

实验目的：

1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。

2.掌握图论中的最小生成树及Prim 和 Kruskal 算法等，进一步能用它们来解决实际问题。

实验内容：

输入一个图的权矩阵，得到该图的生成树，用Kruskal算法的最小生成树，用Prim算法的最小生成树。

实验五 得到最小生成树

实验原理：

Kruskal算法

假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。

1）将所有顶点涂成红色；

2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红；

3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。

Prim算法

假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:

1)初始化:U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。

2)在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。

数学建模中的图论方法

一、引言

我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。

另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。

图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如：

AMCM90B－扫雪问题；

AMCM91B－寻找最优Steiner树；

AMCM92B－紧急修复系统的研制(最小生成树)

AMCM94B－计算机传输数据的最小时间(边染色问题)

CMCM93B－足球队排名(特征向量法)

CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性)

CMCM98B－灾情巡视路线(最优回路)

等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。

DNA序列分类模型

重庆市数学建模竞赛一等奖

王 勇，莫志锋，秦力顼(1999级自动化学院)

［摘要］

本文根据题中所给两个已知类别的DNA序列进行结构特征分析，从中提取信 息和构造分类模型,对未知类别的DNA序列进行分类。我们构造了三个分类模型, 它们分别是：特征密码子概率分布判别模型、图论最小生成树模型和向量空间直 观判别模型。后两种分类结果几乎一致，判别率在90%左右，误判率控制在 (0. 05-0.1)范围。

问题一结果为： 模型一的结果：

A 类有 7 个：22, 23, 27, 29, 34, 35, 37；

B 类有 10 个：21, 24, 26, 28, 30, 31, 32, 33, 38, 40； 不能判断的有3个：25, 36, 39；

模型三的结果：

A 类有 10 种:22, 23, 25, 27, 29, 34, 35, 36, 37, 39；

B 类有 10 种：21, 24, 26, 28, 30, 31, 32, 33, 38, 40；

问题二结果为：

模型二的结果：

A类有108个，B类有74个。具体情况见文中答案。

模型三的结果：

A类有120个，B类有62个。具体情况见文中答案。

我们还对三种分类方法进行了类比，认为模型二、三方法新颖独特，结果稳 定，它们是一种较好的分类方法。并且对各种计算结果进行误差分析和检验等工 作。问题的重述

本问题为一个DNA序列分类问题。假定已知两组人工已分类的DNA序列（20个已知类 别的人工制造的序列），其中序列标号1—10为A类，11-20为B类。要求我们从已经分类 了的DNA序列片段中提取共同特征构造分类方法，并评价所用分类方法的好坏，从而构造或 选择一种较好的分类方法。测试对象是20个未标明类别的人工序列（标号21-40）和182 个自然DNA序列。

二、模型的假设及符号说明

1、 名词解释：

碱基：在生物学中，用A, T, C, G四个字符代表组成DNA序列的四种碱基；

各种图论模型及其解答

摘要：

本文用另一种思路重新组织《图论及其应用》相关知识。首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。

符号约定：

Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。

一、引言

图论是研究点、线间关系的一门学科，属于应用数学的一部分。现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。点表示事物，连线表示事物间的联系。整个求解过程如下：

原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解

整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。存在以下两种情况：

①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图

②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图

如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。

综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。

例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友

M：点表示人，连线表示当且仅当该两个人是朋友

A：问题转化为任何一个图一定存在两个顶点的度相等

二、图论模型

接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。

2.1 偶图模型 凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这类模型通常被包含在后续的模型中，但因许多现实问题可抽象成该模型，所以单列出来讨论。