各种图形类型的意义

Question

有很多named graph types。我想知道这个分类背后的标准是什么。不同的类型适用于不同的环境吗？而且，从商业应用程序（从设计和编程的角度来看）是否可以从这些分类中获益？这类似于设计模式吗？

Answer 1

我们给名图的普通家庭有以下几个原因：

• 图的某些家庭拥有不错的，简单的属性。例如，trees具有许多有用的属性（任何一对节点之间只有一条路径，它们最大程度地是非循环的，它们最小连接等），不包含任意图。 Directed acyclic graphs可以是topologically sorted，正常图不能。如果您可以使用这些类型的图表之一对问题进行建模，则可以使用它们上的专用算法来提取不一定能从任意图表获得的属性。

• 某些算法在某些类型的图表上运行得更快。许多图上的NP难问题，到目前为止还没有任何多项式时间算法，可以很容易地在某些类型的图上求解。例如，maximum independent set problem（选择没有两个节点通过边连接的节点的最大集合）是NP-hard，但可以在树和bipartite graphs的多项式时间内求解。 4着色问题（确定一个图的节点是否可以用四种不同颜色中的一种着色，而不向相邻节点分配相同的颜色）通常是NP-hard，但对于planar graphs（这是着名的四 - 色原理）。

• 某些算法在某些类型的图上更容易。图中的matching是图中没有两个边共享端点的边的集合。可以使用最大匹配来表示将人员组合成组的方式。在二分图中，可以使用最大匹配来表示将人员分配给任务的方式，使得没有人被分配两个任务并且没有任务被分配给两个人。有许多快速算法用于在双向图中找到最大匹配，该算法工作迅速且易于理解。一般图的相应算法明显更复杂，效率略低。

• 某些图表具有历史意义。许多命名图是以某人使用该图来反驳关于任意图的属性的猜测的名字命名的。例如，Petersen graph是许多定理的反例，对于图似乎是正确的，但事实上并非如此。

• 某些图表在理论计算机科学中很有用。一个expander graph是一个图，直观地说，任何节点集合都必须连接到图中比例较大的节点集合。并非所有图都是扩展图。 Expander图用于理论计算机科学中的许多结果，例如PCP定理的一个证明和证明SL = L。

这不是我们为什么关心不同的图科一个详尽的清单，但希望它有助于激发他们的使用和研究。

希望这会有所帮助！