超图的现实应用

Question

超图是一种图的推广，其中边可以连接多个顶点。最近，我看到了许多关于超图(分割、聚类等)的出版物。所以我的问题是：

• 是否有超图的实际应用(可能还有实现)，或者这只是一项学术研究，不打算被工程师使用？
• 有没有类似于常用的图形算法，如max-flow或Dijkstra，可以与超图一起使用？

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

Answer 1

超图可表示为二部图，而二部图可用来构造超图。这实际上是说，您可以表示某种形式的参与者之间的交互，无论是顶点还是(超)边。

一旦我们认识到这种等价性，我们就可以得出超图是可用的，否则你可以使用二部图，而图算法的类比则更直接于二分图上的算法。

Answer 2

有一个用于使用超图的图像聚类的好方法：http://vision.ucsd.edu/bpc/

幻灯片在这里：slides.pdf

虽然该算法没有成为主流，但它很好地说明了超量语言中链接的概念及其含义。我认为超图在数据挖掘中可能非常有用。

Answer 3

零件装配的数学模型是基于超图的。这是用于计算机辅助制造(CAM)系统，以确定可能的和最优的(在某种意义上)的装配顺序。