超圖和超超圖理論及其應用

HyperGraph and SuperHyperGraph Theorywith Applications

超圖和超超圖理論及其應用

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

摘要

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

為了幫助彌合這一差距，本書呈現了一份關于超級超圖相關基礎和高級概念的綜述。我們的目標是雙重的：(i) 增加超級超圖理論的可見性和可及性，從而刺激進一步的研究，以及 (ii) 加深從事基于圖和超圖模型工作的研究人員和從業者對其結構的數學理解。

關鍵詞：超級超圖理論，超圖理論， ( m , n )
-超級超圖理論，不確定圖理論，圖應用

第 1 章 引言

1.1 圖、超圖和超級超圖

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

圖和超圖為復雜系統提供了直觀的視覺隱喻，并支持人工智能、網絡科學、數據挖掘、信息學、化學、物理學及其他領域的廣泛應用 [8–11]。通過明確容納層次和多層關系，超級超圖為建模和分析現代網絡數據中遇到的復雜結構提供了一個強大的框架（例如，[12–14, 14–16]）。

表 1.1 總結了圖、超圖和超級超圖之間的關鍵區別。在本書中，除非另有說明， 被視為自然數。

使用超級超圖的優勢包括幾個眾所周知的好處，例如：

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

圖、超圖和超級超圖結構已在廣泛的應用領域中得到研究。代表性示例總結在表 1.2 和 1.3 中。需要注意的是，超級超圖的研究仍處于早期階段，在撰寫本文時，大多數現有工作仍然是理論性的。因此，未來的研究預計將包括更多由計算實驗、機器學習技術和領域專家進行的詳細案例研究支持的實用研究。

1.3 我們的貢獻

從上述討論中可以清楚地看出，超級超圖對于建模層次結構和多路結構具有極其重要的意義。然而，與關于圖和超圖的廣泛文獻相比，關于超級超圖的系統研究仍然相對有限。

為了幫助彌合這一差距，本書提供了一份關于超級超圖相關基礎和高級概念的綜述。我們的目標是雙重的：(i) 提高超級超圖理論的可見性和可及性，從而刺激進一步的研究；以及 (ii) 加深從事基于圖和超圖模型工作的研究人員和從業者對這些結構的數學理解。

本書主要聚焦于理論發展。我們真誠地希望，相關領域的專家能夠開展進一步的計算實驗和現實世界的案例研究。

第 2 章 預備知識：基本超級超圖理論

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

2.1 圖和超圖

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

通過這種方式，超邊編碼了多人協作關系，這是普通的（成對）圖邊無法單獨捕捉的。

2.2 超級超圖

超級超圖通過從基集的迭代冪集形成頂點和邊，將這一思想進一步推進；這種觀點已出現在最近的幾個研究中 [7,106,107]。據報道，其應用包括分子結構建模、復雜網絡分析和信號處理等 [108–112]。在整個過程中，層級 n n 是一個固定的非負整數。我們簡要介紹定義以及相關概念。

表 2.1 再次展示了圖、超圖和超級超圖之間的概念關系。超級超圖有望為表示現實世界系統中出現的層次網絡結構提供一個清晰且富有表現力的框架。我們在下面給出超級超圖的具體例子。

例 2.2.4（作為 2-超級超圖的大學課程束網絡）。大學課程是一個結構化的課程集合，被組織成模塊和項目，以指導學生的學術進展 [117, 118]。我們對大學課程的一小部分進行建模，其中課程被分組為模塊，并且幾個模塊被組合成學位項目模式。

例 2.2.5（作為 3-超級超圖的多醫院監測協議）。 近年來，多醫院管理已變得日益必要 [119, 120]。我們要對不同醫院如何組織多級生命體征監測協議進行建模。

步驟 1：基集和第一級組合。設原子生命體征信號的基集為

2.3 超級超圖的推廣定理

超級超圖可以推廣多種圖及相關數學結構。作為一個說明性的起點，我們明確考察超級超圖如何推廣幾個經典對象，即抽象單純復形、有限擬陣和平衡不完全區組設計（BIBDs）。

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

定理 2.3.8（超級超圖的普適性）。 下列每一個結構都可以忠實地表示為一個 n n-超級超圖：

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

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