Evolving Dependencies: From Graphs to Hypergraphs and

SuperHypergraphs

進(jìn)化依賴:從圖到超圖和超超圖

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

摘要

圖論研究頂點(diǎn)和邊的數(shù)學(xué)結(jié)構(gòu)，以建模關(guān)系和連通性 [1, 2]。超圖通過允許超邊一次性連接任意多個(gè)頂點(diǎn)來擴(kuò)展這一框架 [3]，而超超圖通過迭代冪集構(gòu)造進(jìn)一步推廣超圖，以捕捉邊之間的層次鏈接 [4, 5]。依賴圖是一個(gè)有限有向無環(huán)圖，其頂點(diǎn)表示任務(wù)，其邊編碼先決條件關(guān)系。在本文中，我們通過引入依賴超圖和依賴超超圖來擴(kuò)展這一概念，并研究它們的基本性質(zhì)。依賴超圖將每個(gè)非空先決條件頂點(diǎn)集關(guān)聯(lián)到恰好一個(gè)依賴頂點(diǎn)，而依賴超超圖是一個(gè) 層無環(huán)結(jié)構(gòu)，其超頂點(diǎn)位于迭代冪集中，且其超邊編碼多層依賴。我們確立了這些模型如何推廣經(jīng)典依賴圖，并展示了它們表示高階依賴系統(tǒng)的潛力。

關(guān)鍵詞： 超超圖，超圖，依賴圖，依賴超圖，依賴超超圖

1 引言

1.1 從圖到超超圖 經(jīng)典圖通過頂點(diǎn)和邊來表示成對(duì)關(guān)系 [6]。超圖通過允許每個(gè)超邊連接頂點(diǎn)的任意非空子集來擴(kuò)展了這一框架，從而捕捉高階交互 [7, 8]。超超圖通過迭代應(yīng)用冪集操作更進(jìn)一步：某一層的邊成為下一層的頂點(diǎn)，創(chuàng)造出嵌套的、多層級(jí)的網(wǎng)絡(luò)，在一個(gè)統(tǒng)一框架內(nèi)嵌入層次依賴關(guān)系 [9–12]。這種分層方法支持對(duì)具有遞歸或嵌套連接的復(fù)雜系統(tǒng)進(jìn)行靈活表示和分析 [13]。

1.2 依賴圖（依賴關(guān)系圖） 依賴圖（依賴關(guān)系圖）是一個(gè)有限有向無環(huán)圖，其頂點(diǎn)表示任務(wù)，其邊編碼先決條件關(guān)系 [14–21]。使用依賴圖可提供任務(wù)關(guān)系的清晰可視化，通過拓?fù)渑判驅(qū)崿F(xiàn)無環(huán)調(diào)度，支持并行執(zhí)行，優(yōu)化資源分配，并輔助模塊化分析 [14–16]。

1.3 我們的貢獻(xiàn)：依賴超圖和依賴超超圖 我們分兩個(gè)階段推廣該模型。首先，我們定義依賴超圖，其中每個(gè)超邊將一組非空的先決條件任務(wù)關(guān)聯(lián)到單個(gè)依賴任務(wù)，從而能夠表示多輸入依賴。其次，我們引入依賴超超圖，它通過迭代超圖構(gòu)造將依賴超圖擴(kuò)展到 層，從而捕捉分層依賴結(jié)構(gòu)。我們給出了形式化定義，證明了這些模型嚴(yán)格推廣了經(jīng)典依賴圖，并探討了它們的基本性質(zhì)。依賴超超圖捕捉多層先決條件，建模嵌套依賴層次，促進(jìn)高級(jí)調(diào)度，改進(jìn)分析，增強(qiáng)抽象能力，并優(yōu)化資源分配。

2 預(yù)備知識(shí)

在整篇論文中，除非另有說明，我們使用的是有限簡(jiǎn)單圖。本節(jié)回顧了將在后續(xù)部分使用的關(guān)鍵定義和符號(hào)；對(duì)于更深入的討論，請(qǐng)參閱引用的來源。

2.1 超圖和超超圖

超圖通過允許超邊同時(shí)連接任意數(shù)量的頂點(diǎn)來擴(kuò)展普通圖 [3,7,22,23]。超超圖在此基礎(chǔ)上，通過對(duì)邊之間的層次連接應(yīng)用迭代冪集構(gòu)造而建立 [5,10,12,24–26]。這些框架被應(yīng)用于分子建模、網(wǎng)絡(luò)分析和信號(hào)處理 [27–29]。

2.2 依賴圖

依賴圖是一個(gè)有限有向無環(huán)圖，其頂點(diǎn)表示任務(wù)，其邊指示每個(gè)任務(wù)的先決條件（參見 [35–37]）。

定義 2.8（依賴圖） 。（參見 [35–37]）依賴圖是一個(gè)有向圖

3 回顧與結(jié)果：依賴超圖

依賴超圖是一種超圖，其中每個(gè)超邊將一個(gè)非空的先決條件頂點(diǎn)集關(guān)聯(lián)到恰好一個(gè)依賴頂點(diǎn)。

定理 3.5（依賴圖的推廣）。 每一個(gè)普通的（有向、無環(huán)）依賴圖

4 結(jié)果：依賴超超圖

依賴超超圖是一個(gè) 層無環(huán)超圖，其頂點(diǎn)位于迭代冪集中，且其超邊編碼多層依賴關(guān)系。

5 結(jié)論與未來工作

在本文中，我們通過引入依賴超圖和依賴超超圖擴(kuò)展了依賴圖的經(jīng)典概念，并詳細(xì)探討了它們的結(jié)構(gòu)和理論性質(zhì)。

作為未來工作，我們旨在通過結(jié)合基于不確定性的框架來進(jìn)一步推廣這些模型，例如模糊集 [38]、超模糊集 [39]、直覺模糊集 [40]、猶豫模糊集 [41]、中智集 [42] 和植生集 [43]。此類擴(kuò)展將增強(qiáng)依賴建模在不確定或多值環(huán)境中的表達(dá)能力。

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