图的性质

度序列

度序列 $\{d_1,\cdots ,d_n\}$ 可简单图化当且仅当：设 $d_1={\max }_i{d}_i$，则 $\{d_2-1,\cdots ,d_{d_1+1}-1,d_{d_1+2},\cdots ,d_n\}$ 可简单图化。

Erdos-Gallai 定理

TIP

这个定理可以在 $O(n)$ 时间内判断度序列是否可简单图化。

度序列 $\{d_1,\cdots ,d_n\}$ 可简单图化当且仅当：${\sum }_i{d}_i$ 是偶数，并且

$$\sum _{i=1}^k{d}_i⩽k(k-1)+\sum _{i=k+1}^n\min (d_i,k),\forall k.$$

Havel-Hakimi 定理

设 ${\left\{d_i\right\}}_{i=1}^n$ 单调递增，则它可简单图化当且仅当 $\{d_2-1,\cdots ,d_{d_1+1}-1,d_{d_1+2},\cdots ,d_n\}$ 可简单图化。

竞赛图

1. 竞赛图缩点之后，拓扑序靠前的强连通分量向靠后的每个分量连边。
2. 竞赛图上存在边 $(u,v)$ 的充要条件是 $u$ 的出度大于等于 $v$ 的出度。

反图连通性

以下是我搞出来的一个 $O(n+m)$ 的算法，可以根据反图的连通性建立并查集：

quick_union qu(n + 1);
vector<int> cand(n);
iota(cand.begin(), cand.end(), 1);
for (int i = 1; i <= n; ++i) {
    vector<int> nxt = { i };
    unordered_map<int, int, safe_hash> mp;
    for (auto&& u : ch[i]) {
        ++mp[qu.query(u)];
    }
    for (auto&& u : cand) {
        if (mp.count(qu.query(u)) and mp[qu.query(u)] == qu.query_size(u)) {
            nxt.emplace_back(u);
        } else if (not qu.connected(i, u)) {
            qu.merge(i, u);
        }
    }
    cand.swap(nxt);
}

DFS 序相关

• 多个点的 LCA 就是 DFS 序最小的点和 DFS 序最大的点的 LCA
• 无向图关于 DFS 生成树的每个弦都是返祖边

双连通分量

• 点双连通分量：极大子图，满足对于子图中任意一对点，无论删去原图中哪一个点都没法使得它们不连通；
• 边双连通分量：极大子图，满足对于子图中任意一对点，无论删去原图中哪一个边都没法使得它们不连通。

树的性质

直径

• 对任意一个点来说，与他距离最远的点一定在某一条直径上
• 树的所有直径中点重合

重心

• 重心是以它为根的情况下、所有子树大小的最大值最小的那个点
• 树的重心至多有两个，并且相邻
• 以重心为根，所有子树大小不超过 $\frac{n}{2}$
• 树中所有点到某个点的距离和中，到重心的距离和是最小的
• 添加/删除一个叶子，重心至多移动一

树形背包

• 如果合并两个子树的代价等于子树大小乘积，则时间为 $O(n^2)$
• 如果合并两个子树的代价等于子树大小和 $m$ 取最小值，则时间为 $O(nm)$

WARNING

注意背包的时候把范围卡紧！

二分图

• 主条目：二分图
• 可以奇偶染色
• 不存在奇环
• 树是二分图

欧拉图

• 欧拉图全都是偶点
• 半欧拉图只有两个奇点

仙人掌

• 仙人掌就是每个边（而不是点）至多属于一个简单环
• 如果一个图不存在偶环，则它是仙人掌（不可能出现环套环）

生成树

• 最小生成树的边权序列唯一
• 不同权值之间的选择互不影响

基环树

• 基环树分有向和无向两种
• 基环树没有环套环
• 每个点至多有一个出边的有向图是基环树