圖、超圖到超超圖

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