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

Fundamental Computational Problems and Algorithms for SuperHyperGraphs

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

摘要

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

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

1 | 引言

1.1 | 圖與超圖

圖論作為分析網(wǎng)絡(luò)的基礎(chǔ)框架，由節(jié)點(diǎn)（頂點(diǎn)）及其連接（邊）組成。它為不同網(wǎng)絡(luò)的結(jié)構(gòu)、連通性和屬性提供了寶貴的見解 [28]。 超圖通過(guò)允許邊（稱為超邊）連接兩個(gè)以上的頂點(diǎn)，而不僅僅是成對(duì)頂點(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ò)展，超級(jí)超圖引入了更大的靈活性，是近期研究中新興的興趣主題 [109, 110]。超級(jí)超圖泛化了超圖，允許頂點(diǎn)和超邊表示集合或子集，從而能夠建模層次化和復(fù)雜的關(guān)系。 在圖、超圖和超級(jí)超圖的背景下，樹結(jié)構(gòu)已被廣泛研究。例如，超樹已在超圖中得到探索 [58]，而超級(jí)超樹已在超級(jí)超圖中得到研究 [55]。樹結(jié)構(gòu)的概念被廣泛采用，是因?yàn)樗鼈冊(cè)趹?yīng)用中的簡(jiǎn)單性和效率。除了圖相關(guān)概念外，樹結(jié)構(gòu)已應(yīng)用于各種領(lǐng)域，包括樹自動(dò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ù)評(píng)估圖接近樹結(jié)構(gòu)的程度，這對(duì)于許多實(shí)際應(yīng)用至關(guān)重要。 對(duì)于超圖，類似參數(shù)如超樹寬 [57, 59, 125, 79, 3] 和超路徑寬 [87, 82, 2] 已被開發(fā)出來(lái)。這些度量衡量超圖與樹或路徑的相似程度，滿足了將基于樹的分析擴(kuò)展到更復(fù)雜結(jié)構(gòu)的需求。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

? 超級(jí)超圖中的最長(zhǎng)簡(jiǎn)單路徑問(wèn)題：研究識(shí)別超級(jí)超圖中最長(zhǎng)無(wú)環(huán)路徑的方法。

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

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

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

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

2.1 | 圖與超圖

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

2.2 | 樹寬和超樹寬

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

2.3 | 超級(jí)超圖與超級(jí)超樹

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

2.4 | 超級(jí)超樹寬

超級(jí)超樹寬是超樹寬的一種抽象，擴(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)造超級(jí)超圖

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

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

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

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

3.3.2 | 超級(jí)超樹寬的近似算法

3.4 | 超級(jí)超圖劃分問(wèn)題

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

3.5 | 超級(jí)超圖中的可達(dá)性問(wèn)題

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

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

3.6 | 最小生成超級(jí)超樹問(wèn)題

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

3.7 | 超級(jí)超圖中的單源最短路徑問(wèn)題

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

3.8 | 超級(jí)超圖中的旅行商問(wèn)題

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

3.9 | 超級(jí)超圖中的中國(guó)郵遞員問(wèn)題 (CPP)

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

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

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

3.10 | 超級(jí)超圖中的最長(zhǎng)簡(jiǎn)單路徑問(wèn)題

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

3.11 | 超級(jí)超圖中的最大生成樹問(wèn)題

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

3.12 | 超級(jí)超圖中的 Horn 可滿足性問(wèn)題

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

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

本節(jié)概述了與本研究相關(guān)的未來(lái)任務(wù)。 除了本文討論的問(wèn)題之外，圖論和計(jì)算機(jī)科學(xué)中的許多經(jīng)典問(wèn)題在標(biāo)準(zhǔn)圖中已廣為人知 [54]。將這些問(wèn)題擴(kuò)展到超級(jí)超圖框架為未來(lái)的探索提供了一條令人興奮的途徑。 此外，我們希望進(jìn)一步的研究能夠?qū)Ｗ⒂趯⒊?jí)超圖問(wèn)題和算法擴(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ò)展可能為超級(jí)超圖理論提供更深入的見解和更廣泛的應(yīng)用。

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