《南京师范大学2012数学建模校赛论文》由会员分享，可在线阅读，更多相关《南京师范大学2012数学建模校赛论文（43页珍藏版）》请在金锄头文库上搜索。
1、2011年数学建模竞赛试卷封面学院：强化培养学院竞赛题目：基于图论的足球单循环赛况的存在性及唯一性研究竞赛学生：姓名：周祥臻学号：23100225姓名：付子圣学号：23100204姓名：李澍虹学号：23100217 基于图论的足球单循环赛况的存在性及唯一性的研究摘要本问题考虑的是足球单循环赛中，各队对阵情况、胜负平的赛况，求出其存在性与唯一性的条件，并且给出时的解；同时分析题中给出的特例，以最少的条件给出其赛况。该问题可归结为一个已知度序列判断图的存在性及唯一性的图论问题。对于问题1，本文主要采用0-1优化模型，利用lingo软件对所给条件进行分析与约束，得出赛况；并采用机理分析，通过穷举法得
2、出赛况，验证lingo结果的正确性。对于问题2，（1）本文主要利用贪心算法思想及Havel- Hakimi定理，采用递归算法，得出存在性的条件即大小为的整数序列是图解序列当且仅当是图解序列。（2）运用遍历及模块匹配模型得出唯一性的条件为，邻接矩阵A中不存在或的子矩阵（3）本文采用穷举法，利用C语言编程得出对于，有71组是存在赛况的，有16组是存在唯一赛况的；并且通过分析得出唯一性条件：在不断地循环中，只有当每次循环中顶点度最大的度加上1小于非零值的个数；存在性条件：在不断循环中，只要出现一次顶点度最大的度加上1大于非零值的个数。对于问题3，（1）本文将问题2的结论进行推广，得到唯一性的条件：邻
3、接矩阵中不存在()的子矩阵。（2）列出满足问题2存在性条件下的各队胜负场次的度序列，通过对该序列的处理可以得出判断赛况存在性和唯一性的方法。本文采用了邻接矩阵反演法，根据题中升序的要求，得出n=6时，当每只队伍都比赛了五场的情况下，有304019组存在赛况。对于问题4，通过寻找各个数据之间的关系发现多余数据，删除多余条件。所建模型可以改进某一类特定图和稀疏矩阵的压缩存储方式；模块匹配模型可以运用到图像识别技术中去，具有推广价值。【关键词】贪心算法 可图度序列 Havel- Hakimi定理 递归 遍历 模块匹配 一、 问题重述本题是关于足球单循环赛的场次、胜，负，平，状况的一类问题。（1）已知
4、A,B,C,D,E,F,共6个队进行足球单循环比赛进行到一定程度后各队的胜负平以及进球数、失球数的状况，对赛况与比分进行求解。（2）已知各队比赛的场次正整数，论证其存在一种赛况使第个队比赛过的场次是；并求使得赛况唯一的条件。（3）给定每只球队的胜，负，平，状况，论证其存在一种赛况使第个队胜、负、平的场次分别为；并求胜负结果唯一的条件。（4）若要求得第一题的结果，至少需要多少数据。二、模型的假设1、不考虑天气等外部因素对赛况的影响2、在研究问题2与问题3时，在输出结果时，不考虑队伍的顺序，只按场次的升序讨论n=6时解的情况。三、定义与符号说明模型符号模型符号意义n比赛中队伍的个数第队的场次第队取
5、胜的场数第队失败的场数第队平局的场数,三个0-1变量，表示每组的胜平负情况,每只队伍的胜平负场数,每组的进球数与失球数图解序列与比赛时队的进球数邻接矩阵中的元素，表示与之间的赛况四、问题分析4.1对问题1的分析首先，C是解题的切入点。根据题意，C在此次比赛中打了3场，A打了4场，E打了4场，因此AC,CE组合还未进行比赛，C只与B,D,F进行了比赛。C的战绩是胜2场，其进球数为2，输球的个数为5；并且，B,F的进球数均小于5，因此唯一的可能性是，C以1比0的比分胜了D,F，以0比5的比分输给了B。其次，D是解题的另一切入点。根据提议，D在此次比赛中负两场，平3场，由于D已经输给了C，又A没有平
6、局记录，因此D的比赛情况只可能是D输给了A,C，根据D的输球个数知A,D的比分是4比0；D与B,E,F战平，并且，D的进球数为0，因此D与B,E,F的比分均为0比0。最后，由于E,F的平局数均为2，且D与E、D与F以及B与D已经是平局，不难推出，E,F是平局。根据以上两点，我们推导出进球数与失球数的表格（列表示进球数，行表示输球数，X表示未进行的比赛）ABCDEFA-0B-00C-5-0-0D401-00E-0-F10-因此，只要利用各队的进球数、失球数，以及“胜负平”状况即可得出结论。4.2对问题2的分析4.2.0 整体思想模型1：基于图论思想，我们将A-F队作为顶点，而每个队比赛的场次即为
7、顶点度，所有顶点度的列表就是度序列。我们就可以将第二题转化为度序列与无向图的对应关系问题，即判断该度序列是否为可图度序列。一个图解序列是一系列非负整数，这些数可以构成某个简单图的度序列。模型2：根据比赛赛况，我们可以建立的邻接矩阵（根据实际意义，用表示主对角线上的元素），表示为参加比赛，表示参加比赛。4.2.1存在性分析假设有队参加比赛，比赛场次均为,即（，）=（,）,此时若减少1个比赛场次，如，必定也要使。以此类推，要使赛况具有存在性，必定要使不同的两个队的场次同时减少。反过来，已知一组正整数（，）将其从大到小排列，得到（）将最大的数字依次向前分配比赛，即，直到或不能被分配或者是前面某一项已
8、为0为止。重复以上步骤若最后得到个0，则证明该赛况存在。4.2.2唯一性分析建立矩阵来表示队伍的比赛情况（表示不可能出现的情况），如果比赛情况不唯一，则表示在场次（，）确定的情况下，可能出现两种或两种以上的对阵情况，转化为矩阵的语言即：（为一常数）可交换中任意两项（这里指的是1,0交换）。4.3对问题3的分析4.3.1 模型1从题目可以看出，问题2是问题3的特殊情况（在问题3中只考虑平局情况就是在考虑问题2）。所以，满足问题2的存在性是问题3存在的前提条件。当满足第二问的存在性时（），我们只需要判断胜负关系是否可行就能判断赛况是否存在，而不用考虑。4.3.2 模型2在讨论赛况的唯一性时，问题2
9、的遍历及模块匹配模型是不考虑各队之间的胜，平，负关系的，问题2的邻接矩阵中数值0表示没有比赛，1表示有过比赛。我们可以将第二问的遍历及模块匹配模型进行推广，不仅考虑有无比赛，还要考虑胜负关系，这样我们就可以将推广后的模型应用到问题3中。4.4对问题4的分析首先，根据场次与得分，可以将每个队伍的胜、平、负的情况推理出来；其次，根据第二题存在性的结论，可以去掉一个队伍的场次数。五、模型的建立与求解5.1问题1的模型5.1.1 0-1优化模型定义三个0-1变量，分别表示每支队伍的胜，负，平情况每场球赛的对阵双方，一方胜利表示另一方失败表示每只队伍的进球数与输球数根据每个队可能的胜，负，平以及为比赛的
10、状况比较同一场比赛进球数与失球数的关系。结合以上条件，利用lingo软件求出最优解，如下表：（程序与结果见附录1）A-BA胜1比0B-FF胜0比1A-DA胜4比0C-DC胜1比0A-EE胜1比2C-FC胜1比0A-FF胜0比1D-E平局0比0B-CB胜5比0D-F平局0比0B-D平局0比0E-F平局2比2B-EE胜1比35.1.2 穷举法假设1：E:F=2:2，由此可以得出A与F比赛中进球数为0，同理，B与F比赛中进球为0。并且假设B与A比赛中进一球，则表格可变为。ABCDEFA-0B-00C-5-0-0D401-00E-0-2F00102-ABCDEFA-1-0B0-00C-5-0-0D40
11、1-00E20-0-2F00102-剩下四个空格通过解方程证明其不存在。假设2：E:F=2:2，由此可以得出A与F比赛中进球数为0，同理，B与F比赛中进球为0。B与E的比赛中进一球，则表格可变为：ABCDEFA-0-021B1-0031C-5-0-0D401-00E11-0-2F00102-剩下四个空格（加粗部分）通过解方程证明其存在。假设3：E:F=1:1，且E,F均必定胜2局，因此，E,F均必定胜A,B，此外A必定胜2局，因此A必定胜B。综合以上条件用lingo软件建立优化模型，得出该假设不存在。假设4：E:F=0:0，且E,F均必定胜2局，因此，E,F均必定胜A,B，此外A必定胜2局，因
12、此A必定胜B。综合以上条件用lingo软件建立优化模型，得出该假设不存在。综上所述，通过穷举法可得，问题1有唯一解，如下表所示A-BA胜1比0B-FF胜0比1A-DA胜4比0C-DC胜1比0A-EE胜1比2C-FC胜1比0A-FF胜0比1D-E平局0比0B-CB胜5比0D-F平局0比0B-D平局0比0E-F平局2比2B-EE胜1比35.2问题2的模型建立及求解5.2.1 递归模型5.2.1.0 理论基础阐述贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种
13、量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这样就能够得到某种量度意义下最优解。Havel-Hakimi定理:对于1，大小为的整数序列是图解序列当且仅当是图解序列，是删除中最大元素（）并且将紧跟的个最大元素一次减1得到的序列，含1个元素的图解序列只有是。5.2.1.1 模型的建立因此，我们可以用递归算法，通过检验有个数的序列来检验一个有个数的数列是否是图解序列。例如：把度序列从大到小排序,为了要说明33333221是图解序列，要找到该序列的一个实现使其中一个度为3的顶点有3个度为3的相邻顶点。这样的实现存在当且仅当2223221是图解序列。我们记录这个条件并测试3222221。我们不断地删除和记录，直到可以判断剩下的序列是否可以实现的序列是否是可实现的。如果是，则回过头来逐个顶点使其具有所需的度，最终得到原始序列的一个实现。实现是不唯一的，即存在。流程图如下：
