图论与组合

福建师范大学研究生考试、考查成绩登记表学院数学与计算机科学学院专业学科教学（数学）年级2015级研究生研究生姓名何媛媛学号20151226导师潘彪课程名称现代数学概览课程类别（学位课、必修课、选修课）考试时间课内学时数总学时数学分数成绩评定结果任课教师主考教师（签名）考试考查补考张胜元对考生学习情况的简要评语：注：请主考教师将此表填写好，附在该学生试卷的首页，连同试卷交研究生秘书处。考试成绩按百分法，考查成绩按五级制记分法，补考按实际成绩记载、成绩及格评定结果记“通过”、不及格记“不通过”、学位课程75分以上评为合格2015-2016学年第一学期全日制专业学位研究生期末课程论文课程名称：现代数学概览论文题目：图论问题在数学竞赛中的应用任课教师：张胜元老师学院：数学与计算机科学学院专业：学科教学（数学）学号：20151226姓名：何媛媛目录摘要...............................................................................................................................1前言...............................................................................................................................21、竞赛数学中与图论有关的定理及其性质...........................................................31.1简单图...............................................................................................................31.2完全图...............................................................................................................31.3欧拉图与哈密顿图...........................................................................................31.4竞赛图...............................................................................................................32、竞赛数学中与图论有关的常见问题.....................................................................42.1图的连通性问题...............................................................................................42.2图的遍历问题...................................................................................................42.2.1欧拉问题.................................................................................................42.2.2哈密顿问题.............................................................................................43、解决数学竞赛图论问题的常用方法.....................................................................53.1存在性问题.......................................................................................................53.1.1抽屉原理.................................................................................................53.1.2反证法.....................................................................................................63.1.3极端性原理.............................................................................................63.1.4计数方法.................................................................................................63.2组合最值问题...................................................................................................73.2.1构造法.....................................................................................................73.2.2调整法.....................................................................................................7小结...............................................................................................................................81图论问题在数学竞赛中的应用摘要图论问题最早起源于世纪初，随肴计算机等现代工丹的产生，图论又与计算机网络、结构化学等相联系，得到广泛的应用而作为竞赛数学中组合部分的一个分支，在解决问题方面，如果从图论的观点出发，往往给我们提供一个处理问题的角度本文运用文献分析法，结合国内外有关图论的赛题，探究了“图论与竞赛数学组合问题”的联系，搭建起图论研究与竞赛数学研究的桥梁关键词：图论问题竞赛数学解题方法2前言经过多年的发展，竞赛数学所涉及的内容，大致可归结为六个方面、四大支柱、三大热点。六个方面是：初等代数、初等几何、不等式、数论、组合数学和图论、函数与其他；四大支柱是：代数（函数与函数方程、数列、不等式、多项式等），平面几何（直线形、圆、几何不等式、几何变换等），初等数论（质数与合数、奇数与偶数、同余、不定方程、进位制、数论函数），组合（组合汁数、组合设计、组合最值）；三大热点是：组合几何、组合数论、集合分拆。作为数学竞赛中的一个重要组成部分，组合数学源远流长几千年前，我国的《河图》、《洛书》就已经涉及一些简单有趣的组合问题近年來，由于计算机科学、编码理论、规划论、数字通讯、实验设计等学科的迅猛发展，提出了系列需要离散数学解决的理论和实际问题，促进了组合数学的发展，使这一古老的数学分支成为了一门充满活力的数学学科。组合问题在IMO数学竞赛试题中占到20%左右，组合问题涉及的知识大致可以分为计数、组合最值、图论、逻辑推理问题和组合构造等，其中出现得非常多的是组合计数和组合构造问题。对于一些组合构造问题，往往间接的体现出某些图的特性，这恰好足图论所要研究的问题。为此，本文将结合国内外有关图论方而的组合竞赛试题，详细探究数学竞赛中图论问题的常用解法和命题规律，旨在搭建起图论研究、竞赛数学研究与解决组合问题教学研究间的桥梁。31、竞赛数学中与图论有关的定理及其性质1.1简单图定理1.1（握手定理）如果G中有n个顶点，则该图中每个顶点的度数之和等于边数的两倍。即设G中的n个顶点为n21vvv、、、，总边数为e，则evdvdvdn2)()()(21。定理1.2对于任意的图G，奇顶点的个数一定是偶数。1.2完全图定理2.1对完全图5K的边进行二染色（红、蓝染色），存在一种染色法，使得染色后的图中没有同色三角形，此时整个图形必然可以分解为一红一蓝两个圈，每个圈恰好由5条边组成。定理2.2对完全图6K的边进行二染色，一定存在一个同色三角形。1.3欧拉图与哈密顿图定理3.1（—笔画定理）有限图G是一条链或圈（即可以笔画出）的充要条件是：G是连通的，且奇顶点个数等于0或2。当且仅当奇顶点的个数等于0时，连通阁是一个圈。定理3.2设连通图G，则G为欧拉图的充分必要条件是图G的每个顶点的度都是偶数。定理3.3设图G是n阶简单图，如果图中任意两个不相邻的顶点vu、，均有nvdud)()(，则称图G是哈密尔顿图。1.4竞赛图定理4.1设),(EVG是n阶竞赛图nK，则（1）VvVvvdvd)()(（2）VvVvvdvd22)]([])([“3循环”在无平局的比赛中，若有三个队满足A胜B，B胜C，C胜A，称这4三个队组成的集合CBA,,为“3循环”。定理4.2在顶点数)3(nn的竞赛图中，存在“3循环”的充要条件是存在两个顶点u、v，满足；)()(vdud。2、竞赛数学中与图论有关的常见问题2.1图的连通性问题在对图的连通性考察中，往往会出现两类题型：1、为了破坏原图的连通性，至少去掉多少条边；2、如果原图连通，去掉有限条边后，图是否还能连通？2.2图的遍历问题无论是理论上，还是在实际生活中，都有一些问题与遍历性有关。最早的遍历问题是著名的哥尼斯堡七桥问题：哥尼斯堡城位于普雷戈尔河畔，河中有两个岛，城区的四个部分通过七座桥连接起来。每到星期日，哥尼斯堡城的居民将会环城散步，由此提出了这样的问题：能否以一种方式环绕全城，使每座桥都被走过且只被走过一次。欧拉在1736年解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每块陆地用一个点来代钱，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”。英国数学家哈密尔顿，在正实心十二面体玩周游列国的游戏：使得从某个顶点出发，能够沿着正十二面体的棱前进，使得每个顶点恰好经过一次回到原来的那个顶点。这些世界上早先的遍历问题为研究现代网络问题提供了背景，而这些现代网络理论的不断完善，也为更好的研究和处理竞赛问题提供了理论依据。我们习惯把这两个问题所形成的问题分别称为欧拉问题和哈密尔顿问题，其对应符合的图称为欧拉图和哈密尔顿图。2.2.1欧拉问题由于哥尼斯堡问题的实质就是能否在图中找到一条封闭的路，使得它包含该图的所有边，其对应的问题也就可以转化为“一笔画”问题。2.2.2哈密顿问题例：在个班里，有)4(nn名同学，在这个班里任何1n名同学可以排成一5圈，使得相邻的两个人是朋友，但所有n名学生不能构成这样的圈。求n的最小值。（2009土耳其国家队选拔考试）分析：问题的实质就是求最小的n，使得有1n个顶点的图是哈密尔顿图，任意增加一个顶点，该图就不是哈密尔顿图。即uG（u为图G中任意一点）是哈密尔顿图，而G不是哈密尔顿图。图论中处理有关连通性和遍历性的问题，往往需要有较清晰的逻辑推理能力和灵活的问