图论与组合

确定 Petersen 图的独立数 (independent number, 最大独立集的大小)、团数 (clique number, 最大团的大小) 和染色数。

证明或证伪: 如果 是仅有的两个度数为奇数的点, 那么存在一条 -path。

我们采用“最大边优先”的词典序：比较两棵树 时，先比较 ；若相等，再比较 ，依此类推。

区分候选算法的排序开销、并查集实现条件、在线交换代价与尚未证明的最优性。

归纳已经确认的建模与可行性结论，并列出算法证明、边界验证和实验所缺的证据。

界定最大边优先的词典序目标，整理基树构造、离线候选算法及尚待完成的证明与实验。

明确顶点度数恰好约束和最大边优先的词典序目标，通过五条边的例子逐步确定最优树。

生成子图 (spanning subgraph): 点集为 的子图。

完全图 (complete graph): 简单图, 任意两点间有边。

从最小叶删除到序列解码，建立 Cayley 公式与度数计数，再用拉普拉斯矩阵计算生成树数量。

辨析连通与邻接，证明闭合迹的环分解，并讨论欧拉图、排列图和含环条件。

画出二进制 de Bruijn 图，构造正则竞赛图，并证明强连通、拓扑排序和有向欧拉图的判据。

图论与组合的课程笔记，按主题、章节与习题整理。

令 是一个图 a 证明: 是一棵树当且仅当 是连通的且每条边都是割边 b 证明: 是一棵树当且仅当添加任一条以 中的顶点为端点的边恰好生成一个环。

首先连续的三条边至少有一条在极大匹配中, 不然一定可以将中间那条边加入到匹配中构成更大的一个匹配。

整理边连通度、Menger 定理、二分图匹配与点覆盖、最大流最小割等第 4 次作业。

在圆周上放置 个点, 其中 . 令 为将每个点与两个方向上与它最近的 个点相连得到的 -正则图. 例如, , 如下图所示. 证明: 当 能被 整除时, ；当 不能被 整除时, . 证明 时有 , 由此证明上面结论中 的下界不能被削弱。

无度约束的最小生成树（MST）可在多项式时间内求解{cormen2009introduction}： Kruskal：边按权升序，能连通且不成环则加入，复杂度 {kruskal1956shortest}； Prim：从任一顶点出发，每次取跨割最小边，二叉堆实现为 {prim1957shortest}。

本文给出一个多项式时间的构造算法，并在后续证明其在可行域内的词典序最优性。

加权图 (weighted graph): 边有边权。

图论与组合中关于「Algo」的课程笔记。

分割集 (separating set)/ 点割 (vertex cut): 点集 , 满足 的不连通或只有一个顶点。

称两条 -path 内部不相交, 当且仅当除了端点外没有公共点。

匹配 (matching): 一个没有自环, 任意两边没有公共端点的图。

k-因子 (k-factor): k-正则的导出子图。

保留基树、离线指派与 Kruskal 补全流程，明确可行性检查以及尚未完成的最优性证明。

保留可独立验证的可行性和基树结论，用反例纠正割交换、增度、前缀最优性及离线键的论证。