超图，超图，超超图

Evolving Dependencies: From Graphs to Hypergraphs and

SuperHypergraphs

进化依赖:从图到超图和超超图

https://engrxiv.org/preprint/view/4769/8211

摘要

图论研究顶点和边的数学结构，以建模关系和连通性 [1, 2]。超图通过允许超边一次性连接任意多个顶点来扩展这一框架 [3]，而超超图通过迭代幂集构造进一步推广超图，以捕捉边之间的层次链接 [4, 5]。依赖图是一个有限有向无环图，其顶点表示任务，其边编码先决条件关系。在本文中，我们通过引入依赖超图和依赖超超图来扩展这一概念，并研究它们的基本性质。依赖超图将每个非空先决条件顶点集关联到恰好一个依赖顶点，而依赖超超图是一个 𝑛 层无环结构，其超顶点位于迭代幂集中，且其超边编码多层依赖。我们确立了这些模型如何推广经典依赖图，并展示了它们表示高阶依赖系统的潜力。

关键词： 超超图，超图，依赖图，依赖超图，依赖超超图

1 引言

1.1 从图到超超图 经典图通过顶点和边来表示成对关系 [6]。超图通过允许每个超边连接顶点的任意非空子集来扩展了这一框架，从而捕捉高阶交互 [7, 8]。超超图通过迭代应用幂集操作更进一步：某一层的边成为下一层的顶点，创造出嵌套的、多层级的网络，在一个统一框架内嵌入层次依赖关系 [9–12]。这种分层方法支持对具有递归或嵌套连接的复杂系统进行灵活表示和分析 [13]。

1.2 依赖图（依赖关系图） 依赖图（依赖关系图）是一个有限有向无环图，其顶点表示任务，其边编码先决条件关系 [14–21]。使用依赖图可提供任务关系的清晰可视化，通过拓扑排序实现无环调度，支持并行执行，优化资源分配，并辅助模块化分析 [14–16]。

1.3 我们的贡献：依赖超图和依赖超超图 我们分两个阶段推广该模型。首先，我们定义依赖超图，其中每个超边将一组非空的先决条件任务关联到单个依赖任务，从而能够表示多输入依赖。其次，我们引入依赖超超图，它通过迭代超图构造将依赖超图扩展到 𝑛 层，从而捕捉分层依赖结构。我们给出了形式化定义，证明了这些模型严格推广了经典依赖图，并探讨了它们的基本性质。依赖超超图捕捉多层先决条件，建模嵌套依赖层次，促进高级调度，改进分析，增强抽象能力，并优化资源分配。

2 预备知识

在整篇论文中，除非另有说明，我们使用的是有限简单图。本节回顾了将在后续部分使用的关键定义和符号；对于更深入的讨论，请参阅引用的来源。

2.1 超图和超超图

超图通过允许超边同时连接任意数量的顶点来扩展普通图 [3,7,22,23]。超超图在此基础上，通过对边之间的层次连接应用迭代幂集构造而建立 [5,10,12,24–26]。这些框架被应用于分子建模、网络分析和信号处理 [27–29]。

2.2 依赖图

依赖图是一个有限有向无环图，其顶点表示任务，其边指示每个任务的先决条件（参见 [35–37]）。

定义 2.8（依赖图）。（参见 [35–37]）依赖图是一个有向图

3 回顾与结果：依赖超图

依赖超图是一种超图，其中每个超边将一个非空的先决条件顶点集关联到恰好一个依赖顶点。

定理 3.5（依赖图的推广）。 每一个普通的（有向、无环）依赖图

4 结果：依赖超超图

依赖超超图是一个 𝑛 层无环超图，其顶点位于迭代幂集中，且其超边编码多层依赖关系。

5 结论与未来工作

在本文中，我们通过引入依赖超图和依赖超超图扩展了依赖图的经典概念，并详细探讨了它们的结构和理论性质。

作为未来工作，我们旨在通过结合基于不确定性的框架来进一步推广这些模型，例如模糊集 [38]、超模糊集 [39]、直觉模糊集 [40]、犹豫模糊集 [41]、中智集 [42] 和植生集 [43]。此类扩展将增强依赖建模在不确定或多值环境中的表达能力。

原文链接：https://engrxiv.org/preprint/view/4769/8211