跳到正文

MATH3260

图论

树与连通性、Euler 图与 Hamilton 图、平面性与染色、有向图、匹配、流与割,以及极值图论,附证明及例题。

10 章 · 28 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 28 节已标记完成

下一节: 树与连通性

完成记录保存在此浏览器中。

这门课在网上

MATH3260 笔记里的内容

定理卡
90
定义
56
反例
32
概念视角
20
思想史
0
证明透视
30

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 28 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 90 · 定义 56 · 反例 32 · 概念视角 20 · 证明透视 30

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 28 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 6 节

树与连通性

用路径和桥理解有限树及其边数。

定理 24 · 定义 13反例 8视角 4证明透视 7

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    树与连通性

    以路径和桥理解有限树及其边数。

  2. 1.2

    二分染色与奇圈证书

    证明奇圈判据,并构造染色或反证。

  3. 1.3

    基本圈与偶度边集

    从生成森林构造循环空间并计算其元素数目。

  4. 1.4

    距离、直径与树的中心

    寻找使最远距离最小的顶点,并证明为什么逐轮同时删除叶顶点能找出树的中心。

  5. 1.5

    标号树的 Prüfer 编码与 Cayley 公式

    从编码、解码算法及其不变量出发,完整证明 Prüfer 编码给出双射,并推导 Cayley 公式和指定度数序列的树计数公式。

  6. 1.6

    加权拉普拉斯矩阵与生成树计数

    由关联矩阵的子式证明加权矩阵–树公式,计算完全图与完全二部图的生成树数目,并推导精确的边包含概率与删除–收缩恒等式。

第 2 章 · 2 节

Euler 遍历

用闭迹拼接证明偶数度判别法。

定理 5 · 定义 2反例 1视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    欧拉回路与奇偶性

    用闭迹拼接证明偶数度判别法。

  2. 2.2

    欧拉迹与欧拉回路:奇偶条件和构造

    证明每条边恰走一次的度数判据,并以拼接闭迹的方法构造回路。

第 3 章 · 2 节

平面性与染色

在平面嵌入中计数面,并用所得界证明非平面性。

定理 6 · 定义 5反例 3视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    平面图、欧拉公式与染色

    在平面嵌入中计数面,并用所得界证明非平面性。

  2. 3.2

    细分与非平面性证据

    识别细分后的障碍,并证明它们为何能证实图非平面。

第 4 章 · 2 节

Hamilton 条件

证明保证哈密顿圈存在的度数条件,并区分充分条件和必要条件。

定理 6 · 定义 3反例 2视角 1证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    哈密顿圈与度数条件

    证明保证哈密顿圈存在的度数条件,并区分充分条件和必要条件。

  2. 4.2

    哈密顿闭包与度序列判据

    证明度和加边引理、与加边顺序无关的闭包,以及完整的单调度序列条件,并给出构造性的圈恢复方法和否定性检验的明确局限。

第 5 章 · 2 节

有向图

区分弱连通与强连通,并证明有向欧拉回路判别法。

定理 9 · 定义 5反例 3视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    有向图、可达性与欧拉回路

    区分弱连通与强连通,并证明有向欧拉回路判别法。

  2. 5.2

    竞赛图与有向路径

    构造有向哈密顿路径,并理解竞赛图中的圈与可达性。

第 6 章 · 2 节

匹配

通过交错路径证明匹配的最优性,推出 Hall 条件,并由同一次搜索构造最小顶点覆盖。

定理 6 · 定义 3反例 2视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    增广路径、Hall 定理与 König 定理

    通过交错路径证明匹配的最优性,推出 Hall 条件,并由同一次搜索构造最小顶点覆盖。

  2. 6.2

    奇分支、Tutte 条件与匹配亏量

    通过饱和障碍结构证明一般图的完美匹配判别准则,推导未匹配顶点个数的精确公式,并解释为什么奇分支取代了二部图中的邻域。

第 7 章 · 1 节

流与割

证明增广流算法的正确性与整数最大流最小割定理,解释反向残量弧,并由二部图匹配恢复匹配与覆盖的证书。

定理 3 · 定义 2反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 7.1

    残量路径、整数流与最小割

    证明增广流算法的正确性与整数最大流最小割定理,解释反向残量弧,并由二部图匹配恢复匹配与覆盖的证书。

第 8 章 · 2 节

图的表示

表示有限简单图并比较重新标号后的结构。

定理 6 · 定义 7反例 3视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    图的表示与同构

    表示有限图,证明重新标号保留的信息,并区分不变量与同构证书。

  2. 8.2

    可图化的度序列与 Havel–Hakimi 定理

    判断有限整数列能否成为带标号简单图的度列,并完整证明 Havel–Hakimi 定理及其构造算法。

第 9 章 · 3 节

连通性

区块、割点与 Menger 型连通性定理。

定理 8 · 定义 8反例 3视角 2证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 9.1

    块与块割森林

    把割点与允许重叠的稳健部分组织成森林,读出每一次单顶点分离。

  2. 9.2

    通过 Menger 定理研究边连通度与顶点连通度

    利用整数流证明有限无向图中两种路径–分隔集等式,并明确说明抵消、流分解以及端点不相邻这一假设。

  3. 9.3

    全局顶点连通度与扇引理

    将端点不相邻的 Menger 定理推广到 k-连通图中的所有顶点对,证明扇引理及其逆命题,并区分度、边韧性与顶点韧性。

第 10 章 · 6 节

染色与极值图论

色多项式、边染色、Ramsey 与 Turán 型结果。

定理 17 · 定义 8反例 6视角 6证明透视 6

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 10.1

    色多项式与删除–收缩

    用容斥原理和删除–收缩计数正常染色,证明树、圈与割点公式,并从多项式系数中读出边数和三角形数。

  2. 10.2

    二部图的边染色与交错修复

    通过正则补全与构造性的双色修复两种方法,证明二部图边染色的最大度紧界,并讨论平行边、运行时间与奇圈障碍。

  3. 10.3

    扇、双色修复与一般边染色上界

    证明每个有限简单图都存在一种边染色,所用颜色数至多比最大度多一种。证明利用完整的扇不变量、交替路径的情形分析以及明确的实现代价。

  4. 10.4

    退化度、收缩与平面图的五色定理

    证明按退化序的染色,得到平面图的线性六染色构造,并通过收缩两个不相邻的邻点证明五色定理。

  5. 10.5

    有限 Ramsey 界与随机染色

    证明有限的二色与多色团保证、三角形的精确阈值以及基于第一矩的下界,并将普遍性保证、存在性结论与充分的概率检验区分开来。

  6. 10.6

    无团极值图与均衡部分

    证明排除团所需的精确整数边数阈值,包括完整的等号情形分类,并将其转移到独立数有界的最少边图上。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情