4

有很多命名的图类型。我想知道这种分类背后的标准是什么。不同的类型是否适用于不同的上下文？此外，业务应用程序（从设计和编程的角度来看）能否从这些分类中受益？这类似于设计模式吗？

4

1 回答 1

2

我们为常见的图族命名有几个原因：

  • 某些图族具有良好、简单的属性。例如，树有许多有用的属性（任何一对节点之间只有一条路径，它们是最大无环的，它们是最小连接的，等等）不包含任意图。 有向无环图可以进行拓扑排序，而普通图则不能。如果您可以根据其中一种类型的图对问题进行建模，则可以对它们使用专门的算法来提取不一定从任意图获得的属性。

  • 某些算法在某些类型的图上运行得更快。图上的许多 NP-hard 问题，目前还没有任何多项式时间算法，可以在某些类型的图上非常容易地解决。例如，最大独立集问题（选择最大的节点集合，其中没有两个节点通过边连接）是 NP-hard，但可以在多项式时间内解决树和二分图。4 着色问题（确定图的节点是否可以用四种不同颜色中的一种着色，而不为相邻节点分配相同的颜色）通常是 NP-hard，但对于平面图（这是著名的四-颜色定理）。

  • 某些算法在某些类型的图上更容易。图中的匹配是图中没有两条边共享端点的边的集合。最大匹配可用于表示将人们配对成组的方式。在二分图中，最大匹配可用于表示将人员分配给任务的一种方式，即没有人被分配两个任务，也没有任务分配给两个人。有许多快速算法可以在二分图中找到最大匹配，这些算法运行迅速且易于理解。一般图的相应算法明显更复杂，效率略低。

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

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

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

希望这可以帮助！

于 2013-05-02T16:54:29.860 回答