图论GraphTheory复旦大学数学科学学院

运筹学与控制论专业（运筹学方向）攻读硕士学位研究生培养方案一．培养目标根据德、智、体全面发展的教育方针，培养具有社会主义觉悟、严谨的治学态度和良好的学风、有追求真理、献身科学的敬业精神和高尚的道德情操，具有系统的运筹学理论基础和专业知识，既能独立进行科学研究，又能从事经济和企业管理及高等学校教学工作的高级专门人才。

二．研究方向1．数学规划2．组合优化3．管理运筹学三．招生对象招生对象为数学、管理学、系统科学专业高等院校全日制本科毕业人员以及同等学力（指上述专业的函授、自考本科毕业或高等院校全日制专科毕业）人员，同等学力考生在报名时须提交以第一作者身份在二级或二级以上学术刊物公开发表的学术论文一篇。

四．学习年限三年，在职研究生四年。

应修满37学分。

五．课程设置（教学计划表附后）（一）学位课程1．公共课0000002101邓小平理论Deng Xiaoping Theory0000002104自然辨证法概论Conspectus of Nature Dialectics0000002103第一外国语The Foreign Language2．专业课0701052101离散数学Discrete Mathematics0701052102凸分析Convex Analysis0701052103线性规划Linear Programming(二) 选修课程1.指定选修课（必修课）0701052201非线性规划理论与算法Nonlinear Programming Theory and Algorithm0701052202组合优化Combinational Optimization0701052203图论Graph Theory0701052204决策优化Decision-making Analysis0701052205对策论Games Theory0701052206数值优化Numerical Optimization0000002201网络技术与应用Network Technology and Its Application多元微积分算法复杂性2.任意选修课（任选课）0701052207变分与互补理论Variational Inequalities and Complementarity0701052208软件设计Design on Software0701052209经济运筹学Economics Operations Research0701052210排序论Shcheduling Theory0701052211 物流管理Logistics Management0000002202第二外国语The Second Foreign Language六．社会实践与教学实践参与科研应用项目的研制与开发一项，或为信息管理与信息系统专业本专科生讲授、辅导运筹学、应用数学或管理学课程16学时，记2学分。

数学系本科生课程设置与简介01101011 数学分析(1) mathematical analysis课程性质：专业基础课课内学时：112 学分：7简介：“数学分析”是数学专业最重要的一门专业课。

第一学期主要内容是分析基础。

第一章函数、第二章极限、第三章连续函数、第四章实数的连续性、第五章导数与微分、第六章微分基本定理及其应用、第七章不定积分、第八章定积分。

先修课要求：无教材及参考书：《数学分析讲义》刘玉琏傅沛仁编高等教育出版社适用专业：数学与应用数学开课学期：秋01101021 数学分析(2) mathematical analysis课程性质：专业基础课课内学时：144 学分：8简介：本学期将在此基础上继续学习级数和多元函数微分学。

级数是数学分析的重要组成部分，它分为数值级数和函数级数。

数值级数是函数级数的特殊情况，也是函数级数的基础；函数级数是表示非初等函数的一个重要的数学工具，它在自然科学、工程技术和数学本身都有广泛的应用。

多元函数微分学是一元函数微分学的推广，隐函数、反常积分与含参变量的积分、重积分和曲线积分与曲面积分。

并且对某些概念和定理作了进一步的发展。

先修课要求：数学分析(1)教材及参考书：《数学分析讲义》刘玉琏傅沛仁编高等教育出版社适用专业：数学与应用数学开课学期：春01101031 数学分析(3) mathematical analysis课程性质：专业基础课课内学时：40 学分：2简介：本学期将在此基础上继续学习级数和多元函数积分学。

多元函数积分学是一元函数积分学的推广，隐函数、反常积分与含参变量的积分、重积分和曲线积分与曲面积分。

并且对某些概念和定理作了进一步的发展。

先修课要求：数学分析(1) 、数学分析(2)教材及参考书：《数学分析讲义》刘玉琏傅沛仁编高等教育出版社适用专业：数学与应用数学开课学期：秋01101041 数学分析选讲 Selected Topics of Analysis课程性质：专业选修课课内学时：48 学分：2简介：数学分析教材自身科学规律概述、数学分析的思想方法与表达方式浅析、数学分析解题方法概述、关于数学分析中何种类型习题宜于用反证法证明的问题、形式逻辑与辩证逻辑方面易出现的错误及其分析、函数、数列极限、函数极限、函数的连续性、导数、中值定理与导数的应用、实数的基本定理、不定积分、定积分、数项级数、函数列与函数项级数、含参量正常积分、黎曼积分概念与性质，重积分的计算、曲线积分、曲面积分、各类积分间的联系、非正常积分、含参量非正常积分。

图论学习笔记（3）基本概念图G中的结点u与v相邻接当且仅当它们在图H中的相应结点也邻接，则称图G与图H是同构的（isomorphic），记作G≈H，否则，称两者为非同构的（nonisomorphic）。

用函数描述同构：图G与图H同构，即存在一个一一映射函数 f : V(G) →V(H)，此时，图G中任何结点对u和v邻接当且仅当f(v)和f(u)在图H中邻接。

函数f 称作从G到H的同构函数（isomorphic function）。

相关推论：令函数 f : V(G) →V(H)为图G与图H的同构函数，那么，对任意结点u∈V(G),都有deg(u)=deg(v)，换句话说，如果两个图同构，则对应的结点有相同的度数。

设图G与H同构，同构函数为 f : V(G) →H(G)。

若在图G中，结点v1与v2间的测地线为v1,v2,v3,...,vk，则在图H中，f(v1),f(v2),f(v3),...,f(vk)是结点f(v1)与f(vk)间的测地线。

含n个结点的图G的度序列（degree sequence）是指按照节点度数排列的n-元非递增序列。

若一个非负整数的非递增序列S可以表示某个图的度序列，则称序列S是可绘的。

注：非递增序列可绘⇒图的结点度数之和是非负偶数。

相关算法：可绘图度序列的判定算法从序列S中删除第一个数k。

如果S的第一个数后的k个数都大于等于1，则将这k个数分别都减去1得到新序列S'；否则，停止，得出元序列不可绘图的结论。

若S'全是0，停止，得原序列为可绘图。

将步骤2得到的序列S'重新排序，得到非递增序列S*。

令S=S*，转不骤1。

图常量是指根据图的某个性质定义的函数，即同构图将具有相同的函数值。

注：如果f 是图常量，而f(G) ≠f(H)，则图G于图H不同构。

用来说明图是否同构的一些量：结点个数连通分量个数边数度序列具有给定唯一度数结点对间的测地线长度图中的最长路具有唯一度数结点的邻接点的度基本定理定理3.1 设S是由以上算法得到的序列，那么当且仅当S'是可绘图序列时，S是可绘图序列。

大一离散数学知识点总结笔记离散数学是计算机科学和信息技术等领域的基础学科，它主要研究离散对象以及离散结构及其关系。

以下是本文对大一离散数学的知识点总结。

1. 集合论（Set Theory）- 集合的定义和表示方法- 集合间的运算：并、交、差、对称差- 集合的基本性质：幂集、空集、全集- 集合的相等和包含关系- 集合的基数和无穷集合2. 命题逻辑（Propositional Logic）- 命题的定义和符号表示- 命题的逻辑运算：非、合取、析取、条件、双条件- 命题之间的等价和蕴含关系3. 谓词逻辑（Predicate Logic）- 一阶逻辑的基本概念：谓词、量词、项、公式 - 一阶逻辑的语义：解释、真值- 一阶逻辑的语法：公式的语法规则- 命题逻辑与谓词逻辑的比较4. 证明方法与技巧（Proof Methods and Techniques） - 直接证明与间接证明- 分情况讨论和归纳法- 反证法和递归法- 等价变换和代入法5. 计数原理（Counting Principles）- 乘法原理和加法原理- 排列和组合：全排列、循环排列、组合数- 二项式系数和三角形数- 鸽笼原理和抽屉原理6. 图论（Graph Theory）- 图的基本概念：顶点、边、路径、环- 图的存储结构：邻接矩阵、邻接链表- 图的遍历算法：深度优先搜索、广度优先搜索- 最短路径算法：Dijkstra算法、Floyd-Warshall算法7. 关系代数与关系数据库（Relational Algebra and Relational Databases）- 关系代数的基本运算：选择、投影、并、差、笛卡尔积- 关系数据库的基本概念：关系模型、关系实例、关系模式 - 关系数据库查询语言：结构化查询语言（SQL）- 范式理论和函数依赖8. 有限状态自动机（Finite State Automata）- 自动机的定义和表示：状态、转移函数、初始状态、接受状态- 有限状态自动机的类型：确定性有限状态自动机（DFA）、非确定性有限状态自动机（NFA）- 正则表达式与有限状态自动机的等价性- 有限状态自动机的应用：词法分析、编译原理以上是大一离散数学的主要知识点总结，希望对你的学习有所帮助。

图论介绍（GraphTheory）1 图论概述1.1 发展历史第⼀阶段：1736：欧拉发表⾸篇关于图论的⽂章，研究了哥尼斯堡七桥问题，被称为图论之⽗1750：提出了拓扑学的第⼀个定理，多⾯体欧拉公式：V-E+F=2第⼆阶段（19~20世纪）：1852: Francis Guthrie提出四⾊问题1856: Thomas P. Kirkman & William R.Hamilton研究了哈密尔顿图1878: Alfred Kempe给出给出四⾊定理证明1890: 希伍德（Heawood）推翻原有四⾊定理证明1891: 彼得森（Petersen 丹麦）给出关于图论的理论知识的第⼀篇论⽂1936: 哥尼格(Dénes Kőnig Hungarian), 写出第⼀本图论专著《有限图与⽆限图的理论》，图论成为了⼀门独⽴学科第三阶段（现代图论）：1941: F. P. Ramsey开创 Extremal graph theory1959: Erd˝os and Rényi 引⼊随机图理论（边的存在的概率为p）1976: Kenneth Appel & Wolfgang Haken使⽤计算机最终证明了四⾊问题1.2 参考教材Graph Theory with Application - J.A. Bondy and U.S.R. Murty, Elsevier, 1976《图论及其应⽤》经典教材，吴望名译，有电⼦版Graph theory - J.A. Bondy and U.S.R. Murty, Springer, 2008《图论》GTM244，可以认为是 “Graph Theory with Application” 的第⼆版，推荐教材Graph Theory, 5th - Reinhard Diestel, Springer, 2017《图论》GTM173，有电⼦版Introduction to Graph Theory, 2nd- Douglas B. West, 2017⼊门教材2 图的初步知识（注：⼀般考虑simple graph (no graph loops or multiple edges), 且阶⼤于等于2）2.1 不规则图Definition: 所有顶点的度都不同的图叫不规则图 (irregular graph)Definition: 只有⼀对顶点的度相同的图叫⼏乎不规则图 (almost irregular graph)Theorem:1）不规则图不存在2）恰好存在两个阶数相同的⼏乎不规则图，且互为补图（顶点相同，边合起来是完全图）3）对于任意最⼤值为n的正整数集合，存在n+1阶的图，使其顶点数正好等于这些整数（以上结论不适⽤于多重图和加权图）2.2 正则图Definition: 所有顶点的度为r的图叫 r-正则图 (r-regular graph)e.g. 单连通的0-regular是单个点，单连通的1-regular是⼀条边的图，单连通的2-regular是⼀个圈，单连通的3-regular称为⽴⽅图Theorem: n阶r正则图存在，只要r, n不都是奇数，且r<=n-1常⽤正则图：Kn: n阶完全图，r = n-1Cn: n(n>=3)阶圈， r = 2Qr: n=2^r阶的超⽴⽅体(r-cube)Kr,r: n=2r阶的⼆分图2.3 ⼆分图（bipartite graph）Definition：顶点被分为两个集合，所有边只在两个集合之间连接的图叫⼆分图Theorem：图G是⼆分图\Leftrightarrow G中⽆奇圈2.4 ⼦图图G，⼦图（subgraph）Hsubgraph ---> spanning subgraph---> induced subgraph ---> vertex-delete subgraphspanning subgraph: ⽣成⼦图，H和G的顶点相同induced subgraph: 诱导⼦图，H = G[S] (从图中去除1个或多个顶点)vertex-delete subgraph: 去顶点⼦图，从图中去除1个顶点Theorem：任意图都可以表⽰为某个正则图的导出⼦图未解问题：给定某⼀图G的所有去顶点⼦图，是否能够重构出唯⼀的图G（同构意义上是唯⼀的）？2.5 距离Definition：连通图（connected），由多个连通分⽀（component）构成的图为不连通图（disconnected）G-v ⽐ G有更多的连通分⽀，则点v称为G的割点（cut-vertex）G-e ⽐ G有更多的连通分⽀，则边e称为G的桥（bridge）Theorem:连通图G，e是桥\Leftrightarrow e不属于G的任何⼀个圈\Leftrightarrow存在顶点u，v，使得任意路径u-v的路径经过e连通图G，w是割点\Leftrightarrow存在顶点u，v，使得任意路径u-v的路径经过wDefinition：点u, v之间的距离（distance）：u,v之间最短路径的长度d(u,v)点u的离⼼率（eccentricity）：u 与其它点的最⼤距离\epsilon(u)=\max\limits_v d(u,v)最⼩离⼼率为图的半径（radius），达到最⼩离⼼率的点为中⼼点（central vertex）最⼤离⼼率为图的直径（diameter），达到最⼤离⼼率的点为边缘点（peripheral vertex）2.6 TreeDefinition：不包含圈的连通图为树（Tree）Theorem：图G是树\Leftrightarrow G中任意两个顶点都有且只有⼀条连通路径n阶树有n-1条边在G内添加任意⼀条边，就会形成⼀个回路。

图论中的饱和安排双边会议组合问题作者：甘伟雄来源：《读写算》2012年第51期【摘要】图论〔Graph Theory〕是数学的一个分支，有着相当广泛的应用。

随着社会分工的细化，利用图论参与管理方面的研究有着广阔的天地。

饱和安排双边会议组合问题，就是在一个复杂的关系网中，需要梳理出各种双边关系，从而进行饱和会场安排。

比如参加一个系统工程小组讨论会，各小组间需要单独讨论，形成会议结果。

在同一时间段最大安排的会议数，就是饱和性问题。

研究这类问题涉及的领域广泛，具有极其高的应用价值。

本文应用图论知识，通过例子具体说明和探讨如何实现饱和安排双边会议组合问题，进行算法研究。

【关键词】图论二维表格饱和安排算法研究1.问题的提出图论极有趣味性和实用性，从逻辑上来讲它是组合数学的一个重要分支。

虽然图论表面上研究点和线的学问，但其理论的应用领域十分广阔，已经超出了数学和计算机应用学科。

还涵盖了社会学、交通管理、电信领域，管理研究等。

图论所研究的内容也非常广泛。

例如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。

探讨图论中的饱和安排双边会议组合问题，就是要利用图论解决生活中的现实问题。

比如ABCDEFG分别代表一个专业小组，要进行交叉讨论技术问题，而每一个小组的作用和地位不同，有些小组和其他小组的关系比较复杂，比如下图：图1图中的边代表两小组需要技术会议，如果全部会议需要规定的时间内完成，每一个时间段每一个小组只能安排一次会议，比如AC会议。

这就需要能解决饱和安排的算法来完成。

具体说来有以下几个方面的考虑：1.边的两头一起参加会议，而且只能一次。

比如AC会议结束后，不再安排AC会议了。

2.边的两头在同一时间段只能出现一次。

比如上午开了AC，BD，上午就不能出现AD。

3.能得出最短时间完成全部会议，也就是饱和状态的算法研究。

2.算法的研究单从图1很难找出内在的逻辑联系和同步异步的关系，我们可以把图1转换为二维表格形式。

图论课程介绍
课程代码:82905000
课程名称:图论
英文名称:Graph Theory
学分：2 修读期：循环开设
授课对象：理科本科生各专业
课程主任：宋慧敏，副教授，理学博士
课程简介：图论是近二十年来发展十分迅速，应用比较广泛的一个新兴的数学分支。

本课程旨在介绍图论的基础概念、理论、算法及其应用。

学习图论，不仅帮助学生
有效地采用它的成果与方法解决实际问题，还可以提高学生思考问题和解决问
题的能力。

实践教学环节：无
课程考核：
课程最终成绩=平时成绩*30%+期末考试成绩*70%；
平时成绩包括小论文、读书报告、作业成绩等情况；
期末考试采取开卷考试
指定教材：
王树禾.《图论》.北京:科学出版社,2004年1月,第一版.
参考书目：
[1] 王朝瑞.《图论》.北京:北京理工大学出版社,2001年12月,第三版.
[2]J. A. Bondy , U.S.R. Murty. 《Graph Theory with Application》.London: The Macmillan Press Ltd,1976年,第1版.。

第一章 图形理论图形理论有明确的起始点，由瑞士数学家尤拉(Leonhard Euler, 1707-1783)于1736年发表的论文开始。

其研究的主要论点，乃在于解决当时的热门问题，即有名K önigsgerg 的七桥问题。

1.1 定义与例题定义1.1：令 V 为非空集合，且E V V ⊆⨯. 序对(),V E 称为(V 上)有向图(directedgraph or digraph)，其中 V 为顶点(vertex)或节点(node)的集合，E 为边(edge)的集合。

我们记(),G V E =表示此图形。

图1.1为{}, , , , V a b c d e =上有向图的例子，其中()()()(){}, , , , , , , E a a a b a d b c =。

边的方向由边上的有向箭头表示，如图所示对任意边，如(), b c ，我们说此边接合(incident)顶点, b c ；称b 邻接至(adjacent to) c ；或c 邻接自(adjacent from) b 。

此外， b 称为边的原点(origin)或源点(source)， c 称为终点(terminus or terminating vertex)。

边(), a a 为一个循环(loop)， 且顶点e 不与任何边接合，称为孤立点(isolated)。

若不考虑边的方向，此图称为无向图(undirected)。

定义1.2：令, x y 为无向图(), G V E =的顶点(不一定相异)。

G 中的X Y -路(x y -walk)是指选自G 的顶点及边的有限交错序列。

01122311,,,,,,...,,,,n n n n x x e x e x e e x e x y --==其中由顶点 1x 开始，终止于顶点y ，n 个边{}1,,1i i i e x x i n -=≤≤路的长度(length)是指该条路的边数n 。

漫谈图论图论〔Graph Theory〕是数学的一个分支，它以图为研究对象。

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

本期周末讲坛邀请到数学与计算科学学院的丁超老师，带领我们走进数学的世界，以生动浅显的方式谈谈图论的秘密。

丁超老师以图论简史开始了本期讲座。

他说，图论属于应用数学范畴，像中学时我们学到的排列组合就是图论的一种。

它与我们的生活有着千丝万缕的联系，通过它能解决生活中遇到的很多问题。

丁老师向同学们介绍了图论的开创鼻祖“哥尼斯堡七桥问题”：普雷格尔河横穿城堡，河中有两个小岛，共有七座桥连接两岸和小岛。

哥尼斯堡人在寻找一条路线从某点出发经过每个桥一次回到出发点。

当时的很多人都争相思考，却都无果。

最后，欧拉将其概括为数学模型，“七桥”问题变为“一笔画”问题，证明了该问题无解。

丁老师介绍：“图论的历史发展一直很缓慢，近五十年随着计算机技术的发展图论才飞速发展起来。

”像著名的“四色猜想”，即对地图中的地区着色，只需四种颜色就能保证每两个相邻的地区颜色不同。

该问题1852年由伦敦大学学生Francis Guthrie提出，1879年A.B.Kempe 宣布了一个“证明”。

而在11年后即1890年，P.J.Heawood 发现了Kempe证明中的错误，称其方法只能证明“五色定理”。

该理论最后虽被计算机证明出来，但人工计算仍是一个世界难题。

丁老师幽默地说：“我劝初学者不要轻易去接触它。

”而诸如“欧拉图”和“中国邮递员问题”等，则是与生活息息相关的数学问题，讲座现场丁老师对其进行了简单的讲解和证明，并画图帮助同学们理解。

其中“中国邮递员问题”更是中国图论研究的一大进展，1962年由中国组合数学家管梅谷教授提出。

丁老师强调：“中国对图论研究贡献太少，是一大遗憾！”为了使同学们更好地理解图论的价值，丁老师介绍了旅行售货员问题、货郎担问题、相识问题、Ramsey数和握手问题等贴近生活、丰富而有趣的经典图论问题，在场同学纷纷积极地参与其中，全神贯注听着丁老师的讲解。