图论及应用

第1章  图
  1.1 图的定义和术语
    1.1.1 图的定义
    1.1.2 特殊的图
    1.1.3 有向图和无向图
    1.1.4 路径与连通
  1.2 图的存储结构
    1.2.1 邻接矩阵
    1.2.2 前向星
    1.2.3 邻接表
  1.3 图的遍历
    1.3.1 图的深度优先遍历
    1.3.2 图的宽度优先遍历
    1.3.3 图的拓扑排序
    1.3.4 图的可行遍性
第2章  树
  2.1 树的定义和遍历
    2.1.1 树的相关定义
    2.1.2 树的遍历
  2.2 图的生成树
    2.2.1 最小生成树
    2.2.2 次小生成树
    2.2.3 有向图的最小树形图
  2.3 树的其他问题
    2.3.1 树上两点的最近公共祖先
    2.3.2 树的最小支配集，最小点覆盖与最大独立集
第3章  图的最短路径问题
  3.1 单源最短路径
    3.1.1 Dijkstra算法
    3.1.2 Bellman-Ford算法
    3.1.3 SPFA算法
    3.1.4 例题
  3.2 每对顶点间的最短距离
    3.2.1 Floyd算法
    3.2.2 例题
  3.3 最短路问题的扩展与应用
    3.3.1 k短路
    3.3.2 差分约束系统
    3.3.3 DAG图上的单源最短路径
    3.3.4 Floyd求最小环
第4章  连通性问题
  4.1 图的强连通
    4.1.1 强连通的定义
    4.1.2 Kosaraju算法
    4.1.3 Tarjan算法
    4.1.4 Garbow算法
    4.1.5 例题
  4.2 最小点基
    4.2.1 最小点基的定义
    4.2.2 最小点基
    4.2.3 最小权点基
    4.2.4 例题
  4.3 图的双连通
    4.3.1 双连通的定义
    4.3.2 点双连通分量
    4.3.3 边双连通分量
    4.3.4 例题
  4.4 图的全局最小割问题和Stoer-Wagner算法
  4.5 2-SAT
    4.5.1 SAT
    4.5.2 2-SAT
    4.5.3 例题
第5章  网络流
  5.1 网络
    5.1.1 容量与流
    5.1.2 残留网络及增广路
    5.1.3 最小割最大流定理
  5.2 最大流算法
    5.2.1 Ford-Fulkson方法的基本思想
    5.2.2 Edmond-Karp算法
    5.2.3 SAP算法及其优化
    5.2.4 Dinic算法
    5.2.5 例题与应用
  5.3 有上下界的网络流
    5.3.1 解决上下界网络流的一般思路
    5.3.2 例题与应用
  5.4 网络的费用流
    5.4.1 连续最短路算法
    5.4.2 例题与应用
第6章  二分图及匹配算法
  6.1 匹配问题
  6.2 匹配基本定理
    6.2.1 Berge定理
    6.2.2 Hall定理
  6.3 二分图最大匹配
    6.3.1 匈牙利算法
    6.3.2 Hopcroft-Karp算法
    6.3.3 二分图多重匹配
    6.3.4 二分图最大匹配的网络流解法
  6.4 二分图最佳匹配
    6.4.1 Kuhn Munkras算法
  6.5 二分图模型的应用
    6.5.1 二分图最小点覆盖
    6.5.2 有向无环图的最小路径覆盖
    6.5.3 二分图的最大独立点集
    6.5.4 最小点权覆盖
参考文献