图论与组合

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

确定下列命题的真假 a) 任意非连通图都有一个孤立顶点 b) 一个图是连通的当且仅当它的某个顶点与其他所有顶点是连通的 c) 任意闭合迹的边集可以划分成若干个环的边集 d) 如果图中有一个极大迹不是闭合的, 则其端点的度是奇数。

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

证明: 存在一个 -顶点的竞赛图使得其中每个顶点的入度等于出度当且仅当 是奇数。

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

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

时间的主导来自一次全局排序与 Kruskal；其余操作为线性或近线性。

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

本文针对单点度限制下的词典序最小生成树问题，提出了一种基于 Kruskal 构造初始最小生成森林； 一类/二类边的划分与优先级排序； 离线“指派”技术快速确定被替换的边。

对于任意的正整数列 满足 , 那么有 种有标号树, 满足第 个节点的度数恰好为。

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

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

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

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

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

无向连通图 ，其中 、； 每条边 的权值 ，且互不相同； 一个整数 （），要求最终生成树中顶点 的度数恰好为 。 一棵生成树 ，满足： ； 若记 的边权升序为。

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

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

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

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

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

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

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

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

{词典序最小生成树；度限制生成树；单顶点度约束；贪心算法；图论}。

我们研究的目标是：在所有满足 的生成树中，使按从小到大排序的边权向量 在“最大边优先”的词典序下最小（先最小化 ，若相同再最小化 ，依此类推）。

本章在边权互异的前提下，严格证明第~{sec:base-tree}~节与第~{sec:types}~节所述算法在 的可行域内输出“最大边优先”的词典序最小生成树，且最优解唯一。 {}{{maxlex}} 对生成树 ，记其边权从小到大排序为 。 给定两棵树 ，定义 当且仅当存在最小的 使得 且 。