ch7 图应用¶

1. 双连通分量¶

【无向图的关节点】其删除之后，原图的连通分量增多。

【双（重）连通图】无关节点的图。极大的双连通子图，称作双连通分量。

定义 \(hca(v) = subtree(v)\) 经后向边能抵达的最高祖先。
\(\tt DFS\) 过程中，一旦发现后向边 \((v,u)\)，即取 \(hca(v) = \min(hca(v), dTime(u))\)
\(\tt DFS(u)\) 完成并返回 \(v\) 时，若有 \(hca(u) < dTime(v)\)，即取 \(hca(v) = \min(hca(v), hca(u))\)
否则，即可断定 \(v\) 为关节点，且 \(\{v\} + subtree(u)\) 即为一个 \(\tt BCC\)。

【SSSP】单源最短路径问题

【APSP】全源最短路径问题

【Dijkstra 算法】优先级搜索算法，用于求解单源最短路径问题，不允许负边权。事实上，对于大部分负边权问题，可以进行扰动优化。

【Floyd - Warshall 算法】动态规划算法，用于求解全源最短路径问题，允许负边权。

【最小生成树】是众多优化问题的基本模型，为许多 NP 问题提供足够好的近似解。

【Kruskal 算法】

依据：任何环路 \(C\) 上的最长边 \(f\)，都不会被 \(\tt MST\) 采用，否则在移除 \(f\) 之后，\(\tt MST\) 将分裂为两棵树，将其视作一个割，则 \(C\) 上必有该割的另一跨边 \(e\)，既然 \(|e| < |f|\)，那么只要用 \(e\) 替换 \(f\)，就会得到一棵总权重更小的支撑树。
贪心算法。

【Prim 算法】

依据：设 \((U:V\setminus U)\) 是 \(N\) 的一个割，若 \((u,v)\) 是该割的一条极短跨边，则必存在一棵包含 \((u,v)\) 的 \(\tt MST\)。
优先级搜索算法。