下载文档原格式
图论与网络流理论（Graph Theory and Network Flow Theory）高随祥中科院研究生院专业基础课学时/学分：60/3本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。
主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。
为学习者将来从事有关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具。
内容提要第一章 图的基本概念图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。
路、圈与连通图；最短路问题。
树及其基本性质；生成树；最小生成树。
第二章 图的连通性割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。
第三章 匹配问题匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。
第四章 欧拉图与哈密尔顿图欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。
第五章 支配集、独立集、覆盖集与团支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。
第六章图的着色问题点着色；边着色；平面图；四色猜想；色多项式；色数的应用。
第七章网络流理论有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。
主要参考书[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。
[2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。
[3] 蒋长浩，图论与网络流，中国林业出版社，2001。
《离散数学》课后习题答案《离散数学》简介1、集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数2、图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用3、代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4、组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理5、数理逻辑部分：命题逻辑、一阶谓词演算、消解原理离散数学被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。
教学方式以课堂讲授为主，课后有书面作业、通过学校网络教学平台发布课件并进行师生交流。
《离散数学》学科内容随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。
离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。
由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。
离散数学是传统的逻辑学，集合论(包括函数)，数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数(包括代数系统，群、环、域等)，布尔代数，计算模型(语言与自动机)等汇集起来的一门综合学科。
离散数学的应用遍及现代科学技术的诸多领域。
离散数学也可以说是计算机科学的基础核心学科，在离散数学中的有一个著名的典型例子-四色定理又称四色猜想，这是世界近代三大数学难题之一，它是在1852年，由英国的一名绘图员弗南西斯格思里提出的，他在进行地图着色时，发现了一个现象，“每幅地图都可以仅用四种颜色着色，并且共同边界的国家都可以被着上不同的颜色”。
信息学竞赛中的的最小点覆盖与最大独立集信息学竞赛中的最小点覆盖与最大独立集在信息学竞赛中，图论是一个重要的知识点，其中最小点覆盖和最大独立集是经常被提及的概念。
一、最小点覆盖最小点覆盖是指在一个无向图中，选取最少的顶点，使得每条边至少有一个端点被选中。
换句话说，最小点覆盖是指选取尽可能少的顶点，使得这些顶点的邻接边覆盖了整个图的边。
1. 最小点覆盖的应用在信息学竞赛中，最小点覆盖通常用于解决资源分配、任务调度等问题。
例如，一个工厂有多个生产任务需要分配给不同的机器，每个任务需要的机器不同。
在这种情况下，我们可以将任务看作图中的边，机器看作图中的顶点，通过求解最小点覆盖，来确定最少需要多少台机器可以执行所有的任务。
2. 最小点覆盖的算法求解最小点覆盖的算法有多种，其中一种常用的算法是匈牙利算法（Hungarian Algorithm）。
该算法通过不断寻找增广路径，来找到最大匹配，从而得到最小点覆盖。
二、最大独立集最大独立集是指在一个无向图中，选取最多的顶点，使得这些顶点之间没有边相连。
换句话说，最大独立集是指选取尽可能多的顶点，使得这些顶点相互之间不相连。
1. 最大独立集的应用在信息学竞赛中，最大独立集通常用于解决资源分配、任务调度等问题的对偶情况。
例如，一个工厂有多个机器，每个机器可以执行一个任务。
在这种情况下，我们可以将机器看作图中的顶点，任务看作图中的边，通过求解最大独立集，来确定最多可以执行多少个任务。
2. 最大独立集的算法求解最大独立集的算法也有多种，其中一种常用的算法是使用动态规划。
该算法通过构建一个大小与顶点数相等的数组，来记录每个顶点所对应的最大独立集的大小。
通过不断更新数组中的值，最终可以得到最大独立集的大小。
三、最小点覆盖与最大独立集的关系最小点覆盖和最大独立集是图论中互为对偶的概念。
在一个无向图中，最小点覆盖的顶点数与最大独立集的顶点数之和等于图的顶点数。
这可以通过反证法来证明：假设一个无向图中最小点覆盖的顶点数为 k，最大独立集的顶点数为 m，图的顶点数为 n。
精选全文完整版可编辑修改离散数学教学大纲一、教学目标本课程的教学目标是：1．学习和掌握离散型关系结构的构成及分析方法，包括：集合论的主要内容：集合的基本概念、二元关系、函数、自然数和基数等；图论的主要内容：图的基本概念、欧拉图与哈密尔顿图、树、图的矩阵表示、平面图、图的着色、支配集、覆盖集、独立集与匹配、带权图及其应用等；2. 学习和掌握离散型代数结构的构成、性质和分析方法，熟悉半群、群、环、域、格、布尔代数等有着重要应用背景的代数模型；3. 学习和掌握组合配置的存在性证明和计数方法，并用于离散结构的性质分析。
4. 学习和掌握命题逻辑、一阶谓词逻辑的基本概念和推理方法。
5. 能够理论联系实际，用上述离散数学的描述工具和分析方法对实践中的离散系统进行建模和分析。
6. 通过严谨证明及正确逻辑推理的训练，进一步培养学生的抽象思维、计算思维能力和专业素质。
二、教学内容1．集合（教材第一章）●引言●预备知识（命题逻辑）●预备知识（一阶谓词逻辑）●集合的概念和集合之间的关系●集合的运算●基本的集合恒等式2．二元关系（教材第二章）●有序对与卡氏积●二元关系●关系的表示和关系的性质●关系的幂运算和闭包●等价关系和划分●序关系3．函数（教材第三章）●函数的基本概念、性质、合成、反函数4．自然数（教材第四章）●自然数的定义●自然数的性质5．基数（教材第五章）●集合的等势、有穷集合与无穷集合●基数和基数的比较与运算6．图（教材第七章）●图的基本概念●通路与回路●无向图和有向图的连通性●无向图的连通度7．欧拉图与哈密顿图（教材第八章）●欧拉图●哈密顿图8．树（教材第九章）●树9．图的矩阵表示（教材第十章）●图的矩阵表示10．平面图（教材第十一章）●平面图的基本概念●欧拉公式与平面图的判断●平面图的对偶图与外平面图●平面图与哈密顿图11．图的着色（教材第十二章）●点着色和色多项式●平面图着色和边着色12．支配集、覆盖集、独立集与匹配（教材第十三章）●支配集、点覆盖集、点独立集●边覆盖数与匹配●二部图中的匹配13．带权图及其应用（教材第十四章）●中国邮递员问题和货郎问题14. 代数系统（教材第十五章）●二元运算及其性质●代数系统、子代数和积代数●代数系统的同态与同构●同余关系与商代数15. 半群与独异点（教材第十六章）●半群与独异点16 . 群（教材第十七章）●群的定义和性质、子群●循环群、变换群与置换群●群的分解、正规子群与商群、群的同态与同构17. 环与域（教材第十八章）●环与域18. 格与布尔代数（教材第十九章）●格的定义和性质、子格、格同态与直积●模格、分配格、有补格与布尔代数19. 组合存在性定理（教材第二十章）●鸽巢原理和Ramsey定理20. 基本的计数公式（教材第二十一章）●两个计数原则、排列组合●二项式定理与组合恒等式●多项式定理21. 组合计数方法（教材第二十二章）●递推方程的公式解法●递推方程的其他求解方法●生成函数的定义和性质●生成函数、指数生成函数及应用●Catalan数与Stirling数22. 组合计数定理（教材第二十三章）●包含排斥原理与对称筛公式●Burnside引理与Polya定理23. 命题逻辑（教材第二十六章）●引言●命题和联结词●命题形式和真值表●联结词的完全集●推理形式●命题演算自然推理形式系统N●命题演算形式系统P●N与P的等价性●赋值与等值演算●命题范式●可靠性、和谐性与完备性24. 一阶谓词逻辑（教材第二十七章）●一阶谓词演算的符号化●一阶语言●一阶谓词演算形式系统NL●一阶谓词演算形式系统KL●NL与KL的等价性●KL的解释与赋值●KL的可靠性与和谐性●KL的和谐公式集三、教学方式以课堂讲授为主，辅以作业和练习，并配备助教对作业进行批改。
单元12.1 支配集、点覆盖集、点独立集第二编图论第十二章支配集、覆盖集、独立集与匹配13.1 支配集、点覆盖集、点独立集内容提要•支配集•点独立集•点覆盖集•团•支配数，点独立数，点覆盖数，团数之间的关系支配集•G=<V,E> , e=(u,v) ⇔u支配v ⇔v支配u •支配集: V*⊆V, ∀v∈V-V*, ∃u∈V*, u支配v•极小支配集: 真子集都非支配集的支配集•最小支配集: 顶点数最少的支配集•支配数: γ0(G) = 最小支配集的顶点数支配集举例•星形图S n: {v0}, {v1,v2,…,v n-1}, γ0(S n)=1•轮图W n: {v0}, {v1,v3,v5…,v n-2}, γ0(W n)=1v1v5 v2v0v4 v3定理13.1•无向图G无孤立点, V1*是极小支配集, 则存在V2*也*⋂V2*=∅.是极小支配集, 且V1•说明: 支配集要包含所有孤立点定理13.1证明•证:(1)V1*是极小支配集⇒V-V1*也是支配集.*, ∀v∈V-V1*, (u,v)∉E,V1*-{u}还是支反证: 否则, ∃u∈V1*极小性矛盾.配集, 与V1(2)V-V 1*是支配集⇒V-V1*中有子集是极小支配集, 设为V2*.显然V*⋂V2*=∅. #1独立集•无向图G=<V,E>•独立集: V*⊆V, ∀u,v∈V*, u与v不相邻•极大独立集: 真母集都非独立集的独立集•最大独立集: 顶点数最多的独立集•点独立数: β0(G) = 最大独立集的顶点数v 1 v 1 独立集举例• {v 0}, {v 1,v 4}, {v 1,v 3,v 5}, 0=3v 1v 5 v 0 v 2v 4 v 3定理13.2•无向图G(无孤立点),V*是极大独立集 V*是极小支配集•说明: 极大独立集要包含所有孤立点“无孤立点”的条件可以去掉定理13.2证明•证: (1) V*是极大独立集⇒V*也是支配集.(反证) 否则, ∃v∈V-V*, ∀u∈V*, (u,v)∉E, V*⋃{v}还是独立集, 与V*极大性相矛盾.(2) V*是极小支配集.(反证) 否则, ∃u∈V*, V*-{u}是支配集, 则∃v∈V*, (u,v)∈E, 与V*是独立集相矛盾. #定理13.2补充推论•无向图G, 则γ0≤β0#v1v5v3定理13.2逆命题反例•极小支配集不一定是(极大)独立集–{v2,v3}是极小支配集–{v2,v3}不是独立集, 当然不是极大独立集v1 v2 v3 v4团•无向图G=<V,E>•团: V*⊆V, G[V*]是完全子图•极大团: 真母集都不是团的团•最大团: 顶点数最多的团•团数: ν0(G) = 最大团的顶点数v0v2团举例•{v0,v1,v2}, {v1,v2}, {v1}, 0=3v1定理13.4•无向图G,V*是G的团⇔V*是G的独立集. # •推论: 无向图G,(1) ν0(G)=β0(G)(2) V*是G的极(最)大团⇔V*是G的极(最)大独立集. #点覆盖•无向图G=<V,E>•点覆盖: V*⊆V, ∀e∈E, ∃v∈V*, v关联e –说明: 点覆盖要含所有带环点•极小点覆盖: 真子集都非点覆盖的点覆盖–说明: 极小点覆盖不含任何孤立点•最小点覆盖: 顶点数最少的点覆盖•点覆盖数: α0(G) = 最小点覆盖的顶点数v 5 v 0v 2 点覆盖举例• {v 0,v 1,v 3,v 5}, {v 1,v 2,v 3,v 4,v 5,v 6}, 0=4v 1v 3补充定理•无孤立点(连通)图中, 点覆盖是支配集γ0≤α0•点覆盖加所有孤立点是支配集v1v5v0v3•极小点覆盖不一定是极小支配集–{v0, v1, v3, v5} 是极小点覆盖–{v1, v3, v5 } 是极小支配集v1v5v0v3•支配集不一定是点覆盖–{v1,v4} 是支配集–{v1,v4} 不是点覆盖v1定理13.3•无向图G无孤立点, V*⊂V,V*是点覆盖⇔V-V*是独立集.•证: (⇒)(反证) 否则, ∃u,v∈V-V*, (u,v)∈E,则V*不是点覆盖, 矛盾.(⇐) V-V*是独立集, ∀(u,v)∈E,(u,v)∈E ⇒⌝( u∈V-V* ∧v∈V-V* )⇔u∈V* ∨v∈V* ⇒V*是点覆盖. #•无向图G无孤立点,V*是极(最)小点覆盖⇔V-V*是极(最)大独立集α0 + β0 = n #α0, β0, γ0, ν0 之间关系•α0+β0=n (无孤立点, 定理13.3推论).•γ0≤β0(定理13.2补充推论)•γ0≤α0(无孤立点, 补充定理)•ν0(G)=β0(G) (定理13.4推论)•α0, β0, ν0都是难解的(intractable, hard)–目前都没有多项式时间算法–与哈密顿回路问题, 着色问题等“一样难”例13.1•求全体极小支配集, 极小点覆盖, 极大独立集cd baa例13.1: 全体极小支配集c• ∏v ∈V (v+∑u ∈Γ(v)u)db= (a+b)(b+a+c+d)(c+b+d)(d+c+b) = ac+ad+b.(幂等: a+a=a, a •a=a, 逻辑加乘)• {a,c}, {a,d}, {b}是全体极小支配集. • γ0=1.a例13.1: 极小点覆盖c• ∏(u,v)∈E (u+v)db= (a+b)(b+c)(b+d)(c+d) = bc+bd+acd.(幂等: a+a=a, a •a=a, 逻辑加乘)• {b,c}, {b,d}, {a,c,d}是全体极小点覆盖. • α0=2.例13.1: 极大独立集cd b •G无孤立点,a V*是极小点覆盖⇔V-V*是极大独立集.•{b,c}, {b,d}, {a,c,d} 是全体极小点覆盖,•{a,d}, {a,c}, {b} 是全体极大独立集.•β0=2. #小结•支配集，支配数γ0•点独立集，点独立数β0•点覆盖集，点覆盖数α0•团，团数ν0•α0, β0, γ0, ν0之间关系。
1. 图G如图所示，完成下列题目：（1）求支配数γ0，G中有非最小支配集的极小支配集吗？（2）求点覆盖数α0，G中有非最小点覆盖集的极小点覆盖集吗？（3）求点独立数β0（4）求匹配数β1，G能有完美匹配吗？为什么？（5）求边覆盖数α1提示参看支配集、点覆盖集、边覆盖集、点独立集、匹配、定理18.2及推论和定理18.3。
答案（1）容易看出，它没有一个顶点组成的支配集，而有两个顶点组成的支配集。
例如V*={V1,V3}为支配集。
显然，它是最小的，因而γ0=|V*|=2。
事实上，G中含8个极小支配集:{V1,V2}，{V1,V3}，{V1,V4}，{V1,V5}，{V2,V3}，{V3,V4}，{V3,V5}，{V2,V4,V5}其中，{V2,V4,V5}是非最小支配集的极小支配集。
（2）类似地，先求最小点覆盖集。
容易看出V*={V1,V3}为最小点覆盖集。
所以α0=2。
经过观察发现，G只有两个极小点覆盖集，除V*外还有{V2,V4,V5}，它是非最小点覆盖集的极小点覆盖集。
（3）G只有两个极大点独立集：{V1,V3}和{V2,V4,V5}，其中后者是最大点独立集，所以β0=3 另外，可由定理18.2及推论求解：α0+β0=5 而α0=2，所以β0=3。
（4）G的极大匹配全是最大匹配，有6个：{a，c}，{a，f}，{b，d}，{b，f}，{c，e}，{d，e}所以β1=2。
显然，若无向图G具有完美匹配，则G的阶数n为偶数。
可是，本题中n=5，故G无完美匹配。
（5）由定理18.3容易求出G的6个最小边覆盖集：{a，c，e}，{a，c，f}，{b，d，e}，{b，d，f}，{c，d，e}，{a，b，f}α1=5-β1=5-2=32. 求彼得松图中的γ0，α0，β0，α1，β1。
提示参看支配集、点覆盖集、边覆盖集、点独立集、匹配、定理18.2与18.3。
答案γ0=3，β1=5，α1=5，β0=4，α0=6。
