图论

Vizing 定理 对于简单图 $G$: $$\chi'(G) \le \Delta (G) + 1$$ 其中 $\chi'(G)$ 为图 $G$ 的边色数，即最少使用多少颜色可以为 $G$ 的边染色，使得相邻边彼此颜色不同。$\Delta (G)$ 是图的最大点度数。 二分图 Vizing 定理 特别的对于二分图我们有 $$\chi'(G) = \Delta (G) $$ 我们可以构 …

约翰逊 Johnson 算法 全源最短路 对于最短路问题，我们的常用算法是 Dijkstra 算法或 Bellman-Ford 算法。但这两个算法经常解决的是单源最短路问题。 对于多源（全源）最短路问题，我们有一个基于动态规划的优秀算法，Floyd-Warshall …