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

问题描述 投票:0回答:3

图表对于模拟现实世界的现象和关系非常有用。

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

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

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

(请注意,“很少”是与站点/人员/元素/道路/等的总数数量相比。)

但是,我从未找到密集图的算法和数据结构的用例。
我记得曾经遇到过的每张图表都变得稀疏。

我需要使用密集图算法来处理什么类型的现实世界图?

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

社交网络软件从来都不是为少数人编写的
  1. Any
  2. 算法适用于小数据;不需要密集图算法。
  3. 这意味着我也不是在寻找像“稀疏图的补集”这样的愚蠢例子。
是的,这些很密集,但是除非你能给我一个具有实际意义的问题的例子,并且用原始稀疏图无法合理解决这个问题,否则这不会回答我的问题。


稀疏图的补充是密集图(想想给定网页

algorithm data-structures sparse-matrix graph-theory
3个回答
1
投票

从我的头顶...

小型社交网络(例如俱乐部中的人可能与俱乐部中的大多数其他人都是 Facebook 好友)

图的传递闭包,或至少部分传递闭包(例如朋友的朋友)
  • 确实写得很糟糕/紧密耦合的代码(想象一个有向图,其中如果 A 引用 B,则 A 类指向 B 类;可能作为成员、方法的返回值等)
  • 更一般地说,如果您想要更密集的图表,请尝试放宽某些旅行限制。

图越密集,它就越接近完整,并且具有加权边的完整图通常更容易表示和简单地思考为方阵,可能会散布一些无穷大或负无穷大来表示缺失“边缘”。 或者,它可能会变得接近完整的二部图,也可以表示为矩阵(只是沿两个轴使用不同标签集的矩阵。)

分配问题

0
投票

我认为使用稠密图算法的原因之一是保证稠密图上良好的最坏情况行为。 还有一些问题与图的补集上的其他问题相关——即,在该图中,每对顶点之间都有一条边,前提是它们在原始图中没有边。 例如。如果你正在寻找一个图中包含超过所有可能边的 30% 的最大团(这里真的是猜测),并且你认为这个团会很大,那么你最好创建补图然后寻找它的

最小顶点覆盖

,因为补图中这样的顶点覆盖的补集将是原始图中的一个团。 尽管这两个问题都是 NP 难问题,但当存在小覆盖时,最小顶点覆盖要快得多,对于大小为 k 的覆盖(对应于大小为 n-k 的团),采用 O(1.2378^k*n^O(1)) 与O(1.1888^n) 最大团。

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


0
投票

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.