图论总结 by Amber

ps:
从回复的情况来看，有相当多的人说这个图论总结只是一个目录。拜托，目录能写1MB多么？虽然我鄙视ms产品，但是也不得不普及一下：word的基本功能---“大纲”模式，用菜单---视图---普通看内容。谢谢。


点击这里下载doc版.


Version 0.8 Beta
有很多没有完善的地方。大家多提意见，建议。
真正写是写了一周，但修改了3个月。晕。
因为有很多公式图片，所以doc->html会有很多问题。


个人认为精彩的地方或者说大家可能不知道的东西:

1.1.5.    图论中特殊的集合
1.2.5.    星形表示法.
1.6.1.1.3.    Sollin（Boruvka）
1.6.2.1.1.2.1.    Shortest path faster algorithm(SPFA)
1.6.2.2.1.2.    Johnson
1.6.3.1.2.1.    有上下界的流问题


目录:
1.    图论 Graph Theory
1.1.    定义与术语 Definition and Glossary
1.1.1.    图与网络 Graph and Network
1.1.2.    图的术语  Glossary of Graph
1.1.3.    路径与回路  Path and Cycle
1.1.4.    连通性 Connectivity
1.1.5.    图论中特殊的集合 Sets in graph
1.1.6.    匹配 Matching
1.1.7.    树 Tree
1.1.8.    组合优化 Combinatorial optimization
1.2.    图的表示 Expressions of graph
1.2.1.    邻接矩阵 Adjacency matrix
1.2.2.    关联矩阵 Incidence matrix
1.2.3.    邻接表 Adjacency list
1.2.4.    弧表 Arc list
1.2.5.    星形表示 Star
1.3.    图的遍历 Traveling in graph
1.3.1.    深度优先搜索 Depth first search (DFS)
1.3.1.1.    概念
1.3.1.2.    求无向连通图中的桥 Finding bridges in undirected graph
1.3.2.    广度优先搜索 Breadth first search (BFS)
1.4.    拓扑排序 Topological sort
1.5.    路径与回路 Paths and circuits
1.5.1.    欧拉路径或回路 Eulerian path
1.5.1.1.    无向图
1.5.1.2.    有向图
1.5.1.3.    混合图
1.5.1.4.    无权图 Unweighted
1.5.1.5.    有权图 Weighed — 中国邮路问题The Chinese post problem
1.5.2.    Hamiltonian Cycle 哈氏路径与回路
1.5.2.1.    无权图 Unweighted
1.5.2.2.    有权图 Weighed — 旅行商问题The travelling salesman problem
1.6.    网络优化 Network optimization
1.6.1.    最小生成树 Minimum spanning trees
1.6.1.1.    基本算法 Basic algorithms
1.6.1.1.1.    Prim
1.6.1.1.2.    Kruskal
1.6.1.1.3.    Sollin（Boruvka）
1.6.1.2.    扩展模型 Extended models
1.6.1.2.1.    度限制生成树 Minimum degree-bounded spanning trees
1.6.1.2.2.    k小生成树 The k minimum spanning tree problem(k-MST)
1.6.2.    最短路Shortest paths
1.6.2.1.    单源最短路 Single-source shortest paths
1.6.2.1.1.    基本算法 Basic algorithms
1.6.2.1.1.1.    Dijkstra
1.6.2.1.1.2.    Bellman-Ford
1.6.2.1.1.2.1.    Shortest path faster algorithm(SPFA)
1.6.2.1.2.    应用Applications
1.6.2.1.2.1.    差分约束系统 System of difference constraints
1.6.2.1.2.2.    有向无环图上的最短路 Shortest paths in DAG
1.6.2.2.    所有顶点对间最短路 All-pairs shortest paths
1.6.2.2.1.    基本算法 Basic algorithms
1.6.2.2.1.1.    Floyd-Warshall
1.6.2.2.1.2.    Johnson
1.6.3.    网络流 Flow network
1.6.3.1.    最大流 Maximum flow
1.6.3.1.1.    基本算法 Basic algorithms
1.6.3.1.1.1.    Ford-Fulkerson method
1.6.3.1.1.1.1.    Edmonds-Karp algorithm
1.6.3.1.1.1.1.1.    Minimum length path
1.6.3.1.1.1.1.2.    Maximum capability path
1.6.3.1.1.2.    预流推进算法 Preflow push method
1.6.3.1.1.2.1.    Push-relabel
1.6.3.1.1.2.2.    Relabel-to-front
1.6.3.1.1.3.    Dinic method
1.6.3.1.2.    扩展模型 Extended models
1.6.3.1.2.1.    有上下界的流问题
1.6.3.2.    最小费用流 Minimum cost flow
1.6.3.2.1.    找最小费用路 Finding minimum cost path
1.6.3.2.2.    找负权圈 Finding negative circle
1.6.3.2.3.    网络单纯形 Network simplex algorithm
1.6.4.    匹配 Matching
1.6.4.1.    二分图 Bipartite Graph
1.6.4.1.1.    无权图-匈牙利算法 Unweighted - Hopcroft and Karp algorithm
1.6.4.1.2.    带权图-KM算法 Weighted –Kuhn-Munkres(KM) algorithm
1.6.4.2.    一般图General Graph
1.6.4.2.1.    无权图-带花树算法 Unweighted - Blossom (Edmonds)

[本日志由 admin 于 2008-06-21 03:07 AM 编辑]
文章来自: 本站原创
引用通告: 查看所有引用 | 我要引用此文章
Tags: