你的进度
0/ 28 节已标记完成
下一节: 树与连通性
完成记录保存在此浏览器中。
这门课在网上
MATH3260 笔记里的内容
数字只算这门课 28 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 90 · 定义 56 · 反例 32 · 概念视角 20 · 证明透视 30
第 1 章 · 6 节
树与连通性
用路径和桥理解有限树及其边数。
- 1.1
树与连通性
以路径和桥理解有限树及其边数。
- 1.2
二分染色与奇圈证书
证明奇圈判据,并构造染色或反证。
- 1.3
基本圈与偶度边集
从生成森林构造循环空间并计算其元素数目。
- 1.4
距离、直径与树的中心
寻找使最远距离最小的顶点,并证明为什么逐轮同时删除叶顶点能找出树的中心。
- 1.5
标号树的 Prüfer 编码与 Cayley 公式
从编码、解码算法及其不变量出发,完整证明 Prüfer 编码给出双射,并推导 Cayley 公式和指定度数序列的树计数公式。
- 1.6
加权拉普拉斯矩阵与生成树计数
由关联矩阵的子式证明加权矩阵–树公式,计算完全图与完全二部图的生成树数目,并推导精确的边包含概率与删除–收缩恒等式。
第 2 章 · 2 节
Euler 遍历
用闭迹拼接证明偶数度判别法。
- 2.1
欧拉回路与奇偶性
用闭迹拼接证明偶数度判别法。
- 2.2
欧拉迹与欧拉回路:奇偶条件和构造
证明每条边恰走一次的度数判据,并以拼接闭迹的方法构造回路。
第 3 章 · 2 节
平面性与染色
在平面嵌入中计数面,并用所得界证明非平面性。
- 3.1
平面图、欧拉公式与染色
在平面嵌入中计数面,并用所得界证明非平面性。
- 3.2
细分与非平面性证据
识别细分后的障碍,并证明它们为何能证实图非平面。
第 4 章 · 2 节
Hamilton 条件
证明保证哈密顿圈存在的度数条件,并区分充分条件和必要条件。
- 4.1
哈密顿圈与度数条件
证明保证哈密顿圈存在的度数条件,并区分充分条件和必要条件。
- 4.2
哈密顿闭包与度序列判据
证明度和加边引理、与加边顺序无关的闭包,以及完整的单调度序列条件,并给出构造性的圈恢复方法和否定性检验的明确局限。
第 5 章 · 2 节
有向图
区分弱连通与强连通,并证明有向欧拉回路判别法。
- 5.1
有向图、可达性与欧拉回路
区分弱连通与强连通,并证明有向欧拉回路判别法。
- 5.2
竞赛图与有向路径
构造有向哈密顿路径,并理解竞赛图中的圈与可达性。
第 6 章 · 2 节
匹配
通过交错路径证明匹配的最优性,推出 Hall 条件,并由同一次搜索构造最小顶点覆盖。
- 6.1
增广路径、Hall 定理与 König 定理
通过交错路径证明匹配的最优性,推出 Hall 条件,并由同一次搜索构造最小顶点覆盖。
- 6.2
奇分支、Tutte 条件与匹配亏量
通过饱和障碍结构证明一般图的完美匹配判别准则,推导未匹配顶点个数的精确公式,并解释为什么奇分支取代了二部图中的邻域。
第 7 章 · 1 节
流与割
证明增广流算法的正确性与整数最大流最小割定理,解释反向残量弧,并由二部图匹配恢复匹配与覆盖的证书。
- 7.1
残量路径、整数流与最小割
证明增广流算法的正确性与整数最大流最小割定理,解释反向残量弧,并由二部图匹配恢复匹配与覆盖的证书。
第 8 章 · 2 节
图的表示
表示有限简单图并比较重新标号后的结构。
- 8.1
图的表示与同构
表示有限图,证明重新标号保留的信息,并区分不变量与同构证书。
- 8.2
可图化的度序列与 Havel–Hakimi 定理
判断有限整数列能否成为带标号简单图的度列,并完整证明 Havel–Hakimi 定理及其构造算法。
第 9 章 · 3 节
连通性
区块、割点与 Menger 型连通性定理。
- 9.1
块与块割森林
把割点与允许重叠的稳健部分组织成森林,读出每一次单顶点分离。
- 9.2
通过 Menger 定理研究边连通度与顶点连通度
利用整数流证明有限无向图中两种路径–分隔集等式,并明确说明抵消、流分解以及端点不相邻这一假设。
- 9.3
全局顶点连通度与扇引理
将端点不相邻的 Menger 定理推广到 k-连通图中的所有顶点对,证明扇引理及其逆命题,并区分度、边韧性与顶点韧性。
第 10 章 · 6 节
染色与极值图论
色多项式、边染色、Ramsey 与 Turán 型结果。
- 10.1
色多项式与删除–收缩
用容斥原理和删除–收缩计数正常染色,证明树、圈与割点公式,并从多项式系数中读出边数和三角形数。
- 10.2
二部图的边染色与交错修复
通过正则补全与构造性的双色修复两种方法,证明二部图边染色的最大度紧界,并讨论平行边、运行时间与奇圈障碍。
- 10.3
扇、双色修复与一般边染色上界
证明每个有限简单图都存在一种边染色,所用颜色数至多比最大度多一种。证明利用完整的扇不变量、交替路径的情形分析以及明确的实现代价。
- 10.4
退化度、收缩与平面图的五色定理
证明按退化序的染色,得到平面图的线性六染色构造,并通过收缩两个不相邻的邻点证明五色定理。
- 10.5
有限 Ramsey 界与随机染色
证明有限的二色与多色团保证、三角形的精确阈值以及基于第一矩的下界,并将普遍性保证、存在性结论与充分的概率检验区分开来。
- 10.6
无团极值图与均衡部分
证明排除团所需的精确整数边数阈值,包括完整的等号情形分类,并将其转移到独立数有界的最少边图上。