自然稠密图的例子有哪些？

Question

图形对于建模真实世界的现象和关系非常有用。

从广义上讲，图数据结构和算法分为两类：

• 那些对稀疏图有用的（例如邻接列表，约翰逊算法）
• 那些对稠密图有用的（例如邻接矩阵、Floyd-Warisher）。

然而，在我能想到的每种情况下，现实世界的图表都是稀疏的。例如：

1. Web网络形成稀疏图（每个站点都链接到其他几个站点）
2. 社交网络形成稀疏图（每个人都认识几个其他人）
3. 电气网络形成稀疏图（大多数电路元件只影响附近的少数电路元件）
4. 道路网络形成稀疏图（每条道路都连接到其他几条道路）

（请注意，“很少”是相对于场地/人员/要素/道路/等的总数而言的。）

然而，我从来没有找到密集图的算法和数据结构的用例。
我记得遇到的每个图都被证明是稀疏的。

请注意：是的，我知道每个人都认识的一小群人形成了一个密集的图表，但这不是我要问的那种情况，因为：

1. 社交网络软件从来不是为少数人编写的

这意味着我也不是在寻找像“稀疏图的补码”这样愚蠢的例子<是的，这些都是稠密的，但除非你能给我一个实际感兴趣的问题的例子，并且不能用原始稀疏图合理地解决，否则这不能回答我的问题。

Answer 1

我能想到的一个例子是加密货币，其中每种货币都可以转换为其他货币。为了跟踪市场波动时的所有转换率，您需要一个密集的图表示和算法。

Answer 2

嗯，一个图变得越密集，它就越接近完整，一个带有加权边的完整图通常更容易表示，并且简单地认为它是一个正方形矩阵，可能会有一些无穷大或负无穷大分散在周围来表示缺少的“边”。或者，它可能会变得接近一个完整的二部图，它也可以表示为一个矩阵（只是一个沿着两个轴使用不同标签集的矩阵）。所以例如，分配问题通常被表示为一个关于矩阵的问题，而不是一个关于密集边加权二部图的问题。

我认为使用稠密图算法的一个原因是保证在稠密图上有良好的最坏情况行为。

还有一些问题与图的补码上的其他问题有关——即图中每对顶点之间都有一条边，如果它们在原始图中没有边的话。例如，如果你在一个包含超过所有可能边的30%的图中寻找最大团（在这里真的是猜测），并且你认为这个团会很大，你可能最好创建补码图，然后寻找它的最小顶点覆盖，因为补码图中这样一个顶点覆盖的补码将是原始图中的一个团。尽管这两个问题都是NP-hard，但当存在小覆盖时，最小顶点覆盖要快得多，对于大小k的覆盖（对应于大小n-k的团）取O（1.2378^k*n^O（1））与O（1.1888^n）对于最大团。

Answer 3

稀疏图的补充是密集图（想想给定网页未链接到的所有站点）。所以有一个开始。

从我的头顶...

• 小型社交网络（例如，俱乐部中的人可能与俱乐部中的大多数其他人都是Facebook朋友）

一般来说，如果您想要更密集的图形，请尝试放宽某些旅行限制。