图论-中科院数学研究所

中科大考博辅导班：2019中科大数学科学学院考博难度解析及经验分享中国科学院大学2019年博士研究生招生统一实行网上报名。

报考者须符合《中国科学院大学2019年招收攻读博士学位研究生简章》规定的报考条件。

考生在报考前请联系所报考的研究所(指招收博士生的中科院各研究院、所、中心、园、台、站)或校部相关院系，了解具体的报考规定。

下面是启道考博辅导班整理的关于中国科学技术大学数学科学学院考博相关内容。

一、院系简介数学科学学院的前身数学系于1958年由著名数学家华罗庚教授亲自主持创办并任首任系主任，关肇直、吴文俊、冯康、龚昇、王元、万哲先、陆启铿、石钟慈、林群、张景中、陈希孺等一大批知名专家曾在此任教。

2011年5月，数学科学学院正式挂牌成立，首任院长为马志明院士。

本院为首批全国理科人才培养基地、中国科学院博士生重点培养基地、长江学者特聘岗位设置学科，并获得首批数学一级学科博士学位授予权（涵盖数学所有博士点）,2007年获首批一级重点学科，是教育部985、211工程、中科院知识创新工程建设学科。

为吸引高水平的学者来我院讲学，学校为本院设立了“华罗庚大师讲席”及“吴文俊大师讲席”。

二、招生信息中国科学技术大学数学科学学院博士招生专业有1个：070100数学研究方向：随机分析与数理金融．计算机辅助几何设计．计算机图形学．应用逼近论、并行计算．组合优化．李代数及相关理论．微分几何．可积系统与子流形．几何分析．Ads/ds 空间的几何．可积系统．代数表示论．微分几何．非线性演化方程．可积系统．一维动力系统．材料科学与结构分析的计算方法研究．计算机辅助几何设计．计算机图形学．应用逼近．密码学．李代数及相关理．组合数学．信息安全．编码理论．无穷维系统控制．复杂系统控制及系统可靠．几何拓扑．拓扑量子场．动力系统．遍历理论．拓扑．图论．代数组合．偏微分方程．几何分析．亚纯函数值分布相关理论．一维动力系统．计算机辅助几何设计．计算机图形学．应用逼近论．生物数学．抛物方程动力学．应用分析．计算机图形学．图像处理．微分几何．离散几何分析．偏微分方程．几何分析．大范围分析．极值组合．图论．概率方法．组合优化．偏微分方程．算术代数几何．代数数论．函数空间与算子理论．Clifford分析．哈密尔顿系统．动力系统．遍历理论．拓扑学．一维动力系统．代数几何．微分方程动力系统．生物数学．几何分析．微分几何．代数群与量子群．算术代数几何．概率论与随机分析．偏微分方程数值方法．数据科学．最优化计算方．计算几何（三维打印的优化设计）．黎曼几何．动力系统．遍历理论．拓扑学．代数表示论．量子群与张量范畴．弦理论．共形场．最优化计算方法．随机优化．偏微分方程数值方法理论及应用．李代数与量子群．随机分析．微分几何．几何分析．组合设计与编码．宇宙学．偏微分方程数值解．可积系统三、报考条件（1）中华人民共和国公民；拥护中国共产党的领导，愿意为祖国社会主义现代化建设服务；品德良好，遵纪守法，学风端正，无任何考试作弊、学术剽窃及其它违法违纪行为；（2）身体健康状况符合我校规定的体检要求，心理正常；（3）申请者原则上应来自国内重点院校或所在高校学习专业为重点学科；（4）专业基础好、科研能力强，在某一领域或某些方面有特殊学术专长及突出学术成果；（5）对学术研究有浓厚的兴趣，有较强的创新意识、创新能力和专业能力；（6）申请者的学位必须符合下述条件之一：应届硕士毕业生须在博士入学前取得硕士学位；或已获得硕士或博士学位；在境外获得学位的考生，须凭教育部留学服务中心的认证书报名；（7）具有较强的语言能力，外语（限本单位招生专业目录中公布的语种）水平较高。

图论综述一、简介图论是数学的一个分支。

它以图为研究对象。

图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。

集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。

通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。

图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。

关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。

目前，图论已形成很多分支：如随机图论、网络图论、代数图论、拓扑图论、极值图论等。

图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、非线性物理、心理学、社会学、交通管理、电信以及数学本身等。

二、基本内容2.1 图的基本概念本章首先介绍了图的一些基本性质和一些不同模型的图，包括偶图，完全图和补图，引入了定点度的来描述图的性质。

其次介绍了子图的相关概念，介绍了图的一些基本运算规则，对图的路和连通性进行了阐释。

紧接着讲解了最短路算法，定义设G为边赋权图。

u与v是G中两点，在连接u与v的所有路中，路中各边权值之和最小的路，称为u与v间的最短路。

图的代数表示，包括图的邻接矩阵和图的关联矩阵。

最后对极图理论进行了简介，主要介绍了极值图论中的一个经典结论——托兰定理。

2.2 树本章主要介绍了树的概念与性质，阐述了生成树与最小生成树的基本概念与一些常用结论与定理。

树是不含圈的无圈图，也是连通的无圈图。

树是图论中应用最为广泛的一类图。

在理论上，由于树的简单结构，常常是图论理论研究的“试验田”。

第一章习题1. 对任何简单图G ，(1) 证明：(1)()2G υυε−≤；(2)(1)()2G υυε−=当且仅当G K ν≅。

2. 证明：(1),()m n K mn ε=；(2) 若G 是完全二部图，则2()4G υε≤。

3. 图G 有21条边，12个3度顶点，其余顶点的度均为2，求图G 的阶数。

4. 证明：任何简单图必有至少两个顶点具有相等的度。

5. 设G 是简单图，求G 的所有不同的生成子图的个数（包括G 本身和空图）。

6. 证明：任何图中，奇度顶点的个数总是偶数（包括0）。

并由此证明：在任一次聚会上握过奇数次手的人必为偶数个。

7. 证明或反证：如果u 和v 是图G 中仅有的具有奇数度的顶点，则G 包含一条u , v 路。

8. 证明：若4υ≥且1+=νε，则存在)(G V v ∈使得3)(≥v d 。

由此证明： n 个球队比赛（4n ≥），已赛完n +1场，则必定有一个球队已参加过至少3场比赛。

9. 在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有13个队，能否恰当安排比赛使得每个队在其所在赛区中进行9场比赛而与另一个赛区中的运动队进行4场比赛？10. 在平面上有n 个点12{,,,}n S x x x =⋅⋅⋅，其中任两个点之间的距离至少是1。

证明在这n 个点中，距离为1 的点对数不超过3n 。

11. 某次会议有n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每两个互不认识的人都恰好有两个共同的熟人。

证明每一个参加者都有同样数目的熟人。

12. 在一个化学实验室里，有n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种化学品恰好在两个药箱中出现，问：（1）每个药箱有几种化学品？（2）这n 个药箱中共有几种不同的化学品？13. 在一次舞会中，A 、B 两国留学生各(2)n n >人，A 国每个学生都与B 国一些(不是所有)学生跳过舞，B 国每个学生至少与A 国一个学生跳过舞。

科大组合与图论专业三十五年------为科大校庆五十周年而写李乔、李炯生、徐俊明中国科学技术大学组合与图论专业从李乔发表的第一篇论文算起，经历了整整35年。

在这35年里，逐渐形成了自己的研究特色：组合矩阵论和组合网络理论。

发表学术论文300余篇，专著和教材16部。

获得1993年国家教委科技进步一等奖（合作）和2003年安徽省自然科学二等奖。

培养硕士研究生57名，博士研究生26名，进站博士后5名，接收国内高校青年进修和访问学者9名。

回忆这段历史，科大组合学与图论专业的创立和发展大体上分为三个阶段。

一、创立阶段（1973-1985）中国科学技术大学数学系的组合学与图论研究始于上世纪七十年代初。

北京大学段学复教授向曾肯成建议：国内可由科大牵头研究组合与图论。

李乔和冯克勤凭借代数方面的深厚功底开始涉及组合与图论，在国内率先开展代数图论研究。

1973年，李乔在《中国科学技术大学学报》上发表的“关于偶图的极大对口”是本专业第一篇学术论文。

随后，李乔和冯克勤合作完成了 “关于树和其他图的联系矩阵”、“图的谱性质的若干结果”和“论图的最大特征根” 3篇论文，分别发表在《中国科学技术大学学报》（1976，1979）和《应用数学学报》（1979）上。

这些论文是国内代数图论研究最早的学术论文，现成为此研究领域的经典论文之一。

在此期间，李乔和冯克勤还从数学角度介入当时国内兴起的“量子化学的图论研究”，成为国内最早开展此项研究的学者。

1977年8月在上海举行的全国第一次量子化学学术会议上，李乔介绍了他与冯克勤在这方面的研究成果。

组合学是经典的数学分支，被人熟知。

图论是组合学的一个活跃分支，但当时数学界对它还不大了解。

1977年底，李乔对数学系师生做了题为《图论》的介绍性报告。

他以图论语言简洁证明“在任意六人中必存在三人, 要么都相识,要么都不相识”为开场，来介绍图论，生动有趣。

正是这个报告引起了不少人对图论的兴趣。

在此以前，国内出版的图论教材只有李修睦于1962年译自法国图论专家C.Berge的《图的理论及其应用》。

中科院谈论四色定理中科院谈论四色定理1. 引言：四色定理是一条著名的图论定理，它给出了一个惊人的结论，即任意平面图都可以用四种颜色给图中的所有国家着色，使得任意相邻的国家颜色不同。

这个定理在数学界引起了广泛的关注和研究。

在本文中，我们将从深度和广度两个角度来探讨中科院在谈论四色定理时所提出的观点和理解。

2. 深度探讨：2.1 背景介绍：四色定理最早由英国数学家弗朗西斯·格斯伊在1852年提出，并在正式发表于1977年之前一直是一个猜想。

这个定理经过了长时间的推导和证明，才最终被证明是成立的。

2.2 中科院的观点：中科院认为四色定理在图论领域具有重要的理论和实际意义。

通过研究四色定理，人们能够更好地理解和应用图论的相关概念和方法，同时也为一些实际问题的解决提供了启示。

在地图着色问题中，四色定理的应用可以帮助我们有效地解决颜色分配的困难。

2.3 个人观点：我认为四色定理的证明过程非常复杂和深奥，需要借助大量的数学工具和推导过程。

通过深入研究四色定理，我意识到数学的广度和深度远远超出了我们的想象。

作为一名写手，我深深体会到了数学的美妙之处，也进一步认识到数学在现实生活中的重要性。

3. 广度探讨：3.1 相关概念解析：在讨论四色定理时，我们需要了解一些相关概念，如平面图、着色、相邻等。

平面图是指可以画在平面上，并且不同的边不会相交的图形。

着色是指给图中的每个国家或区域分配一种颜色的过程。

相邻是指在图中两个共享边或顶点的国家之间的关系。

3.2 解决方法：中科院指出，四色定理的证明过程需要借助大量的数学推理和证据，其中最重要的是运用了红蓝可授、细分、降维等方法。

这些方法的运用使得人们能够更好地理解和证明四色定理的正确性。

3.3 总结回顾：通过对四色定理的深入研究，我认识到解决问题的方法和途径远远超出了我们的想象。

在数学领域，我们需要运用多种方法和策略来解决复杂的问题，而这些方法也可以在其他领域或生活中得到应用。

中国科学院武汉物理与数学研究所中国科学院武汉物理与数学研究所简介中国科学院武汉物数所座落在风景秀丽的武汉东湖之滨、小洪山麓，由原武汉物理所（创建于1958年）和武汉数学物理与计算技术研究所（创建于1957年）合并而成，现任所长詹明生研究员。

在两所合并之前，著名原子物理学家王天眷，著名物理学家张承修，著名空间物理学家李钧院士，著名数学家李国平院士，著名数学家丁夏畦院士都曾在武汉物理所或武汉数学物理所长期工作并担任重要职务。

本所以核磁共振波谱学、原子分子物理、数学物理、光电子学和相关高技术为主要研究领域，涵盖了核磁共振方法、核磁共振成像、冷原子物理、量子计算、非线性偏微分方程、原子频标、激光雷达和原子信标等主要研究方向。

在此基础上加强物理与数学、生物、化学等其他学科领域的交叉结合，衍生新的学科生长点。

中国科学院冷原子物理中心（武汉）和武汉磁共振研究中心均依托在本所。

本所的基础研究主体由波谱与原子分子物理国家重点实验室、数学物理实验室、原子频标实验室、光电探测实验室组成。

本所是武汉光电国家实验室（筹）的组建单位之一。

拥有由波谱光谱技术、频标技术平台和信息中心组成的支撑系统以及实现成果转化的控股高技术公司；具有优越的科研条件和大量现代化科研仪器装备。

本所拥有4个博士点、多个硕士点和一个博士后流动站，同美、英、日、法等20余个国家和地区的著名学府和科研机构建立了合作交流关系。

近年来本所致力于科研队伍的优化，引进和造就了一批高层次的青年学科带头人，形成了以中青年专家为主的研究群体，他们充分施展才智，所做的研究工作和取得的科研成果在国内多具特色，并在国际上占有一席之地。

本所是中国物理学会的常务理事单位，全国波谱学专业委员会的挂靠单位，湖北省暨武汉市物理学会理事长单位。

主办的《数学物理学报》（中、英文版）和《波谱学杂志》均为我国自然科学的核心刊物，《数学物理学报》英文版为SCI收录期刊。

高校基本信息学校名称：中国科学院武汉物理与数学研究所高校代码：99999所在省市：湖北学校。

图论与代数结构戴一奇　胡冠章　陈　卫清华大学出版社(京)新登字158号内　容　简　介离散数学是计算机专业的主要数学基础,本书与“数理逻辑与集合论”一起构成了清华大学计算机系的离散数学教材,全书共分10章:图论的基本概念;道路与回路;树;平面图与图的着色;匹配与网络流;图的连通性;代数结构预备知识;群;环和域;格与布尔代数。

全书结构紧凑、内容精炼、证明严谨、语言流畅。

为了便于读者理解和掌握基本理论,书中提供了丰富的例题,同时给出了众多良好的图算法,并进行了复杂性分析。

此外,每章附有较多习题,其难度恰当。

本书可作为计算机专业学生的教科书或参考书,也可供计算机工程技术人员作为参考。

图书在版编目(CIP)数据图论与代数结构/戴一奇等编著。

—北京:清华大学出版社,1995ISBN7－302－01814－6Ⅰ．图…　Ⅱ．戴…　Ⅲ．①图论②代数－结构(数字)Ⅳ．①0157．5②015中国版本图书馆CIP数据核字(95)第03642号出版者:清华大学出版社(北京清华大学校内,邮编100084)印刷者:北京通县宏飞印刷厂发行者:新华书店总店北京科技发行所开　本:787×10921/16　印张:　14．25字数:　335千字版　次:1995年8月第1版 1997年12月第2次印刷书　号:ISBN7－302－01814－6/T P・810印　数:4001～6000定　价:12．90元前 言离散数学是计算机专业的基础数学课程,它以离散量为研究对象,主要包括数理逻辑、集合论、图论和代数结构四部分内容。

清华大学计算机科学与技术系把离散数学安排为“数理逻辑与集合论”,“图论与代数结构”两门课程,分两个学期讲授,各占50学时。

本书分两大部分,其中一～六章是图论,在第一章介绍了图的基本概念及其代数表示方法,第二至第六章分别详细讨论了道路与回路、树、平面图与图的着色、匹配与网络流、图的连通性等图论的主要内容,并且将它们与计算机的应用紧密结合,分析介绍了众多良好的图算法,给出其正确性证明与复杂度分析,这样,使读者在图的应用及算法的设计与分析方面能得到较好的训练与培养。

数研所标准
数研所，即中国科学院数学与系统科学研究院，是中国科学院下
属研究所之一，成立于1978年。

数研所是我国数学、应用数学、运筹
学与系统科学研究的重要基地，也是我国数学教学与人才培养的重要
力量。

数研所在研究领域涵盖了数学、数理统计、运筹学与管理学、系
统理论与控制论、金融数学等多个学科。

其研究方向包括李群李代数、非线性系统与控制、微分方程与动力系统、图论与组合优化、统计理
论与方法等。

数研所在科学研究、人才培养、学术交流等方面都有一定的贡献
和影响力。

它是国内较早进行数学研究的机构之一，拥有一批优秀的
科研人员和学科团队，进行着创新性的基础研究和应用研究。

数研所
还开设了一系列的学科硕士、博士研究生培养项目，为我国培养了大
批的学术骨干人才。

数研所的标准是根据科学研究的要求和学术规范来制定和遵守的。

这包括在研究项目的选择、研究方法的运用、研究成果的评价和发表
等方面，都有一定的规定和要求。

数研所还积极开展国内外学术交流
与合作，举办学术会议、学术报告等活动，促进学术交流与合作，推
动学科发展。

总的来说，数研所的标准体现了科学严谨、创新性、学术规范等
方面的要求，对于促进学科的发展和培养优秀人才具有重要意义。

关于研究生图论教学的研究作者：沈健来源：《东方教育》2018年第24期摘要：《图论及其应用》是我校数学系研究生的一门基础选修课，选修的同学来自多个专业方向，存在基础不同，研究方向迥异等诸多问题。

论文分析了上这门课时遇到的问题，并提出解决方法，希望能提高教学效果。

关键词：图论；研究；教学模式一、引言图论是研究由若干点及连接点的边所组成的图的科学，是数学的一个分支，属于应用数学的一部分。

图论是一门古老而又新兴的科学，它的起源很早。

早在1736年，著名的科学家欧拉在哥尼斯堡七桥问题[1]上就用图的方法解决这个问题，并开创了一门学科——图论。

虽然在欧拉发表奠基性论文之后的几百年时间，图论发展非常缓慢，很多问题都是围绕游戏展开，如迷宫问题，博弈问题，棋盘上马的行走问题等。

直到十九世纪中叶，图论问题大量出现，如四色问题，汉密尔顿问题[2]等，并且以图为工具解决了其他领域的问题。

随着上世纪七八十年代科学的发展，在生产管理，交通运输，军事，计算机等领域提出了很多离散问题，促进了图论的发展。

所以现在图论知识涉及到各个领域，有着举足轻重的地位。

我校数学系开设《图论及其应用》这门基础选修课[3]，是希望同学能掌握基本的图论知识，学会图论中的算法，并灵活掌握解决图论问题的方法。

在讲授这门课的时候，发现同学存在基础差异巨大、研究方向迥异、对图论应用缺乏了解等诸多问题[4]。

二、图论教学中存在问题分析1、同学基础差异较大学校的研究生本科阶段在不同的学校学习，各校的培养计划不同，所学的知识也不同。

有些学校将图论列为必修课，所以这些同学在本科阶段已经有了系统的学习，对图论的基本概念，重要定理，主要方法已经有了很好的掌握，基础较好。

另外一部分同学所在学校仅开设了《离散数学》，或者将图论列为选修课，同学重视程度不够，所以虽然了解一些相关概念，但是基础不佳。

最糟糕的是极少数同学在本科阶段没有学习过任何图论有关的知识，所以同学的基础为零。

中科院对数学领域的划分
中科院（中国科学院）对数学领域进行了如下划分：
1. 数论与代数数论：研究数与数的性质、数的分布规律、数的整数解等。

2. 代数学：研究代数结构的性质与变换。

3. 存在性理论与计算复杂性：研究数学中的存在性问题与计算问题。

4. 几何与拓扑学：研究空间与形状的性质与变换。

5. 微分方程与动力系统：研究描述自然与社会现象、物理模型中的微分方程与动力系统。

6. 数学物理方程与非线性分析：研究描述物理系统的数学模型与非线性分析方法。

7. 数学方法与计算数学：研究数学方法在科学与工程中的应用，包括数值计算、优化方法、模拟与建模等。

8. 统计学：研究概率与统计的理论与方法，包括多元统计、贝叶斯统计、时间序列分析等。

9. 运筹学与控制论：研究优化与决策理论，以及系统的模型建立与控制方法。

10. 应用数学与交叉学科：研究数学在其他学科中的应用，如
生物数学、金融数学、图论等。

此外，中科院还设有数学研究所，作为数学领域的研究机构，开展各个方向的研究工作。

第一章习题1. 对任何简单图G ，(1) 证明：(1)()2G υυε−≤；(2)(1)()2G υυε−=当且仅当G K ν≅。

2. 证明：(1),()m n K mn ε=；(2) 若G 是完全二部图，则2()4G υε≤。

3. 图G 有21条边，12个3度顶点，其余顶点的度均为2，求图G 的阶数。

4. 证明：任何简单图必有至少两个顶点具有相等的度。

5. 设G 是简单图，求G 的所有不同的生成子图的个数（包括G 本身和空图）。

6. 证明：任何图中，奇度顶点的个数总是偶数（包括0）。

并由此证明：在任一次聚会上握过奇数次手的人必为偶数个。

7. 证明或反证：如果u 和v 是图G 中仅有的具有奇数度的顶点，则G 包含一条u , v 路。

8. 证明：若4υ≥且1+=νε，则存在)(G V v ∈使得3)(≥v d 。

由此证明： n 个球队比赛（4n ≥），已赛完n +1场，则必定有一个球队已参加过至少3场比赛。

9. 在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有13个队，能否恰当安排比赛使得每个队在其所在赛区中进行9场比赛而与另一个赛区中的运动队进行4场比赛？10. 在平面上有n 个点12{,,,}n S x x x =⋅⋅⋅，其中任两个点之间的距离至少是1。

证明在这n 个点中，距离为1 的点对数不超过3n 。

11. 某次会议有n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每两个互不认识的人都恰好有两个共同的熟人。

证明每一个参加者都有同样数目的熟人。

12. 在一个化学实验室里，有n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种化学品恰好在两个药箱中出现，问：（1）每个药箱有几种化学品？（2）这n 个药箱中共有几种不同的化学品？13. 在一次舞会中，A 、B 两国留学生各(2)n n >人，A 国每个学生都与B 国一些(不是所有)学生跳过舞，B 国每个学生至少与A 国一个学生跳过舞。