HyperGraph and SuperHyperGraph Theorywith Applications

超圖和超超圖理論及其應(yīng)用

https://philpapers.org/archive/TAKHAS-2.pdf

摘要

超圖通過允許連接超過兩個(gè)頂點(diǎn)的超邊，推廣了這一框架 [1]。超級(jí)超圖通過迭代冪集構(gòu)造進(jìn)一步豐富了該模型，捕捉了超邊之間的層次和自引用結(jié)構(gòu) [2]。一個(gè) ( m , n ) -超級(jí)超圖是一種數(shù)學(xué)結(jié)構(gòu)，其中每個(gè)頂點(diǎn)對(duì)應(yīng)于定義在基集上的一個(gè) ( m , n )
-超級(jí)超函數(shù)，而超邊將此類函數(shù)分組在一起以表示高階關(guān)系和上下文連接。與關(guān)于圖和超圖的廣泛文獻(xiàn)相比，關(guān)于超級(jí)超圖的系統(tǒng)研究仍然相對(duì)有限。

為了幫助彌合這一差距，本書呈現(xiàn)了一份關(guān)于超級(jí)超圖相關(guān)基礎(chǔ)和高級(jí)概念的綜述。我們的目標(biāo)是雙重的：(i) 增加超級(jí)超圖理論的可見性和可及性，從而刺激進(jìn)一步的研究，以及 (ii) 加深從事基于圖和超圖模型工作的研究人員和從業(yè)者對(duì)其結(jié)構(gòu)的數(shù)學(xué)理解。

關(guān)鍵詞：超級(jí)超圖理論，超圖理論， ( m , n )
-超級(jí)超圖理論，不確定圖理論，圖應(yīng)用

第 1 章 引言

1.1 圖、超圖和超級(jí)超圖

網(wǎng)絡(luò)建模通常依賴于圖，其中實(shí)體由頂點(diǎn)表示，二元關(guān)系由邊表示 [3]。然而，經(jīng)典圖可能不足以描述三個(gè)或更多實(shí)體同時(shí)交互的復(fù)雜網(wǎng)絡(luò)。超圖通過允許每個(gè)超邊連接頂點(diǎn)的任意非空子集來解決這一限制，從而捕捉高階交互 [4]。盡管具有表達(dá)能力，超圖可能仍然不足以表示許多現(xiàn)實(shí)世界系統(tǒng)中出現(xiàn)的分層、嵌套和固有層次關(guān)系。為了彌合這一差距，F(xiàn). Smarandache 引入了超級(jí)超圖的概念。超級(jí)超圖采用基于迭代冪集的構(gòu)造來編碼嵌套連接模式和多層關(guān)系 [2,5]，并且最近引起了大量關(guān)注 [6, 7]。

圖和超圖為復(fù)雜系統(tǒng)提供了直觀的視覺隱喻，并支持人工智能、網(wǎng)絡(luò)科學(xué)、數(shù)據(jù)挖掘、信息學(xué)、化學(xué)、物理學(xué)及其他領(lǐng)域的廣泛應(yīng)用 [8–11]。通過明確容納層次和多層關(guān)系，超級(jí)超圖為建模和分析現(xiàn)代網(wǎng)絡(luò)數(shù)據(jù)中遇到的復(fù)雜結(jié)構(gòu)提供了一個(gè)強(qiáng)大的框架（例如，[12–14, 14–16]）。

表 1.1 總結(jié)了圖、超圖和超級(jí)超圖之間的關(guān)鍵區(qū)別。在本書中，除非另有說明， 被視為自然數(shù)。

使用超級(jí)超圖的優(yōu)勢(shì)包括幾個(gè)眾所周知的好處，例如：

• 通過迭代冪集自然地建模層次結(jié)構(gòu)。
• 在統(tǒng)一框架內(nèi)表示多路、多級(jí)關(guān)系。
• 包含圖 [3]、多圖 [18,19]、子頂點(diǎn)圖 [20–22]、超圖 [17]、超圖 [23]、h-模型 [24]、準(zhǔn)超級(jí)超圖 [5]、冪集圖 [25]、k-鏈自由集 [26]、約翰遜圖 [27]、克內(nèi)瑟圖 [28] 和多超圖 [29] 作為特殊（扁平化）實(shí)例。
• 在每一層支持豐富的屬性系統(tǒng)（模糊、直覺模糊、中智、plithogenic [2]）。
• 為真正的層次系統(tǒng)（如課程或供應(yīng)鏈網(wǎng)絡(luò)）提供更好的適配。

圖、超圖和超級(jí)超圖結(jié)構(gòu)已在廣泛的應(yīng)用領(lǐng)域中得到研究。代表性示例總結(jié)在表 1.2 和 1.3 中。需要注意的是，超級(jí)超圖的研究仍處于早期階段，在撰寫本文時(shí)，大多數(shù)現(xiàn)有工作仍然是理論性的。因此，未來的研究預(yù)計(jì)將包括更多由計(jì)算實(shí)驗(yàn)、機(jī)器學(xué)習(xí)技術(shù)和領(lǐng)域?qū)＜疫M(jìn)行的詳細(xì)案例研究支持的實(shí)用研究。

1.3 我們的貢獻(xiàn)

從上述討論中可以清楚地看出，超級(jí)超圖對(duì)于建模層次結(jié)構(gòu)和多路結(jié)構(gòu)具有極其重要的意義。然而，與關(guān)于圖和超圖的廣泛文獻(xiàn)相比，關(guān)于超級(jí)超圖的系統(tǒng)研究仍然相對(duì)有限。

為了幫助彌合這一差距，本書提供了一份關(guān)于超級(jí)超圖相關(guān)基礎(chǔ)和高級(jí)概念的綜述。我們的目標(biāo)是雙重的：(i) 提高超級(jí)超圖理論的可見性和可及性，從而刺激進(jìn)一步的研究；以及 (ii) 加深從事基于圖和超圖模型工作的研究人員和從業(yè)者對(duì)這些結(jié)構(gòu)的數(shù)學(xué)理解。

本書主要聚焦于理論發(fā)展。我們真誠地希望，相關(guān)領(lǐng)域的專家能夠開展進(jìn)一步的計(jì)算實(shí)驗(yàn)和現(xiàn)實(shí)世界的案例研究。

第 2 章 預(yù)備知識(shí)：基本超級(jí)超圖理論

我們匯集了后文中使用的基本術(shù)語和符號(hào)。除非另有明確說明，所有考慮的圖均為有限、無向且無自環(huán)的；僅在指定時(shí)允許存在多重邊。

2.1 圖和超圖

圖和超圖是離散結(jié)構(gòu)的基本組合模型。經(jīng)典（無向）圖可以被視為超圖的一種特殊情況，其中每條邊恰好包含兩個(gè)頂點(diǎn) [3]。相比之下，經(jīng)典超圖允許一條邊連接任意（有限）數(shù)量的頂點(diǎn)，使其適合表示多路關(guān)系 [1, 102, 103]。我們簡要介紹定義以及相關(guān)概念。

通過這種方式，超邊編碼了多人協(xié)作關(guān)系，這是普通的（成對(duì)）圖邊無法單獨(dú)捕捉的。

2.2 超級(jí)超圖

超級(jí)超圖通過從基集的迭代冪集形成頂點(diǎn)和邊，將這一思想進(jìn)一步推進(jìn)；這種觀點(diǎn)已出現(xiàn)在最近的幾個(gè)研究中 [7,106,107]。據(jù)報(bào)道，其應(yīng)用包括分子結(jié)構(gòu)建模、復(fù)雜網(wǎng)絡(luò)分析和信號(hào)處理等 [108–112]。在整個(gè)過程中，層級(jí) n n 是一個(gè)固定的非負(fù)整數(shù)。我們簡要介紹定義以及相關(guān)概念。

表 2.1 再次展示了圖、超圖和超級(jí)超圖之間的概念關(guān)系。超級(jí)超圖有望為表示現(xiàn)實(shí)世界系統(tǒng)中出現(xiàn)的層次網(wǎng)絡(luò)結(jié)構(gòu)提供一個(gè)清晰且富有表現(xiàn)力的框架。我們?cè)谙旅娼o出超級(jí)超圖的具體例子。

例 2.2.4（作為 2-超級(jí)超圖的大學(xué)課程束網(wǎng)絡(luò)）。大學(xué)課程是一個(gè)結(jié)構(gòu)化的課程集合，被組織成模塊和項(xiàng)目，以指導(dǎo)學(xué)生的學(xué)術(shù)進(jìn)展 [117, 118]。我們對(duì)大學(xué)課程的一小部分進(jìn)行建模，其中課程被分組為模塊，并且?guī)讉€(gè)模塊被組合成學(xué)位項(xiàng)目模式。

例 2.2.5（作為 3-超級(jí)超圖的多醫(yī)院監(jiān)測(cè)協(xié)議）。 近年來，多醫(yī)院管理已變得日益必要 [119, 120]。我們要對(duì)不同醫(yī)院如何組織多級(jí)生命體征監(jiān)測(cè)協(xié)議進(jìn)行建模。

步驟 1：基集和第一級(jí)組合。設(shè)原子生命體征信號(hào)的基集為

2.3 超級(jí)超圖的推廣定理

超級(jí)超圖可以推廣多種圖及相關(guān)數(shù)學(xué)結(jié)構(gòu)。作為一個(gè)說明性的起點(diǎn)，我們明確考察超級(jí)超圖如何推廣幾個(gè)經(jīng)典對(duì)象，即抽象單純復(fù)形、有限擬陣和平衡不完全區(qū)組設(shè)計(jì)（BIBDs）。

因此，每個(gè)有限擬陣都可以被視為一個(gè) 1-超級(jí)超圖，在其超級(jí)邊上滿足特定的關(guān)聯(lián) - 正則性約束，反之，任何這種形式的 1-超級(jí)超圖都確定一個(gè)擬陣。因此，有限擬陣是 1-超級(jí)超圖的特例。

定理 2.3.8（超級(jí)超圖的普適性）。 下列每一個(gè)結(jié)構(gòu)都可以忠實(shí)地表示為一個(gè) n n-超級(jí)超圖：

• 普通圖；
• 超圖 [17]；
• 多重圖 [18,19]；
• 超級(jí)圖 [23]；
• 多重超圖 [29]；
• 準(zhǔn)超級(jí)超圖 [5]；
• n n 次冪圖 [129]；
• 子集-頂點(diǎn)圖 [22]；
• 子集-頂點(diǎn)多重圖 [20]；
• h-模型 [24]；
• k-鏈自由超圖 [26]；
• 冪集圖 [130]；
• n n 次冪集圖 [128]；
• 約翰遜圖 [131]；
• 克內(nèi)瑟圖 [132]；
• 集合 [105]；
• 多重集 [133]；
• 迭代多重集 [134]；
• 冪集 [130]；
• n n 次冪集 [135]；
• 抽象單純復(fù)形 [136,137]；
• 有限擬陣 [125]；
• 平衡不完全區(qū)組設(shè)計(jì) (BIBDs) [127,138]。

原文鏈接：https://philpapers.org/archive/TAKHAS-2.pdf