路径问题
        
0/1边权最短路径
        BFS
        非负边权最短路径(Dijkstra)
            可以用Dijkstra解决问题的特征
        负边权最短路径
        Bellman
-Ford
            Bellman
-Ford的Yen-氏优化
            差分约束系统
        Floyd
            广义路径问题
            传递闭包
            极小极大距离 
/ 极大极小距离
        Euler Path 
/ Tour
            圈套圈算法
            混合图的 Euler Path 
/ Tour
        Hamilton Path 
/ Tour
            特殊图的Hamilton Path 
/ Tour 构造

    生成树问题
        最小生成树
        第k小生成树
        最优比率生成树
        
0/1分数规划
        度限制生成树

    连通性问题
        强大的DFS算法
        无向图连通性
            割点
            割边
            二连通分支
            有向图连通性
            强连通分支
            
2-SAT
            最小点基

    有向无环图
        拓扑排序
            有向无环图与动态规划的关系

    二分图匹配问题
        一般图问题与二分图问题的转换思路
        最大匹配
            有向图的最小路径覆盖
            
0 / 1矩阵的最小覆盖
        完备匹配
        最优匹配
        稳定婚姻

    网络流问题
        网络流模型的简单特征和与线性规划的关系
        最大流最小割定理
        最大流问题
            有上下界的最大流问题
                循环流
        最小费用最大流 
/ 最大费用最大流

    弦图的性质和判定

posted on 2009-11-27 14:37 西风萧瑟 阅读(684) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理