C++算法-图算法-03

1.8 图处理问题

图问题按照解决难度，可以粗略分为如下几类：

 

1.简单。简单问题在最坏情况下运行是线性的。

 

简单连通性 一个给定的图是连通的吗？

有向图中的强连通 有向图中的每对顶点，是否存在一条彼此连接的有向路径？

传递闭包 有向图中，由各个顶点出发，沿着有向边可以到达哪些顶点？

最小生成树 加权图中，找到连接所有顶点的边集，且其权值最小。

单源最短路径 加权有向图中，将一个给定顶点v与图中各个顶点相连的最短路径是什么？

 

2.易处理。对于这种问题已经有一种算法，而且可以保证该算法的时间和空间需求由图规模(V+E)的一个多项式函数所限定。

 

平面性 是否可以画出一个给定图，并且用来表示边的任何线段都不相交？

库拉托夫斯基定理：无法在没有边交叉的条件下画出的图仅为如下的图，即它们包括一些子图，删除这些子图中度数为2的顶点后，相应子图与图平面图中的禁止子图（略）所示的某个图同构。

匹配 给定一个图，对于其边的某些子集，其中任意两条边都不会连接到同一个顶点上，那么满足此属性的最大边子集是什么？

有向图中的偶环 一个给定的有向图中，是否存在一个长度为偶数的环？

指派 二部加权匹配，它是在一个二部图中找到一种最小权值的最佳匹配。网络流算法

一般连通性 如果将图中的某条边删除，将把这个图分解为不相交的两个部分，那么这种边最少是多少（边连通性）？

邮差问题 给定一个图，找出一条变数最小的周游路径，该图中的每条边至少使用了一次（不过允许多次使用边）。

 

3.难处理。尚无已知的算法可以保证在一个合理的时间内解决此问题。 NP难问题。

 

最长路径 在一个图中，连接两个给定顶点的最长简单路径是什么？

着色问题 是否存在一种方法可以为图中的每个顶点着色，其可选颜色有k种，要求不存在连接相同颜色顶点的边。

独立集 存在一些图顶点子集，其中任何两个顶点都未由边相连，那么满足这种属性的最大顶点子集的规模如何？

包 在一个给定图中，最大包（完全子图）的规模是多少？

 

4.未知。既不知道其存在高效的算法，也未认定它们是NP难问题。

 

图同构 通过对顶点的重命名，能否使两个给定的图相同？

 

 

常用图算法的难度表

 

		E	T	I	?
无向图
	连通性	*
	一般连通性		*
	欧拉周游路径	*
	哈密顿周游路径			*
	二部匹配	*
	最大匹配		*
	平面性		*
	最大包			*
	2-着色	*
	3-着色			*
	最短路径	*
	最长路径			*
	顶点覆盖			*
	同构				*
有向图
	传递闭包	*
	强连通性	*
	奇数长度环	*
	偶数长度环		*
加权图
	最小生成树	*
	旅行商问题			*
网
	最短路径（非负权值）	*
	最短路径（负权值）				*
	最大流	*
	指派		*
	最小成本流		*

E：简单 T：易处理 I：难处理 ？：未知