algorithm - 超图在现实世界中的应用

Question

A hypergraph是图的概括，其中边可以连接许多顶点。最近我看到很多关于超图(分割、聚类等)的出版物。所以我的问题是:

• 超图是否在现实世界中有任何应用(可能还有实现)，或者这只是学术研究而不打算供工程师使用？
• 是否有可以与超图一起使用的常见图算法的任何类似物，例如 max-flow 或 Dijkstra？

我对正态图有直觉。例如，图可以用来表示传输网络或贝叶斯网络的繁忙度规则。但我对超图没有这样的直觉，它们对我来说绝对是违反直觉的。

Answer 1

超图可表示为二分图，二分图可用于构造超图。这实际上只是说您可以将某种形式的参与者之间的交互表示为顶点或(超)边。

一旦我们认识到这种等价性，我们就可以得出结论，当您本来可以使用二部图时，超图是可用的，并且图算法的类比更直接地类似于二部图上的算法。