图论相关性质和结论整理
树的直径相关
-
边权非负时，两端点必为叶子节点。
-
对于两棵树，第一棵树的直径端点为 \(u_1,v_1\) ，第二棵的为 \(u_2,v_2\) ，将两棵树用一条边合并，新树的直径的端点必为上述四个端点中的两个。
-
若在一棵树的叶子结点上新接一个节点，直径最多会改变一个端点。
-
一棵树多条直径的交点是这些直径的中点。
-
若树的直径定义为两端点点权和加边权和，边权非负，点权可以为负数，可以用贪心法求直径。
树的重心相关
-
树的重心至多有两个，树的重心有两个时必树的大小必为偶数，有两个重心时两重心相邻，且两重心两子树大小为 \(\frac{n}{2}\) 和 \(\frac{n}{2} - 1\) 。
-
在一个 \(n\) 阶树中，一个点是重心 \(\Longleftrightarrow\) 该点的子树大小 \(size_v \leq \frac{n}{2}\) 。
-
设 \(\text{dist}(u,v)\) 表示树中点 \(u\) 到 \(v\) 之间的简单路径长度，那么一个点 \(G\) 是重心 \(\Longleftrightarrow\) 对于 \(\forall\ u \neq G\) ，有 \(\sum_{v=1}^n\text{dist}(u,v) \geq \sum_{v=1}^n \text{dist}(G,v)\) 。
-
若一棵树添加或删除一个叶子，整个树的重心最多移动一个节点。
-
将两棵树用一条边连接，生成的新树的重心在原来两棵树的重心的简单路径上。
-
重心一定在根节点的重链上。
MST 相关
-
在最小生成树去掉一条边 \(e\) ，树被分为两个点集 \(S_u\) ，\(S_v\) ，那么 \(e\) 是两个点集之间的最小的边。
-
最小生成树的第 \(k\) 小边是所有生成树第 \(k\) 小边的最短边。
-
对于联通图中的一个点，所有连接该边的最短边，必定为此图 MST 中的一条边。
-
若一个联通块属于 MST ，从外部到该联通块的最小的一条边也属于 MST 。
-
对于任意连通图， MST 中每种权值的边的数量是一定的。
Prufer 序列
基本性质：
-
Prufer 序列不考虑节点数为 \(1\) 的情况。
-
若一个点的度数为 \(d_i\) ，在 Prufer 序列中出现的次数为 \(d_i - 1\) 。
-
Prufer 序列和树形态形成双射关系。
Cayley's Formula :
-
带标号 \(n\) 阶无根树个数 ：\(n^{n-2}\)
-
设树中点 \(i\) 的度数为 \(d_i\) ， \(n\) 阶无根树个数 ： \({(n-2)!\over \prod_{i=1}^n d_i}\)
Generalized Cayley's Formula :
- 设 \(f(n,m)\) 为 \(n\) 个点构成 \(m\) 棵树，且对于 \(\forall\ i \leq m\) 都不在一棵树中，有标号，无根，则有 \(f(n,m) = mn^{n-m-1}\) 。
拓展：
\(n\) 个带权的点，边权为连接两点点权之积，树的权值为所有边权之积，求所有树的权值之和。
设第 \(i\) 个点权值为 \(val_i\) ，度数为 \(d_i\)，单棵树权值为 \(\prod_{i=1}^n val_i^{d_i}\) 。
考虑 Prufer 序列，根据乘法分配律有，答案为
\[\left(\prod_{i=1}^n{val_i}\right)\left(\sum_{i=1}^nval_i\right)^{n-2} \]应用：图联通方案数
欧拉图、半欧拉图、欧拉回路、欧拉通路
-
若 \(G\) 是欧拉图，则它为若干个边不重的圈的并。
-
若 \(G\) 是半欧拉图，则它为若干个边不重的圈和一条简单路径的并。
-
对于无向图 \(G\) ， \(G\) 是欧拉图当且仅当 \(G\) 是联通的且没有奇度顶点。
-
对于无向图 \(G\) ， \(G\) 是半欧拉图当且仅当 \(G\) 是联通的且 \(G\) 中恰好有 \(0\) 或 \(2\) 个奇度顶点。
-
对于有向图 \(G\) ， \(G\) 是欧拉图当且仅当 \(G\) 的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。
-
对于有向图 \(G\) ， \(G\) 是半欧拉图当且仅当
- 如果将 \(G\) 中的所有有向边退化为无向边时，那么 \(G\) 的所有顶点属于同一个连通分量。
- 最多只有一个顶点的出度与入度差为 \(1\)。
- 最多只有一个顶点的入度与出度差为 \(1\)。
- 所有其他顶点的入度和出度相同。
哈密顿图、哈密顿回路、哈密顿通路
性质：
-
设 \(G=<V,E>\) 是哈密顿图，则对于 \(V\) 的任意非空子集 \(V'\) ，均有 \(p(G-V')\leq|V'|\) 。其中 \(p(x)\) 为 \(x\) 的连通分支数。
对于半哈密顿图，有 \(p(G-V') \leq |V'|+1\) 。 -
完全图 \(K_{2k+1}(k\geq 1)\) 中含 \(k\) 条边不重的哈密顿回路，且这 \(k\) 条边不重的哈密顿回路包含 \(K_{2k+1}\) 的所有边。
-
完全图 \(K_{2k}(k\geq 2)\) 中含 \(k-1\) 条不重的哈密顿回路，从 \(K_{2k}(k \geq 2)\) 中删除这 \(k-1\) 条不重的哈密顿回路后所得到的图包含 \(k\) 条互不相邻的边。
-
设 \(G\) 是 \(n(n\geq 2)\) 的无向简单图，若对于 \(G\) 中不相邻的两个顶点 \(u, v\) ，均有 \(d(u) + d(v) \geq n - 1\) ，则 \(G\) 中存在哈密顿通路。
-
设 \(G\) 是 \(n(n\geq 3)\) 的无向简单图，若对于 \(G\) 中不相邻的两个顶点 \(u, v\) ，均有 \(d(u) + d(v) \geq n\) ，则 \(G\) 中存在哈密顿回路，从而 \(G\) 是哈密顿图。
-
设 \(G\) 是 \(n(n\geq 2)\) 的无向简单图，若对于 \(G\) 中任意顶点 \(u\) ，均有 \(d(u) \geq \frac{n}{2}\) ，则 \(G\) 中存在哈密顿回路，从而 \(G\) 是哈密顿图。
-
设 \(D\) 为 \(n(n\geq 2)\) 阶竞赛图，则 \(D\) 中存在哈密顿通路。
-
若 \(D\) 含 \(n(n\geq 2)\) 阶竞赛图为子图，则 \(D\) 中存在哈密顿通路。
-
强连通的竞赛图为哈密顿图。
-
若 \(D\) 含 \(n(n\geq 2)\) 阶竞赛图作为子图，则 \(D\) 中存在哈密顿回路。
竞赛图相关
概念：
-
竞赛图：\({n \choose 2}\) 条边的有向图，无重边或自环。
-
比分序列： 把竞赛图的每一个点的出度从小到大排序的序列。
性质：
-
缩点后生成的 DAG 呈链状，前面的点向后面的点连边。
-
每个强连通分量中存在一条哈密顿回路，整个图中存在一条哈密顿通路。
-
在每个大小 \(size>1\) 的强连通分量中，存在大小为 \([3,size]\) 的环。
-
兰道定理 (Landau's Theorem)：
竞赛图的比分序列合法当且仅当
\(\forall i\in[1,n]\) ，满足 \(\sum_{k=1}^i s_k \geq {i \choose 2}\) ，详细证明。
- 设有集合 \(P\) 对于 \(\forall i\in P\) 满足 \(\sum_{k=1}^i s_k = {i\choose 2}\) ，则点 \([P_i + 1, P_{i+1}]\) 会组成一个强连通分量。
计数（带标号）：
-
\(n\) 阶竞赛图个数为 \(h_n = 2^{\frac{n\times(n-1)}{2}}\)
-
强连通的 \(n\) 阶竞赛图个数 \(f_n = h_n - \sum_{k=1}^{n-1} h_k \times {n \choose k} \times f_{n - k}\)
二分图
-
最小点覆盖 = 二分图最大匹配
-
最小边覆盖 = 总点数 - 最大匹配
-
最小独立集 = 总点数 - 最大匹配
网络流
咕~~~~
Reference
OI-Wiki & 前文中链接