国家集训队2000论文集徐静论文

《国家集训队2000论文集徐静论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图论模型的建立与转化安徽徐静关键字：图论模型、建立、转化摘要本文主要写图论模型的建立与转化，共分四部分：第一部分引言说明了图论建模在整个信息学竞赛中的地位，以及图论模型与其它数学模型的异同，并指出很有研究总结图论建模的思想、方法及技巧的必要。第二部分提出了图论模型建立中的两个要点：对原型中的要素进行适当的取舍和选择合适的理论体系,并分别举例加以详细分析，然后从中总结出了图论建模的总的原则：准确、清晰、简明。IIII第三部分主要讨论了在图论模型的转化中，应用得较为广泛的两种方法：拆分转化和补集转化,并着重分析了前者。文中把前者分为三类：点T边、点T点、边T边，其中详细分析了第二类。第四部分总

2、结了全文，并指出了进一步研究图论模型的必要性。目录—・弓I言二.图论模型的建立2I.要素的取舍2II.选择合适的理论体系4三.图论模型的转化7I•拆分转化7II.补集转化10U!结语11正文一・引言信息学竞赛以解题为主，整个解题过稈中一个重要的步骤就是数学建模，本文要讨论的就是数学建模的一个分支——图论建模。图论建模是指对…些客观事物进行抽象、化简，并用图I来描述事物特征及内在联系的过程。建立图论模型的冃的和建立其它的数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或是构造性问题；并且，和几何模型、运筹学模型一样，在建立图论

3、模型的过程中，也需要用到集合、映射、函数等基本的数学概念和工具；但图论模型和其它模型在它们的研究方法上又有着很人的不同，例如我们可以运用典型的图论算法来对图论模型进行求解，或是根据图论的基本理论来分析图论模型的性质，这些特殊的算法和理论都是其它模型所不具备的，而且在其它模型中，能用类似丁•图这种直观的结构来描述的也很少。我们学习图论，一般都是通过书籍，但书上介绍的往往只限丁图论模型的基本要素、一些图论的相关理论和经典算法等，至于如何建立图论模型、如何运用这些理论和算法、如何研究图论问题，都只有靠自己来理解、来领会，并通过实践来验证这些理解，通过摸索总结来提高自己的能力。在建立图论模型的过程

4、屮，我们常常会遇到…些困难，例如难以建立点、边、权关系,或是原型中的一些重要因素无法纳入现有模型，或是现有模型虽能表示原型，却无法求解等等。为了克服这些困难，就需要用到某些独特的思想、方法和技巧，本文要写的正是我在学习、实践中得出的这方面的一点认识。二.图论模型的建立在建立模型之前，我们首先要对研究对象进行全面的调查，将原型理想化、简单化（对于竞赛题而言，这一步大部分已经由出题人完成了）；然后对原型进行初步的分析，分清其中的各个耍素及求解目标，理出它们之间的联系；下一步就是用恰当的模型来描述这些耍素及联系。I•要素的取舍在用图论模型描述研究对象时，为了更突岀与求解目标息息相关的要素，降低思

5、考的复杂度，就不可避免地耍舍去部分耍素。下面我们就通过例1来分析一下。【例1】导线排布Linem：题目（文档附件:导线排布.doc）中蓝色的一段是问题描述的重点，其中涉及的要素有圆圈、N根导线、2N个端点、编号规则、导线的交叉等，求解冃标是构造一种符合所给的导线交叉情况的导线排布方案。起先，我们对题冃描述的导线排布并不熟悉，或许我们能够画出几个无解或是多解的例子，但竞赛时我们不可能花更多的时间在熟悉题目上了，这时只有尽快地把我们不熟悉的、难于思考的原型转化成我们熟知的、便于思考的模型。先来分析求解目标：所谓的构造导线排布方案，也就是找出每根导线两个端点的编号;而编号要满足的条件就是导线交叉

6、的情况。那么下一步我们就来分析一下编号与导线交义之间的关系。记第i根导线两端点的标号为Ai和Bi(AiA2>Bl>B2(b)Al>Bl>A2>B2图…(c)Al>A2>B2>Bl共同点是A1>B1,A2>B2,A1>A2(根据编号规则)，不同的是⑷满足A2>B1,B1>B2,⑹满足B1>A2,而(c)满足B2>B1o显然，这是•种偏序关系(有点不确切，它只满足反对称和传递性，但不是自反的)，而我们的任务就是根据这种偏序关系求得全序关系，即拓扑排序。我们用图中的有向边来表示偏序关系，若有向边构成环，则问题无解。以

7、上三种情况对应的有向图如图二所示，若两导线交叉，贝ij$ll(a)；若不交叉,则必是(b)、(c)其中之一，至于选择哪一个，就要看它们中哪一个不会导致无解。图二若(b)无解，就表示图中除了B1TA2这条边之外，还存在着一条A2TB1的路径，可能的两种情况如图三⑴⑵中红色有向边所示：⑴表示有编号大于2的导线(⑴中的导线3)与导线1交叉；(2)表示虽然它们都不与导线1交叉，但其中有选择图二(c)表示的。显然，如果情况⑴出现，