Ruiqy~

返回：0100 离散数学课程总目录 · 上一章：0111 图着色 · 下一章：0113 图论应用、习题课与课程总结 1、学习目标本章把图论中的“选点/选边”问题系统化：支配、覆盖、独立、匹配和边覆盖。核心目标是会在这些参数之间互相转化，尤其是Gallai 恒等式、Berge 定理、Hall 定理。 2、核心概念 概念 记号 定义 支配集 D 每个不在 D 中的顶点都与 D 中某点相邻 支配数 gamma0(G) 最小支配集大小 点覆盖 K 每条边至少有一个端点在 K 中 点覆盖数 alpha0(G) 最小点覆盖大小 点独立集 S 任意两点不相邻 点独立数 beta0(G) 最大点独立集大小 匹配 M 任意两条边不相邻 匹配数 beta1(G) 最大匹配大小 边覆盖 L 每个顶点都与 L 中某条边关联 边覆盖数 alpha1(G) 最小边覆盖大小 “极小/极大”说的是不能再删或不能再加，是局部性质；“最小/最大”说的是数量最少或最多，是全局最优。极小支配集不一定是最小支配集，极大匹配也不一定是最大匹配。 3、支配、独立、点覆盖 ...

返回：本科课程：疾风计划 1、课程定位数据结构是 408 主干入门的第一门课，也是 C++ 程序设计之后最适合继续补强的一门课。它关心的不是“语法怎么写”，而是数据如何组织、操作如何定义、算法为什么正确、复杂度如何估计。 项目 内容 课程 数据结构 教师 邓俊辉 院校 清华大学 资料来源 本地邓俊辉《数据结构》上、下视频与 PDF 课件 学习定位 408 主干入门，衔接算法设计、计算机系统、网络安全项目和后续刷题 笔记范围 0301~0312，对应 12 章课程内容 这组笔记按邓俊辉老师课程的 12 章整理：先搭总框架，再逐章复盘 ADT、实现、关键算法、复杂度、易错点和练习清单。后面真正跟视频学习时，可以在每章继续补截图、推导和代码实验。 2、学习主线 部分 章节 核心问题 后续连接 算法分析基础 Chap 1 如何度量算法效率，如何理解迭代、递归、动态规划和下界 408 算法复杂度、递归分析 线性结构 Chap 2-4 向量、列表、栈和队列如何支持不同访问模式 顺序表、链表、表达式求值、BFS 树与图 Chap ...

返回：0100 离散数学课程总目录 · 上一章：0110 平面图 · 下一章：0112 支配、覆盖、独立与匹配 1、学习目标本章对应刘田老师图着色部分，资料包括点着色、色多项式、平面图着色、面着色和边着色。核心目标是掌握色数、色多项式、四色问题、边色数这条线。 2、颜色标注 颜色 含义 粉色 必背结论 蓝色 概念名称 橙色 易错点 绿色 证明提示 3、点着色与色数点着色： 1给顶点染色，使相邻顶点颜色不同。 k-可着色表示可用不超过 k 种颜色完成点着色。色数： 1chi(G)=使 G 可着色的最小颜色数。 典型结果： 123456chi(K_n)=nchi(C_{2r})=2chi(C_{2r+1})=3树 T_n 的色数为 2（n>=2）chi(W_n)=4, n 偶数chi(W_n)=3, n 奇数 二部图判定： 1G 是 2-可着色图 <=> G 是二部图 <=> G 不含奇圈。 色数上界： 1chi(G) <= Delta(G)+1 Brooks 定理： 12n&g ...

返回：0100 离散数学课程总目录 · 上一章：0109 图的矩阵表示 · 下一章：0111 图着色 1、资料来源与学习目标本章对应刘田老师平面图部分，Auto_Tutor 中包含 10.1 到 10.5 的课件、习题课、习题十一和答案。核心目标是把“能否无交叉画图”转化为欧拉公式、面次数、禁用子图和对偶图的判断。 本章主线：平面嵌入 -> 面 -> 欧拉公式 -> 边数上界 -> 非平面判定。 2、颜色标注 颜色 含义 粉色 必背公式和判定定理 蓝色 核心概念 橙色 易错边界 绿色 证明线索 3、核心概念 概念 定义 平面图 已画在平面上，边只允许在公共端点相交的图 可平面图 存在某种平面嵌入的图 平面嵌入 把图画到平面上且没有非端点交叉 面 平面图中不含顶点和边的极大连通区域及其边界 外部面 面积无界的面 面次数 面边界长度，桥要在同一面边界上计两次 极大平面图 已是平面图，任意两个不相邻点之间加边都会破坏平面性 极小非平面图 非平面图，删任意一条边后变成平面图 4、欧拉 ...

返回：0100 离散数学课程总目录 · 上一章：0108 树 · 下一章：0110 平面图 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第九章，课件实际标题是“第十章 图的矩阵表示”。Auto_Tutor 中整理到的资料包括： 资料 内容 9.1 图的矩阵表示 有向图关联矩阵、无向图关联矩阵、基本关联矩阵、生成树判定、邻接矩阵、矩阵幂、可达矩阵、相邻矩阵、连通矩阵 009 习题与答案 习题 10.2、10.4，重点考察基本关联矩阵求生成树、邻接矩阵幂求通路与回路数量 本章的核心目标：把“图的结构问题”翻译成矩阵计算问题。关联矩阵服务于连通性和生成树，邻接矩阵服务于通路计数，可达矩阵和连通矩阵服务于可达性判断。 2、颜色标注 颜色 含义 粉色 必背定理、矩阵算法、习题直接使用的结论 蓝色 核心术语、矩阵名、图论对象 橙色 易错点、适用条件、下标方向 绿色 理解提示和操作步骤 3、章节主线 模块 本章要会什么 典型题型 关联矩阵 会按边和顶点写 M(D)、M(G) 判断度数、平行边、连通分 ...

返回：0100 离散数学课程总目录 · 上一章：0107 欧拉图与哈密顿图 · 下一章：0109 图的矩阵表示 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第八章。Auto_Tutor 中整理到的资料包括： 资料 内容 8.1 树 树、森林、树叶、分支点、树的六个等价定义、生成树、基本回路、基本割集、生成树计数、Cayley 公式 008 习题与答案 习题 9.2、9.6、9.11，重点考察握手定理、树的边数、森林边数上界、最大度与树叶数量 本章的核心目标：掌握树 = 连通 + 无圈这条主线，并能在“连通、无圈、边数 n-1、唯一路径、极小连通、极大无圈”之间自由切换。 2、颜色标注 颜色 含义 粉色 必背、必会证明、后续章节反复使用 蓝色 核心术语和定义 橙色 易错点、边界条件 绿色 理解提示和后续连接 3、章节主线 模块 本章要会什么 后续连接 树与森林 会用连通性和圈判定树/森林 图论基础 等价定义 会在六种树定义之间转换 证明题 树叶 会用握手定理证明非平凡树至少两片叶 ...

返回：0100 离散数学课程总目录 · 上一章：0106 图的基本概念、通路回路与连通性 · 下一章：0108 树 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第七章。Auto_Tutor 中整理到的资料包括： 资料 内容 7.1 欧拉图 欧拉通路、欧拉回路、欧拉图、半欧拉图、有向欧拉图、Fleury 算法、逐步插入回路算法 7.2 哈密顿图 哈密顿通路、哈密顿回路、哈密顿图、必要条件、Ore 条件、Dirac 条件、竞赛图 007 习题与答案 习题 8.4、8.7、8.13，重点考察任意行遍点、哈密顿必要条件和半哈密顿充分条件 本章的核心目标：区分欧拉与哈密顿。欧拉关注“每条边恰好走一次”，判定容易；哈密顿关注“每个顶点恰好经过一次”，判定困难，更多依赖必要条件和充分条件。 2、颜色标注 颜色 含义 粉色 必背、必会证明、后续章节反复使用 蓝色 核心术语和定义 橙色 易错点、边界条件 绿色 理解提示和后续连接 3、章节主线 模块 本章要会什么 后续连接 欧拉图 会用度数判定欧拉图 ...

返回：0100 离散数学课程总目录 · 上一章：0105 等势、基数、序数与集合论公理 · 下一章：0107 欧拉图与哈密顿图 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第六章。Auto_Tutor 中整理到的资料包括： 资料 内容 6.1 图的基本概念 图、无向图、有向图、简单图、度、握手定理、度数列、Havel 定理、图同构、子图、补图 6.2 通路与回路 通路、简单通路、初级通路、回路、圈、周长、围长、扩大路径法 6.3 无向图的连通性 连通关系、连通分支、距离、直径、二部图、强/单向/弱连通 6.4 无向图的连通度 点割集、边割集、割点、桥、点连通度、边连通度、Whitney 不等式、Menger 定理、块 006 习题与答案 习题 1、2、3、5、11、14、16、18、22、25，重点考察握手定理、补图、自补图、极大路径法、连通度和块 本章的核心目标：把图论的对象语言搭起来。先会数点、数边、数度，再会判断“走法”和“连通性”，后面的欧拉图、哈密顿图、树、平面图都会反复调用这些定义。 2、颜色标注 颜色 ...

返回：0100 离散数学课程总目录 · 上一章：0104 自然数的定义与性质 · 下一章：0106 图的基本概念、通路回路与连通性 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第五章。Auto_Tutor 中整理到的资料包括： 资料 内容 5.1 集合的等势、有穷集与无穷集合 等势、典型等势例子、Cantor 定理、有穷集、无穷集 5.2 基数和基数的比较运算 基数定义、优势/劣势、Schröder-Bernstein 定理、可数集、基数运算 5.3 集合论习题课 4-5 章 第四、五章习题复盘 5.3 序数和集合论公理 序数、连续统假设、ZF/ZFC 公理、罗素悖论 005 习题与答案 习题 2、5、11、12、补充题，重点考察等价类、等势、可数性和基数运算 本章的核心目标：分清基数和序数。基数回答“有多少”，靠双射匹配；序数回答“排第几、先后如何”，靠良序结构。 2、颜色标注 颜色 含义 粉色 必背、必会证明、后续章节反复使用 蓝色 核心术语和定义 橙色 易错点、边界条件 绿色 理解提示和后 ...

返回：0100 离散数学课程总目录 · 上一章：0103 函数与集合论习题课 · 下一章：0105 等势、基数、序数与集合论公理 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第四章。Auto_Tutor 中整理到的资料包括： 资料 内容 4.1 自然数的定义 Peano 系统、封闭、后继、归纳集、自然数集、后继函数、数学归纳法 4.2 自然数的性质 传递集、递归定理、加法、乘法、自然数上的序 004 习题与答案 习题 2、3、5、7，重点考察自然数作为集合、非零自然数是后继、传递集和递归定义出的单射 本章的核心目标：用集合论构造自然数。这里的 0,1,2,3,... 不再只是熟悉的数字，而是冯·诺依曼自然数：0=∅，1={0}，2={0,1}，3={0,1,2}。 2、颜色标注 颜色 含义 粉色 必背、必会证明、后续章节反复使用 蓝色 核心术语和定义 橙色 易错点、边界条件 绿色 理解提示和后续连接 3、章节主线 模块 本章要会什么 后续连接 Peano 系统 理解起点、后继、单射 ...