超超圖的基本計(jì)算問題與算法

Fundamental Computational Problems and Algorithms for SuperHyperGraphs

https://www.researchgate.net/publication/390760743_Fundamental_Computational_Problems_and_Algorithms_for_SuperHyperGraphs

摘要

超圖通過允許邊（稱為超邊）連接兩個(gè)以上的頂點(diǎn)，而不僅僅是成對的頂點(diǎn)，從而擴(kuò)展了傳統(tǒng)圖。本文探討了超級超圖背景下的基本問題和算法，超級超圖是超圖的一種高級擴(kuò)展，能夠建模層次化和復(fù)雜的關(guān)系。涵蓋的主題包括構(gòu)建超級超圖、識別超級超樹以及計(jì)算超級超樹寬。我們解決了一系列優(yōu)化問題，例如超級超圖劃分問題、可達(dá)性、最小生成超級超樹和單源最短路徑。此外，經(jīng)典問題的改編版本，如旅行商問題、中國郵遞員問題和最長簡單路徑問題，也在超級超圖框架中被提出。

關(guān)鍵詞：超級超圖，超圖，樹寬，算法

1 | 引言

1.1 | 圖與超圖

圖論作為分析網(wǎng)絡(luò)的基礎(chǔ)框架，由節(jié)點(diǎn)（頂點(diǎn)）及其連接（邊）組成。它為不同網(wǎng)絡(luò)的結(jié)構(gòu)、連通性和屬性提供了寶貴的見解 [28]。 超圖通過允許邊（稱為超邊）連接兩個(gè)以上的頂點(diǎn)，而不僅僅是成對頂點(diǎn)，從而擴(kuò)展了傳統(tǒng)圖。由于在圖論、計(jì)算機(jī)科學(xué)及相關(guān)領(lǐng)域的廣泛應(yīng)用，這些廣義結(jié)構(gòu)獲得了顯著關(guān)注 [32, 21, 53, 6, 62, 120]。作為超圖的進(jìn)一步擴(kuò)展，超級超圖引入了更大的靈活性，是近期研究中新興的興趣主題 [109, 110]。超級超圖泛化了超圖，允許頂點(diǎn)和超邊表示集合或子集，從而能夠建模層次化和復(fù)雜的關(guān)系。 在圖、超圖和超級超圖的背景下，樹結(jié)構(gòu)已被廣泛研究。例如，超樹已在超圖中得到探索 [58]，而超級超樹已在超級超圖中得到研究 [55]。樹結(jié)構(gòu)的概念被廣泛采用，是因?yàn)樗鼈冊趹?yīng)用中的簡單性和效率。除了圖相關(guān)概念外，樹結(jié)構(gòu)已應(yīng)用于各種領(lǐng)域，包括樹自動機(jī) [23, 17]、樹軟集 [113, 43, 9] 和決策樹 [19, 20]，促進(jìn)了這些領(lǐng)域的持續(xù)研究和進(jìn)展。

1.2 | 圖寬參數(shù)

圖特征通常使用各種參數(shù)進(jìn)行分析，大量研究致力于理解這些度量。其中，圖寬參數(shù)如樹寬 [94, 95, 100, 16, 14, 15] 尤為突出。這些參數(shù)評估圖接近樹結(jié)構(gòu)的程度，這對于許多實(shí)際應(yīng)用至關(guān)重要。 對于超圖，類似參數(shù)如超樹寬 [57, 59, 125, 79, 3] 和超路徑寬 [87, 82, 2] 已被開發(fā)出來。這些度量衡量超圖與樹或路徑的相似程度，滿足了將基于樹的分析擴(kuò)展到更復(fù)雜結(jié)構(gòu)的需求。

1.3 | 計(jì)算復(fù)雜性

算法是一系列旨在解決特定問題或執(zhí)行計(jì)算的明確定義的指令的有限序列 [31]。算法的時(shí)間和空間復(fù)雜性通常是分析的主題。計(jì)算復(fù)雜性評估算法解決問題所需的資源（如時(shí)間和空間），作為輸入大小的函數(shù)，提供理論效率界限 [89, 10, 65, 1]。 圖論中的算法被稱為圖算法 [31]。對于圖和超圖，許多問題和算法已被研究，研究還探索了現(xiàn)實(shí)世界的應(yīng)用（例如 [86, 50, 68]）。

1.4 | 本文的貢獻(xiàn)

與超級超圖相關(guān)的問題和算法的研究仍然有限。因此，本文探討了超級超圖中的各種基本問題，并提出了算法來解決它們。

? 超級超圖的精確構(gòu)造：開發(fā)了一種算法，從給定的頂點(diǎn)和邊集構(gòu)造超級超圖。

? 識別超級超樹：提供一種算法來確定給定結(jié)構(gòu)是否是有效的超級超樹。

? 超級超樹寬的計(jì)算： – 精確算法：

定義了一種精確算法來計(jì)算超級超圖的超級超樹寬。

– 近似算法：提出了一種近似算法，用于計(jì)算上高效的超級超樹寬計(jì)算。

? 超級超圖劃分問題：研究將超級超圖劃分為不相交子集的方法，同時(shí)最小化分區(qū)間的連接。

? 超級超圖中的可達(dá)性問題：探索算法以驗(yàn)證超級超圖中兩個(gè)頂點(diǎn)之間是否存在路徑。

? 最小生成超級超樹問題：提出一種方法來計(jì)算具有最小總邊權(quán)的超級超樹。 ? 超級超圖中的單源最短路徑問題：開發(fā)一種算法來查找超級超圖中從單個(gè)源頂點(diǎn)出發(fā)的最短路徑。

? 超級超圖中的旅行商問題：考察旅行商問題（TSP）對超級超圖的改編，尋找覆蓋所有頂點(diǎn)的最小回路。

? 超級超圖中的中國郵遞員問題 (CPP)：分析如何在給定條件下在超級超圖中找到歐拉回路。

? 超級超圖中的最長簡單路徑問題：研究識別超級超圖中最長無環(huán)路徑的方法。

? 超級超圖中的最大生成樹問題：提出算法來計(jì)算具有最大總邊權(quán)的超級超樹。

? 超級超圖中的 Horn 可滿足性問題：將 Horn 可滿足性問題擴(kuò)展到超級超圖，并帶有改編的算法和證明。

2 | 預(yù)備知識和定義

在本節(jié)中，我們提供預(yù)備知識和定義。尋求圖論基礎(chǔ)概念和符號的讀者被鼓勵參考標(biāo)準(zhǔn)文本、綜述或講義，例如 [28, 26, 27, 123]。這項(xiàng)工作也利用了集合論的基本原理，為此推薦參考文獻(xiàn)如 [66, 35, 76, 71, 70]。對于本文涉及的具體操作和相關(guān)主題的詳細(xì)討論，讀者可以參考各自的參考文獻(xiàn)以獲得額外的見解。

2.1 | 圖與超圖

圖論提供了一個(gè)基礎(chǔ)框架來分析網(wǎng)絡(luò)，網(wǎng)絡(luò)由節(jié)點(diǎn)（頂點(diǎn)）及其連接（邊）組成。超圖通過允許超邊擴(kuò)展了傳統(tǒng)圖的概念，超邊可以連接多個(gè)頂點(diǎn)而不僅僅是成對，從而能夠表示元素之間更復(fù)雜的關(guān)系 [58, 13, 60, 11, 12, 59]。圖和超圖的基本定義如下所示。

2.2 | 樹寬和超樹寬

樹寬通過使用具有最小寬度的樹狀結(jié)構(gòu)來表示圖，以此量化圖與樹的相似程度 [100, 96, 97, 98, 99]。超樹寬將這一概念推廣至超圖，衡量超圖能夠被分解為樹狀結(jié)構(gòu)的有效程度 [57, 59, 125, 79, 3, 2, 56, 58]。樹寬和超樹寬的形式化定義如下所示。

2.3 | 超級超圖與超級超樹

超級超樹是超級超圖中的樹 [55, 40]。超級超圖被認(rèn)為是圖和超圖等概念的泛化（參見 [109, 64, 93, 114, 115, 114, 46, 40, 63, 111, 112, 45, 38, 44, 41, 110]）。定義及相關(guān)概念如下所示。

2.4 | 超級超樹寬

超級超樹寬是超樹寬的一種抽象，擴(kuò)展了樹寬的概念。定義如下所示 [40]。

2.5 | 算法的基本定義

此處提供了與結(jié)果部分中描述的算法相關(guān)的基本定義。如有需要，讀者可參考講義或引言以獲取更多細(xì)節(jié) [31, 24, 103]。 定義 20. (參見 [89, 103]) 算法的總時(shí)間復(fù)雜性定義為執(zhí)行算法每一步所需時(shí)間的總和，表示為輸入大小的函數(shù)。如果算法涉及多個(gè)步驟或操作，則總時(shí)間復(fù)雜性由最耗時(shí)操作所需的最大時(shí)間決定。

3 | 本文的結(jié)果

本文的結(jié)果如下所示。

3.1 | 精確構(gòu)造超級超圖

我們考慮構(gòu)造超級超圖的算法。本子節(jié)中考慮的問題描述如下。

上述問題的算法及相關(guān)定理如下所示。

3.3 | 超級超樹寬的計(jì)算

本子節(jié)探討了超級超樹寬的計(jì)算算法。本子節(jié)中考慮的問題描述如下。

3.3.2 | 超級超樹寬的近似算法

3.4 | 超級超圖劃分問題

我們考慮著名的圖劃分問題。圖劃分問題旨在將圖的頂點(diǎn)劃分為不相交的子集，同時(shí)最小化邊割或最大化組內(nèi)連通性 [104, 75, 33]。超圖劃分問題通過將超圖的頂點(diǎn)劃分為子集同時(shí)最小化超邊割來泛化這一點(diǎn)，其中超邊連接多個(gè)頂點(diǎn) [102, 73, 117, 34]。這些問題在本研究中被進(jìn)一步擴(kuò)展到超級超圖的背景下。本子節(jié)中考慮的問題描述如下。

3.5 | 超級超圖中的可達(dá)性問題

可達(dá)性問題確定在圖或超圖中使用其邊是否存在兩個(gè)頂點(diǎn)之間的路徑 [7, 8]。本子節(jié)中考慮的問題描述如下。

解決可達(dá)性問題的算法遵循適用于超圖的深度優(yōu)先搜索 (DFS) [119] 策略。在傳統(tǒng)的 DFS 中，我們通過跟隨邊來探索頂點(diǎn)。對于超級超圖，一條超邊可以連接任意數(shù)量的頂點(diǎn)，我們需要修改 DFS 以考慮超邊連接的所有頂點(diǎn)。

3.6 | 最小生成超級超樹問題

最小生成樹問題確定一棵連接所有圖頂點(diǎn)且具有最小總邊權(quán)的樹 [61, 4, 128]。最小生成超樹問題將此概念擴(kuò)展至超圖，尋求最小化超邊權(quán)重的樹狀結(jié)構(gòu) [122]。在本子節(jié)中，我們探討最小生成超級超樹問題。所考慮的問題描述如下。

3.7 | 超級超圖中的單源最短路徑問題

超級超圖中的單源最短路徑問題 [92, 88, 81] 涉及尋找從源頂點(diǎn)到所有其他頂點(diǎn)的最短路徑，并使遍歷的超級超邊的總權(quán)重最小化。所考慮的問題描述如下。

3.8 | 超級超圖中的旅行商問題

超級超圖中的旅行商問題 [29, 77, 91] 旨在尋找一個(gè)最小權(quán)重的回路，該回路恰好訪問所有超級頂點(diǎn)一次，在考慮超級超邊權(quán)重的同時(shí)返回起始超級頂點(diǎn)，并確保連通性約束。所考慮的問題描述如下。

3.9 | 超級超圖中的中國郵遞員問題 (CPP)

超級超圖中的中國郵遞員問題 (CPP) [30, 121, 83] 旨在尋找一條最小權(quán)重的閉合行走，該行走至少遍歷所有超級超邊一次，從而確保遍歷的效率。所考慮的問題描述如下。

問題 62. 給定一個(gè)加權(quán)超級超圖 SHG = ( V , E ) ，中國郵遞員問題 (CPP) 旨在尋找一條最小權(quán)重的閉合超級超路徑，該路徑至少遍歷每條超級超邊一次。

上述問題的算法及相關(guān)定理如下所示。

3.10 | 超級超圖中的最長簡單路徑問題

超級超圖中的最長簡單路徑問題涉及尋找一條最大長度的路徑，該路徑至多訪問每個(gè)超級頂點(diǎn)一次，并滿足由超級超邊定義的鄰接約束 [90]。本子節(jié)中考慮的問題描述如下。

3.11 | 超級超圖中的最大生成樹問題

超級超圖中的最大生成樹問題（參見 [51, 80, 85]）尋求一個(gè)超級超樹，該樹連接所有超級頂點(diǎn)，同時(shí)最大化所選超級超邊的總權(quán)重，并保持樹狀結(jié)構(gòu)約束。本子節(jié)中考慮的問題描述如下。

3.12 | 超級超圖中的 Horn 可滿足性問題

Horn 可滿足性問題確定一個(gè)合取范式的布爾公式是否可滿足，每個(gè)子句最多有一個(gè)正文字（參見 [52]）。在本子節(jié)中，我們探討超級超圖中的 Horn 可滿足性問題。相關(guān)的定義和問題概述如下所示。

4 | 本研究的未來任務(wù)

本節(jié)概述了與本研究相關(guān)的未來任務(wù)。 除了本文討論的問題之外，圖論和計(jì)算機(jī)科學(xué)中的許多經(jīng)典問題在標(biāo)準(zhǔn)圖中已廣為人知 [54]。將這些問題擴(kuò)展到超級超圖框架為未來的探索提供了一條令人興奮的途徑。 此外，我們希望進(jìn)一步的研究能夠?qū)Ｗ⒂趯⒊壋瑘D問題和算法擴(kuò)展到模糊環(huán)境 [126, 127, 101]、中性環(huán)境 [105, 37, 116, 106]、超軟環(huán)境 [47, 36, 107] 以及多元生環(huán)境 [108, 39, 48, 49, 42]。這些擴(kuò)展可能為超級超圖理論提供更深入的見解和更廣泛的應(yīng)用。

原文鏈接：https://www.researchgate.net/publication/390760743_Fundamental_Computational_Problems_and_Algorithms_for_SuperHyperGraphs