⚡

图算法策略Skill graph-algorithms

本技能提供在图数论中应用图算法的问题解决策略，涵盖算法选择、决策树和工具命令，用于优化图形理论中的计算和证明。关键词：图算法，图数论，最短路径，最小生成树，网络流，DFS，BFS，算法策略。

数据分析 0 次安装 0 次浏览 更新于 3/14/2026

name: graph-algorithms description: “图数论中图算法的问题解决策略” allowed-tools: [Bash, Read]

图算法

何时使用

在图形数论中处理图算法问题时使用此技能。

决策树

  1. 遍历选择

    • BFS: 最短路径（无权），层级结构
    • DFS: 循环检测，拓扑排序，强连通分量

  2. 最短路径算法

    算法 使用场景 复杂度
    Dijkstra 非负权重 O((V+E) log V)
    Bellman-Ford 负权重 O(VE)
    Floyd-Warshall 所有对 O(V^3)

  3. 最小生成树

    • Prim’s: 稠密图，从顶点贪心
    • Kruskal’s: 稀疏图，并查集
    • z3_solve.py prove "cut_property"

  4. 网络流

    • 最大流 = 最小割（Ford-Fulkerson）
    • 通过流网络匹配
    • sympy_compute.py linsolve "flow_conservation"

  5. 图属性

    • 谱: 邻接矩阵的特征值
    • 连通性: 通过DFS/BFS
    • 着色: 贪心或SAT约简

工具命令

Sympy_Adjacency

uv run python -m runtime.harness scripts/sympy_compute.py eigenvalues "adjacency_matrix"

Z3_Dijkstra

uv run python -m runtime.harness scripts/z3_solve.py prove "d[v] >= d[u] + w(u,v) for all edges"

Z3_Mst_Cut

uv run python -m runtime.harness scripts/z3_solve.py prove "min_edge_crossing_cut_in_mst"

Sympy_Flow

uv run python -m runtime.harness scripts/sympy_compute.py linsolve "flow_conservation_equations"

关键技巧

来自索引教科书：

  • [图论 (Graduate Texts in Mathematics (173))] 给定两个数值图不变量 i1 和 i2，写 i1 i2 如果我们能通过假设 i1(G) 足够大来强制 i2 在 G 的某个子图上任意高。形式上：写 i1 i2 如果存在一个函数 f : N → N 使得，对于任意 k ∈ N，每个具有 i1(G) f (k) 的图 G 都有一个子图 H 具有 i2(H) k。如果 i1 i2 以及 i1 i2，写 i1 ∼ i2。
  • [图论 (Graduate Texts in Mathematics (173))] 找到最小的整数 b = b(k) 使得每个阶为 n、边数超过 kn + b 的图对于每个 k ∈ N 都有一个 (k + 1)-边连通子图。证明每棵树 T 至少有 Δ(T ) 个叶子。证明一棵没有度数为 2 的顶点的树的叶子数多于其他顶点数。
  • [图论 (Graduate Texts in Mathematics (173))] 对于每个 n > 1，找到一个在 2n 个顶点上的二分图，以这样的方式排序，贪心算法使用 n 而不是 2 种颜色。练习 考虑以下顶点着色方法。首先，找到一个极大独立顶点集并用颜色 1 着色；然后在剩余图中找到一个极大独立顶点集并用颜色 2 着色，依此类推。
  • [图论 (Graduate Texts in Mathematics (173))] 证明，对于每个 r ∈ N，每个具有上密度 s 的无限图对于每个 s ∈ N 都有一个 K r 子图。推导出无限图的上密度只能取可数多个值 0, 1, 1/2, 2/3, 3/4 极值图论 给定一棵树 T，找到一个对于 ex(n, T ) 的上界，该界是 n 的线性函数且独立于 T 的结构。证明 Erdős–Sós 猜想当考虑的树是星形的情况。
  • [图论 (Graduate Texts in Mathematics (173))] 着色 稍一般地，一个图类 G 被称为 χ-有界如果存在一个函数 f : N → N 使得对于 G 中的每个图 G ⊇ Kr 有 χ(G) f ®。在这样的图中，那么我们可以通过使 χ 大于 f ® 来强制一个 Kr 子图。证明四色定理确实解决了本章第一句中陈述的地图着色问题。