超超圖的基本計算問題與算法

超超圖的基本計算問題與算法

Fundamental Computational Problems and Algorithms for SuperHyperGraphs

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

摘要

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

關鍵詞：超級超圖，超圖，樹寬，算法

1 | 引言

1.1 | 圖與超圖

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

1.2 | 圖寬參數

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

1.3 | 計算復雜性

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

1.4 | 本文的貢獻

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

? 超級超圖的精確構造：開發了一種算法，從給定的頂點和邊集構造超級超圖。

? 識別超級超樹：提供一種算法來確定給定結構是否是有效的超級超樹。

? 超級超樹寬的計算： – 精確算法：

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

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

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

? 超級超圖中的可達性問題：探索算法以驗證超級超圖中兩個頂點之間是否存在路徑。

? 最小生成超級超樹問題：提出一種方法來計算具有最小總邊權的超級超樹。 ? 超級超圖中的單源最短路徑問題：開發一種算法來查找超級超圖中從單個源頂點出發的最短路徑。

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

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

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

? 超級超圖中的最大生成樹問題：提出算法來計算具有最大總邊權的超級超樹。

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

2 | 預備知識和定義

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

2.1 | 圖與超圖

圖論提供了一個基礎框架來分析網絡，網絡由節點（頂點）及其連接（邊）組成。超圖通過允許超邊擴展了傳統圖的概念，超邊可以連接多個頂點而不僅僅是成對，從而能夠表示元素之間更復雜的關系 [58, 13, 60, 11, 12, 59]。圖和超圖的基本定義如下所示。

2.2 | 樹寬和超樹寬

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

2.3 | 超級超圖與超級超樹

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

2.4 | 超級超樹寬

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

2.5 | 算法的基本定義

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

3 | 本文的結果

本文的結果如下所示。

3.1 | 精確構造超級超圖

我們考慮構造超級超圖的算法。本子節中考慮的問題描述如下。

上述問題的算法及相關定理如下所示。

3.3 | 超級超樹寬的計算

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

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

3.4 | 超級超圖劃分問題

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

3.5 | 超級超圖中的可達性問題

可達性問題確定在圖或超圖中使用其邊是否存在兩個頂點之間的路徑 [7, 8]。本子節中考慮的問題描述如下。

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

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

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

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

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

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

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

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

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

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

上述問題的算法及相關定理如下所示。

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

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

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

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

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

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

4 | 本研究的未來任務

本節概述了與本研究相關的未來任務。 除了本文討論的問題之外，圖論和計算機科學中的許多經典問題在標準圖中已廣為人知 [54]。將這些問題擴展到超級超圖框架為未來的探索提供了一條令人興奮的途徑。 此外，我們希望進一步的研究能夠專注于將超級超圖問題和算法擴展到模糊環境 [126, 127, 101]、中性環境 [105, 37, 116, 106]、超軟環境 [47, 36, 107] 以及多元生環境 [108, 39, 48, 49, 42]。這些擴展可能為超級超圖理論提供更深入的見解和更廣泛的應用。

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