图论在计算机科学、信息科学、人工智能网络理论、系统工程、控制论、运筹学和 经济管理等领域有着广泛的应用。但很多图论问题虽易表达,却难以求解,其中有相当多 的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MP 编程实现,包括传递闭包、连通分量、最短路径和最小生成树等

1.1 图的定义 1.2 图的表示 1.3 图的关系 1.4 图的运算

6.1 赋权图和距离 6.2 最小生成树 6.3 赋权欧拉图 6.4 赋权哈密尔顿图 7.1 有向图的定义 7.2 有向图的表示 7.3 有向图的连通 7.4 有向图的距离 7.5 流网络和最大流

复旦大学：《离散数学》课程教学讲义（图论）图论应用、图论算法

3.1 圈和树 3.2 二分图 3.3 欧拉图 3.4 哈密尔顿图

图的存储结构 图的周游 图的典型应用 ACM题目选讲

图的存储结构 图的周游 图的典型应用 ACM题目选讲

 欧拉通路/回路  欧拉图的充要条件  构造欧拉回路的Fleury算法  哈密尔顿通路/回路  哈密尔顿图的必要和充分条件  哈密尔顿图的应用

1.七桥问题,一笔画,欧拉通(回)路,欧拉图 2.判定欧拉图的充分必要条件 3.求欧拉回路的算法 4.中国邮递员问题

 生成树  深度优先搜索  广度优先搜索  有向图的深度优先搜索  回溯  最小生成树算法