多向圖擴(kuò)展：模糊、中性、Plithogenic、粗糙、軟、超圖及超超圖變體

Extensions of Multidirected Graphs: Fuzzy, Neutrosophic,Plithogenic, Rough, Soft, Hypergraph, and Superhypergraph Variants

https://www.mdpi.com/2813-9542/2/3/11

1. 結(jié)論與未來(lái)工作

在本文中，我們通過(guò)引入多向超圖（Multidirected hypergraph）擴(kuò)展了傳統(tǒng)的圖論模型，該模型統(tǒng)一了超圖的多路連接性與超超圖的分層冪集結(jié)構(gòu)。在此基礎(chǔ)上，我們制定了五種感知不確定性的多向變體——模糊、中智、普利托根、粗糙和軟多向圖——每一種都配備了精確的定義和具體的示例。我們還介紹了另外四個(gè)圖族（雙混合圖、多混合圖、超有向圖和超超有向圖），并考察了它們的關(guān)鍵結(jié)構(gòu)性質(zhì)。

盡管取得了這些理論進(jìn)展，針對(duì)多向圖及相關(guān)超結(jié)構(gòu)的實(shí)用工具包和算法仍處于起步階段。未來(lái)的工作將集中在：

• 算法開(kāi)發(fā)：設(shè)計(jì)用于多向和超有向網(wǎng)絡(luò)遍歷、查詢(xún)和分析的高效例程。
• 軟件實(shí)現(xiàn)：創(chuàng)建支持這些新圖類(lèi)的構(gòu)建、可視化和操作的開(kāi)源庫(kù)。
• 機(jī)器學(xué)習(xí)集成：將感知不確定性的多向圖嵌入圖神經(jīng)網(wǎng)絡(luò)和其他學(xué)習(xí)架構(gòu)中，以處理復(fù)雜的、分層的或不精確的數(shù)據(jù)。
• 應(yīng)用與案例研究：在生物信息學(xué)、社會(huì)網(wǎng)絡(luò)分析和決策支持系統(tǒng)等領(lǐng)域驗(yàn)證所提出的模型，在這些領(lǐng)域中，多頭和不確定關(guān)系自然產(chǎn)生。

我們預(yù)計(jì)，將更深層的理論見(jiàn)解與實(shí)用工具相結(jié)合，將開(kāi)啟豐富的應(yīng)用場(chǎng)景，并激發(fā)關(guān)于不確定性下高級(jí)圖結(jié)構(gòu)的進(jìn)一步研究。

摘要

圖論通過(guò)將實(shí)體表示為頂點(diǎn)并將它們的交互表示為邊來(lái)對(duì)關(guān)系進(jìn)行建模。為了處理方向性和多重頭尾分配，各種擴(kuò)展——有向圖、雙向圖和多向圖——已被引入，其中多向圖統(tǒng)一了前兩者。在這項(xiàng)工作中，我們通過(guò)提出多向超圖進(jìn)一步豐富了這一領(lǐng)域，它融合了超圖和超超圖的靈活性以描述高階和層次連接。在此基礎(chǔ)上，我們通過(guò)將經(jīng)典不確定性模型嵌入到多向設(shè)定中，引入了五個(gè)感知不確定性的多向框架——模糊、中智、普利托根、粗糙和軟多向圖。我們概述了它們的形式定義，考察了關(guān)鍵結(jié)構(gòu)性質(zhì)，并用示例說(shuō)明了每一個(gè)，從而為不確定圖分析和決策方面的未來(lái)進(jìn)展奠定基礎(chǔ)。

關(guān)鍵詞：超超圖；超圖；模糊圖；中智圖；多向圖；多向超圖；粗糙圖；軟圖

1. 引言

1.1. 各種圖論框架

圖論提供了一個(gè)框架，其中實(shí)體由頂點(diǎn)表示，它們的成對(duì)交互由邊表示，支撐著人工智能、網(wǎng)絡(luò)分析和化學(xué)建模等領(lǐng)域的多樣化應(yīng)用 [1,2]。在本文中，我們探討以下概念： ? 超圖和超超圖：普通圖的高階和層次推廣 [3–7] ? 模糊、直覺(jué)模糊、中智和普利托根圖：用于建模不確定性和矛盾的框架 [8–12] ? 有向、雙向和多向圖：用于表示不對(duì)稱(chēng)和多頭連接的結(jié)構(gòu) [13–18]。

1.1.1. 超圖和超超圖

雖然標(biāo)準(zhǔn)圖僅允許頂點(diǎn)之間的成對(duì)邊，但超圖通過(guò)允許每條超邊連接頂點(diǎn)的任何非空子集來(lái)推廣這一概念，從而捕捉高階關(guān)系 [7,19–23]。超超圖通過(guò)迭代應(yīng)用冪集操作將這一點(diǎn)進(jìn)一步推進(jìn)：在每一層，“超頂點(diǎn)”和“超邊”都取自前一層的冪集，從而產(chǎn)生一個(gè)多層連接層次結(jié)構(gòu) [24–27]。表 1 對(duì)比了普通圖、超圖和 n-超超圖的關(guān)鍵特征。

1.1.2. 不確定性下的圖模型

經(jīng)典圖論的幾種擴(kuò)展已被提出，以容納頂點(diǎn)和邊中的不確定性。在模糊圖中，每個(gè)頂點(diǎn)和邊被分配一個(gè) [0, 1] 中的隸屬度值，以表達(dá)漸進(jìn)包含 [8,9]。直覺(jué)模糊圖進(jìn)一步區(qū)分了非隸屬度與隸屬度 [28–31]，而中智圖則在真值和假值水平之外引入了一個(gè)不確定分量 [32–34]。普利托根圖通過(guò)量化屬性值之間的矛盾將這一點(diǎn)進(jìn)一步推進(jìn) [35]。替代方法包括粗糙圖，其使用下近似和上近似來(lái)處理節(jié)點(diǎn)和邊中的模糊性 [36,37]，軟圖，其通過(guò)軟集理論參數(shù)化頂點(diǎn)和邊的子集 [38,39]，以及含糊圖，其使用含糊集對(duì)歧義性進(jìn)行建模 [40–42]。

表 2 提供了這些感知不確定性的圖框架的概述。

1.1.3. 有向、雙向和多向圖

為了捕捉方向性和多重關(guān)系，一系列圖擴(kuò)展已被引入。有向圖為每條邊分配單一方向，而雙向圖允許邊兩端的每個(gè)頂點(diǎn)擁有其自己獨(dú)立的方向 [43]。多向圖通過(guò)允許在同一對(duì)頂點(diǎn)之間存在多條有向邊（?。﹣?lái)推廣這兩種模型，每條邊都有其自己的方向和多重性 [44,45]。

在本文中，我們專(zhuān)注于多向圖，因?yàn)樗鼈兺ㄟ^(guò)對(duì)邊方向和計(jì)數(shù)的顯式編碼，涵蓋了有向和雙向結(jié)構(gòu)兩者。表 3 總結(jié)了有向、雙向和多向圖變體之間的差異。

1.2. 我們的貢獻(xiàn)

基于這些發(fā)展，本文通過(guò)結(jié)合多向圖與現(xiàn)有的圖和超圖擴(kuò)展，定義了一套新的多向結(jié)構(gòu)。我們引入了模糊多向圖、中智多向圖、普利托根多向圖、粗糙多向圖、軟多向圖、多向超圖和多向超超圖。除了這些之外，我們還探索了幾種新的圖類(lèi)，例如雙混合圖和超有向圖。對(duì)于每一個(gè)這些類(lèi)，我們提出了形式定義，研究了它們的核心數(shù)學(xué)性質(zhì)，并用具體示例說(shuō)明了它們。 需要注意的是，本文是一項(xiàng)完全在概念層面進(jìn)行的理論研究。在整篇論文中，我們假設(shè)所有圖都是有限的。我們預(yù)計(jì)這些貢獻(xiàn)將增強(qiáng)圖論及其多樣化擴(kuò)展的理論基礎(chǔ)和潛在應(yīng)用。

1.3. 本文結(jié)構(gòu)

本小節(jié)概述了論文的結(jié)構(gòu)。第 2 節(jié)介紹了一系列基礎(chǔ)圖結(jié)構(gòu)，包括超圖、超超圖、有向圖、有向超圖、有向超超圖、模糊圖、中智圖、普利托根圖、模糊有向圖、中智有向圖、普利托根有向圖、雙向圖和多向圖。第 3 節(jié)考察了高級(jí)變體的結(jié)構(gòu)性質(zhì)，例如模糊多向圖、中智多向圖、普利托根多向圖、粗糙多向圖、軟多向圖、多向超圖和多向超超圖。它還探索了新提出的圖類(lèi)的特征，包括雙混合圖。第 4 節(jié)提供了結(jié)論的簡(jiǎn)要總結(jié)，并討論了未來(lái)研究的方向。

1. 預(yù)備知識(shí)

在本節(jié)中，我們回顧了支撐本文發(fā)展的基本概念和符號(hào)。我們?cè)谡麄€(gè)過(guò)程中將注意力限制在有限圖上。除非另有說(shuō)明，符號(hào) n 將始終表示一個(gè)非負(fù)整數(shù)。

2.1. 圖和超圖

超圖通過(guò)允許超邊——大小至少為二的頂點(diǎn)集子集——擴(kuò)展了普通圖的概念，從而捕捉元素之間的多路關(guān)系 [47–54]。下面是圖、其子圖和超圖的形式定義。

是一個(gè)超圖，其中每條超邊代表一個(gè)同時(shí)連接多種配料的食譜。這種結(jié)構(gòu)自然地模擬了烹飪應(yīng)用中配料之間的高階關(guān)系。

2.2. 冪集與 n 次冪集

2.3. 超結(jié)構(gòu)和超超結(jié)構(gòu)

為了構(gòu)建超結(jié)構(gòu) [63–68] 及其高階對(duì)應(yīng)物超超結(jié)構(gòu) [61] 的統(tǒng)一理論框架，我們回顧幾個(gè)基本定義。特別是，任何超圖都可以被視為一個(gè)超結(jié)構(gòu)，同樣地，一個(gè)超超圖自然地誘導(dǎo)一個(gè)超超結(jié)構(gòu)。

定義 6（經(jīng)典結(jié)構(gòu) [61,69]）。一個(gè)經(jīng)典結(jié)構(gòu)由一個(gè)非空集 H 以及一個(gè)或多個(gè)運(yùn)算組成——稱(chēng)為經(jīng)典運(yùn)算——它們將元素元組映射回 H 中并滿(mǎn)足規(guī)定的公理。形式上，一個(gè) m 元經(jīng)典運(yùn)算是一個(gè)函數(shù)

因此， H 模擬了獨(dú)立的子項(xiàng)目如何被動(dòng)態(tài)連接，并且任務(wù)子集上的并集運(yùn)算正是賦予 H 其超結(jié)構(gòu)特征的超運(yùn)算。

定義 9（超超運(yùn)算 [61]）。設(shè) H 是一個(gè)非空集，并通過(guò)以下方式定義其迭代冪集：

2.4. 超超圖

超超圖通過(guò)迭代冪集構(gòu)造 [26,73] 嵌入遞歸、分層結(jié)構(gòu)，從而推廣了超圖的概念。本質(zhì)上，通過(guò)重復(fù)取冪集，構(gòu)建連續(xù)的頂點(diǎn)和邊“層級(jí)”，從而產(chǎn)生一個(gè)豐富的、分層網(wǎng)絡(luò)。

2.5. 有向超圖

有向超圖通過(guò)允許每條“邊”（通常稱(chēng)為超弧）源自多個(gè)源頂點(diǎn)并終止于單個(gè)目標(biāo)頂點(diǎn)，從而推廣了有向圖。這種更豐富的結(jié)構(gòu)已在數(shù)據(jù)庫(kù)依賴(lài)、生物信息學(xué)和復(fù)雜網(wǎng)絡(luò)模型等領(lǐng)域找到應(yīng)用（參見(jiàn)，例如，[76,77]）。

2.6. 普利托根和軟有向圖

模糊集 [80–82]、直覺(jué)模糊集 [83–85]、中智集 [86–88] 和普利托根集 [89,90] 的經(jīng)典概念啟發(fā)了一系列相應(yīng)的圖模型。特別是，人們會(huì)遇到模糊圖 [8,91]、直覺(jué)模糊圖 [92,93]、中智圖 [94,95] 和普利托根圖 [35,96]。它們的有向?qū)?yīng)物——模糊有向圖 [97,98]、直覺(jué)模糊有向圖 [99,100]、中智有向圖 [101,102] 和普利托根有向圖 [103]——也已被開(kāi)發(fā)。下面，我們回顧這四個(gè)有向圖變體的形式定義。

定義 16（模糊有向圖 [97,104]）。一個(gè)模糊有向圖是一個(gè)四元組

2.7. 粗糙圖和粗糙有向圖

粗糙圖利用頂點(diǎn)和邊上的等價(jià)關(guān)系來(lái)定義下近似和上近似，從而捕捉無(wú)向網(wǎng)絡(luò)結(jié)構(gòu)中的模糊性 [109–112]。粗糙有向圖將粗糙圖的概念擴(kuò)展到有向網(wǎng)絡(luò)，通過(guò)基于等價(jià)關(guān)系的下界和上界來(lái)近似頂點(diǎn)和弧 [36,37]。我們現(xiàn)在回顧粗糙集的概念及其在圖和有向圖中的應(yīng)用。

2.8. 多向圖

多向圖通過(guò)允許任意兩個(gè)頂點(diǎn)之間存在多條有向邊，統(tǒng)一了有向圖 [44,45] 和雙向圖 [115,116] 的特征。我們首先回顧雙向圖。

2.9. 混合圖

混合圖在一個(gè)單一框架中整合了無(wú)向邊和有向邊 [117–121]?；旌蠄D已在圖著色等領(lǐng)域得到研究。

1. 本文結(jié)果

本節(jié)介紹了本文的主要結(jié)果。我們通過(guò)引入多重邊結(jié)構(gòu)（即邊多重性）擴(kuò)展了有向圖和超圖的經(jīng)典概念，并進(jìn)一步融合了包括模糊、中智和普利托根系統(tǒng)在內(nèi)的先進(jìn)框架。這些推廣旨在捕捉復(fù)雜網(wǎng)絡(luò)中各種形式的不確定性、矛盾和基于屬性的推理。

3.1. 多向超圖

多向超圖通過(guò)允許有向超邊將任意非空源頂點(diǎn)集（尾部）連接到單個(gè)目標(biāo)頂點(diǎn)（頭部），從而推廣了普通超圖，并通過(guò)為每條超邊記錄一個(gè)正整數(shù)多重性來(lái)模擬平行出現(xiàn)的情況。

原文鏈接：https://www.mdpi.com/2813-9542/2/3/11