超圖和超超圖理論及其應用(四):不確定圖論

HyperGraph and SuperHyperGraph Theory with Applications (IV): Uncertain Graph Theory

https://books.google.com.tw/books?id=fVbKEQAAQBAJ&printsec=frontcover&hl=zh-CN=onepage&q&f=false

摘要

圖論研究頂點和邊的網(wǎng)絡(luò)及其相關(guān)的結(jié)構(gòu)和算法性質(zhì)[1]。為了對關(guān)系不精確的現(xiàn)實世界情境進行建模，模糊圖通過為每個頂點和邊分配一個[0, 1]區(qū)間內(nèi)的隸屬度來豐富圖的結(jié)構(gòu)[1]?；谶@一思想，中智圖和四中智圖融合了多個分量來表示真度、不確定度和假度（及其細化形式），從而提供了比模糊模型更強的表達能力。植生圖通過提供一種靈活的框架來管理屬性值和矛盾程度的不確定性，進一步拓寬了這一領(lǐng)域。除了普通圖之外，超圖允許每條邊連接頂點集的任意非空子集。迭代冪集構(gòu)造會產(chǎn)生嵌套的高階頂點對象，并導出有限的超超圖，其頂點和邊本身可能在多個層級上呈現(xiàn)集值特征。在本書中，我們考察了包括植生模型在內(nèi)的廣泛圖類、超圖類和超超圖類之間的關(guān)系，并討論了該生態(tài)系統(tǒng)內(nèi)的其他相關(guān)結(jié)構(gòu)。本卷是文獻[2]的續(xù)篇。它也是文獻[3]經(jīng)過大幅修訂和擴展的版本；因此，與文獻[3]存在某些重疊是可以預期的。

關(guān)鍵詞：中智圖，植生圖，四中智圖，模糊圖，不確定圖

第一章 引言 1.1 圖論

圖論是數(shù)學的一個重要分支，致力于研究由頂點和邊構(gòu)成的網(wǎng)絡(luò)，特別關(guān)注路徑、重復出現(xiàn)的結(jié)構(gòu)模式以及基本不變量[1]。幾十年來，它已發(fā)展成為一個成熟的學科，并在眾多領(lǐng)域的廣泛應用中提供了支持[4-6]。特別是近年來，它在人工智能領(lǐng)域發(fā)揮了重要作用，主要體現(xiàn)在圖神經(jīng)網(wǎng)絡(luò)及相關(guān)學習范式中（例如[7-11]）。

在圖論內(nèi)部，許多圖族、結(jié)構(gòu)概念和算法方法都得到了研究。具有代表性的方向包括對樹狀結(jié)構(gòu)[12,13]、基于路徑的結(jié)構(gòu)[14]以及與線性布局相關(guān)的模型[15,16]的研究。這些研究方向通常由具體目標驅(qū)動。一個反復出現(xiàn)的主題是，將關(guān)注范圍限制在性質(zhì)良好的圖類上（而非任意圖），往往能夠設(shè)計出速度更快的算法，這凸顯了基于圖類分析的實際優(yōu)勢[17]。

1.2 超圖與超超圖

經(jīng)典圖論在描述三個或更多實體同時交互的復雜網(wǎng)絡(luò)時可能有所不足。超圖通過允許每條超邊連接任意非空的頂點子集來克服這一局限，從而能夠捕捉高階交互關(guān)系[8]。盡管超圖表達能力很強，但對于許多現(xiàn)實系統(tǒng)中出現(xiàn)的分層、嵌套以及本質(zhì)上是層級結(jié)構(gòu)的關(guān)系，它可能仍然不足以建模。為彌補這一不足，F(xiàn). Smarandache 引入了超超圖的概念[18,19]。超超圖利用基于冪集的迭代構(gòu)造來編碼嵌套的連接模式和多層級關(guān)系[18,20,21]，并在近年來受到了廣泛關(guān)注[22-27]。

表1.1 突出了圖、超圖和超超圖之間的主要區(qū)別。在本書中，除非另有說明， n n 表示一個自然數(shù)（參見[2]）。有關(guān)超超圖的更多細節(jié)，請根據(jù)需要參考文獻[2]等資料。

1.3 模糊圖、中智圖、四部分中智圖與普利索圖

許多現(xiàn)實系統(tǒng)都涉及不確定性，既包括數(shù)值參數(shù)方面的不確定性，也包括概念之間關(guān)系方面的不確定性。受此啟發(fā)，幾種具有不確定性意識的圖形式體系被提出并得到積極研究，包括模糊圖、中智圖、四部分中智圖和普利索圖。

模糊圖為每個頂點和每條邊賦予一個 [ 0 , 1 ]
中的隸屬度，表示該對象歸屬于所建模結(jié)構(gòu)的程度 [29,30]。等價地，模糊圖可視為模糊集的圖論表示（參見 [31,32]）。在應用中，模糊圖已被用于在社交網(wǎng)絡(luò)、決策和交通系統(tǒng)等場景中建模不精確或不確定的關(guān)系 [29,30]。其廣泛的適用性帶來了持續(xù)的研究活動。

在模糊圖理論內(nèi)部，人們提出了許多改進和擴展，要么是為了擴展現(xiàn)有框架，要么是為了使模型更好地符合應用需求。典型的例子包括直覺模糊圖 [33]、雙極模糊圖 [34]、模糊平面圖 [35]、不規(guī)則雙極模糊圖 [36]、廣義模糊圖 [37,38] 以及復猶豫模糊圖 [39]。研究這些圖類有助于識別共享的結(jié)構(gòu)特征、開發(fā)定制化算法，并將理論成果遷移到具體問題場景中。

更廣泛地說，人們已經(jīng)發(fā)展出大量圖模型來表示不確定性和微妙的概念關(guān)系。這些模型包括但不限于模糊圖 [29,30]、含糊圖 [40-42]、普利索圖 [43-46]、概率圖 [47-49]、含糊超圖 [50]、 N N-圖 [51]、 N N-超圖 [52]、馬爾可夫圖 [53]、軟圖（軟集）[54,55]、超軟圖 [56,57] 以及粗糙圖（粗糙集）[58,59]。在這些框架中，本書主要關(guān)注中智圖和四部分中智圖 [60-62]，它們各自有著不同的發(fā)展動機。

近年來，中智圖 [60,63] 和中智超圖 [64,65] 在中智集理論 [66,67] 領(lǐng)域內(nèi)引起了越來越多的關(guān)注?！爸兄恰币辉~指的是經(jīng)典邏輯和模糊邏輯的一種擴展，其中真值、不確定性和假值被建模為獨立的分量。作為模糊圖 [29,30] 的推廣，中智圖因其靈活性和廣泛的應用前景而受到積極研究，這與模糊圖的吸引力是相似的。各種相關(guān)的中智圖和超圖類也已被提出，包括雙極中智圖 [65,68-71]、中智關(guān)聯(lián)圖 [72-75]、單值中智符號圖 [76]、強中智圖 [77]、 m m極中智圖 [78-80]、復中智超圖 [64] 和雙極中智超圖 [65]。

普利索圖 通過屬性值及其對應的隸屬度來描述每個頂點和每條邊，并引入一個矛盾（或相異度）函數(shù)來量化不同屬性值之間的不相容性，從而擴展了具有不確定性意識的圖框架 [3,81-83]。這可以看作是普利索集概念 [43,84,85] 的圖論對應物。這一額外的層次支持在網(wǎng)絡(luò)上進行依賴于上下文的、異質(zhì)且可能相互沖突的評估的聚合，從而對經(jīng)典的模糊圖、直覺模糊圖和中智圖范式進行了細化（例如 [3,86-89]）。為方便起見，表 1.2 以統(tǒng)一的符號總結(jié)了幾個代表性圖擴展中賦予頂點和邊的規(guī)范信息。

近年來， 不確定圖 和 函子圖 等概念也被作為統(tǒng)一框架進行研究，以整合的方式處理包括普利索圖在內(nèi)的這些概念。鑒于模糊數(shù)學文獻的廣度和快速增長，密切相關(guān)的概念在不同地點、不同時間被獨立提出也就不足為奇了。盡管如此，我們認為，統(tǒng)一重疊的概念十分重要，并將切實推動該領(lǐng)域的進一步進展。此外，無論是對于理論研究還是對于應用而言，比較各種具有不確定性意識的圖類都是有價值的，以便為特定問題選擇最合適的框架。

1.4 我們的貢獻

鑒于上述情況，對旨在處理不確定性的圖模型進行系統(tǒng)研究是非常相關(guān)的。關(guān)于四部中性圖（quadripartitioned neutrosophic graphs）的研究仍處于早期階段，并且遠不如模糊圖、直覺模糊圖和中性圖的相應發(fā)展那樣廣為人知。在本書中，我們引入并研究了與直覺模糊圖和四部中性圖相一致的新圖類，即一般直覺模糊圖（General Intuitionistic Fuzzy Graphs）、一般四部中性圖（General Quadripartitioned Neutrosophic Graphs）和四部中性超圖（Quadripartitioned Neutrosophic Hypergraphs）。我們還考慮了五部中性圖（Pentapartitioned Neutrosophic Graphs），其旨在處理五個不確定性參數(shù)。最后，我們考察上述提到的大多數(shù)圖模型是否可以在更廣泛的普利索真圖（plithogenic graphs）框架內(nèi)作為特例來實現(xiàn)。

我們的主要結(jié)論總結(jié)在下面的定理中。此外，我們分析了相關(guān)圖類之間的包含關(guān)系。而且，在不失一般性的情況下，同樣的結(jié)果在超圖和超超圖（superhypergraphs）的設(shè)置中也成立。

定理 1.4.1. 在所考慮的圖類中，以下陳述成立。

• 空圖（empty graph）和零圖（null graph）可以分別表示為二值圖（2-valued graphs）和三值圖（3-valued graphs）。
• 每個邊模糊圖（edge-fuzzy graph）可以通過對邊隸屬度值進行閾值化處理轉(zhuǎn)換為二值圖。
• 每個模糊圖可以通過將頂點和邊的隸屬度值映射到 { ? 1 , 0 , 1 }轉(zhuǎn)換為三值圖。
• 每個直覺模糊圖可以通過將所有頂點的非隸屬函數(shù) v A 設(shè)為 0 簡化為模糊圖。
• 每個中性圖可以通過將不確定度分量設(shè)為 0 簡化為直覺模糊圖。
• 每個五部中性圖是四部中性圖的推廣。
• 普利索真圖（Plithogenic graphs）推廣了模糊圖、直覺模糊圖、中性圖、四部中性圖和擴展五部中性圖。
• 每個一般普利索真圖可以轉(zhuǎn)換為一般四部中性圖、一般模糊圖、一般直覺模糊圖、四值模糊圖、模糊圖（Ambiguous Graph）、圖像模糊圖（Picture Fuzzy Graph）、猶豫模糊圖（Hesitant Fuzzy Graph）、直覺猶豫模糊圖（Intuitionistic Hesitant Fuzzy Graph）、模糊圖（Fuzzy Graph）、直覺模糊圖（Intuitionistic Fuzzy Graph）、中性圖（Neutrosophic Graph）、四部中性圖（Quadripartitioned Neutrosophic Graph）、五部中性圖（Pentapartitioned Neutrosophic Graph）、四部中性圖（Quadripartitioned Neutrosophic Graph）、擴展五部中性圖（Extended Pentapartitioned Neutrosophic Graph）和球形模糊圖（Spherical Fuzzy Graph）。
• 每個不確定圖（Uncertain Graph）可以轉(zhuǎn)換為普利索真圖。

此外，為了闡明這些圖類之間的關(guān)系，我們作為副產(chǎn)品證明了針對個別類的幾個額外定理，并研究了說明性的應用實例。

除了作為 [2] 的續(xù)篇和 [3] 的實質(zhì)修訂和擴展版本外，本卷與 [3] 的主要區(qū)別在于，它納入了對超超圖（SuperHyperGraphs）的擴展討論，并用對四部中性圖的討論取代了對 Turiyam 中性圖的討論。我們還盡可能改進了證明和陳述的定義。

原文鏈接：https://books.google.com.tw/books?id=fVbKEQAAQBAJ&printsec=frontcover&hl=zh-CN=onepage&q&f=true