超图和超超图理论及其应用(四):不确定图论

超图和超超图理论及其应用(四):不确定图论

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

摘要

图论研究顶点和边的网络及其相关的结构和算法性质[1]。为了对关系不精确的现实世界情境进行建模，模糊图通过为每个顶点和边分配一个[0, 1]区间内的隶属度来丰富图的结构[1]。基于这一思想，中智图和四中智图融合了多个分量来表示真度、不确定度和假度（及其细化形式），从而提供了比模糊模型更强的表达能力。植生图通过提供一种灵活的框架来管理属性值和矛盾程度的不确定性，进一步拓宽了这一领域。除了普通图之外，超图允许每条边连接顶点集的任意非空子集。迭代幂集构造会产生嵌套的高阶顶点对象，并导出有限的超超图，其顶点和边本身可能在多个层级上呈现集值特征。在本书中，我们考察了包括植生模型在内的广泛图类、超图类和超超图类之间的关系，并讨论了该生态系统内的其他相关结构。本卷是文献[2]的续篇。它也是文献[3]经过大幅修订和扩展的版本；因此，与文献[3]存在某些重叠是可以预期的。

关键词：中智图，植生图，四中智图，模糊图，不确定图

第一章 引言 1.1 图论

图论是数学的一个重要分支，致力于研究由顶点和边构成的网络，特别关注路径、重复出现的结构模式以及基本不变量[1]。几十年来，它已发展成为一个成熟的学科，并在众多领域的广泛应用中提供了支持[4-6]。特别是近年来，它在人工智能领域发挥了重要作用，主要体现在图神经网络及相关学习范式中（例如[7-11]）。

在图论内部，许多图族、结构概念和算法方法都得到了研究。具有代表性的方向包括对树状结构[12,13]、基于路径的结构[14]以及与线性布局相关的模型[15,16]的研究。这些研究方向通常由具体目标驱动。一个反复出现的主题是，将关注范围限制在性质良好的图类上（而非任意图），往往能够设计出速度更快的算法，这凸显了基于图类分析的实际优势[17]。

1.2 超图与超超图

经典图论在描述三个或更多实体同时交互的复杂网络时可能有所不足。超图通过允许每条超边连接任意非空的顶点子集来克服这一局限，从而能够捕捉高阶交互关系[8]。尽管超图表达能力很强，但对于许多现实系统中出现的分层、嵌套以及本质上是层级结构的关系，它可能仍然不足以建模。为弥补这一不足，F. Smarandache 引入了超超图的概念[18,19]。超超图利用基于幂集的迭代构造来编码嵌套的连接模式和多层级关系[18,20,21]，并在近年来受到了广泛关注[22-27]。

表1.1 突出了图、超图和超超图之间的主要区别。在本书中，除非另有说明， n n 表示一个自然数（参见[2]）。有关超超图的更多细节，请根据需要参考文献[2]等资料。

1.3 模糊图、中智图、四部分中智图与普利索图

许多现实系统都涉及不确定性，既包括数值参数方面的不确定性，也包括概念之间关系方面的不确定性。受此启发，几种具有不确定性意识的图形式体系被提出并得到积极研究，包括模糊图、中智图、四部分中智图和普利索图。

模糊图为每个顶点和每条边赋予一个 [ 0 , 1 ]
中的隶属度，表示该对象归属于所建模结构的程度 [29,30]。等价地，模糊图可视为模糊集的图论表示（参见 [31,32]）。在应用中，模糊图已被用于在社交网络、决策和交通系统等场景中建模不精确或不确定的关系 [29,30]。其广泛的适用性带来了持续的研究活动。

在模糊图理论内部，人们提出了许多改进和扩展，要么是为了扩展现有框架，要么是为了使模型更好地符合应用需求。典型的例子包括直觉模糊图 [33]、双极模糊图 [34]、模糊平面图 [35]、不规则双极模糊图 [36]、广义模糊图 [37,38] 以及复犹豫模糊图 [39]。研究这些图类有助于识别共享的结构特征、开发定制化算法，并将理论成果迁移到具体问题场景中。

更广泛地说，人们已经发展出大量图模型来表示不确定性和微妙的概念关系。这些模型包括但不限于模糊图 [29,30]、含糊图 [40-42]、普利索图 [43-46]、概率图 [47-49]、含糊超图 [50]、 N N-图 [51]、 N N-超图 [52]、马尔可夫图 [53]、软图（软集）[54,55]、超软图 [56,57] 以及粗糙图（粗糙集）[58,59]。在这些框架中，本书主要关注中智图和四部分中智图 [60-62]，它们各自有着不同的发展动机。

近年来，中智图 [60,63] 和中智超图 [64,65] 在中智集理论 [66,67] 领域内引起了越来越多的关注。“中智”一词指的是经典逻辑和模糊逻辑的一种扩展，其中真值、不确定性和假值被建模为独立的分量。作为模糊图 [29,30] 的推广，中智图因其灵活性和广泛的应用前景而受到积极研究，这与模糊图的吸引力是相似的。各种相关的中智图和超图类也已被提出，包括双极中智图 [65,68-71]、中智关联图 [72-75]、单值中智符号图 [76]、强中智图 [77]、 m m极中智图 [78-80]、复中智超图 [64] 和双极中智超图 [65]。

普利索图 通过属性值及其对应的隶属度来描述每个顶点和每条边，并引入一个矛盾（或相异度）函数来量化不同属性值之间的不相容性，从而扩展了具有不确定性意识的图框架 [3,81-83]。这可以看作是普利索集概念 [43,84,85] 的图论对应物。这一额外的层次支持在网络上进行依赖于上下文的、异质且可能相互冲突的评估的聚合，从而对经典的模糊图、直觉模糊图和中智图范式进行了细化（例如 [3,86-89]）。为方便起见，表 1.2 以统一的符号总结了几个代表性图扩展中赋予顶点和边的规范信息。

近年来， 不确定图 和 函子图 等概念也被作为统一框架进行研究，以整合的方式处理包括普利索图在内的这些概念。鉴于模糊数学文献的广度和快速增长，密切相关的概念在不同地点、不同时间被独立提出也就不足为奇了。尽管如此，我们认为，统一重叠的概念十分重要，并将切实推动该领域的进一步进展。此外，无论是对于理论研究还是对于应用而言，比较各种具有不确定性意识的图类都是有价值的，以便为特定问题选择最合适的框架。

1.4 我们的贡献

鉴于上述情况，对旨在处理不确定性的图模型进行系统研究是非常相关的。关于四部中性图（quadripartitioned neutrosophic graphs）的研究仍处于早期阶段，并且远不如模糊图、直觉模糊图和中性图的相应发展那样广为人知。在本书中，我们引入并研究了与直觉模糊图和四部中性图相一致的新图类，即一般直觉模糊图（General Intuitionistic Fuzzy Graphs）、一般四部中性图（General Quadripartitioned Neutrosophic Graphs）和四部中性超图（Quadripartitioned Neutrosophic Hypergraphs）。我们还考虑了五部中性图（Pentapartitioned Neutrosophic Graphs），其旨在处理五个不确定性参数。最后，我们考察上述提到的大多数图模型是否可以在更广泛的普利索真图（plithogenic graphs）框架内作为特例来实现。

我们的主要结论总结在下面的定理中。此外，我们分析了相关图类之间的包含关系。而且，在不失一般性的情况下，同样的结果在超图和超超图（superhypergraphs）的设置中也成立。

定理 1.4.1. 在所考虑的图类中，以下陈述成立。

• 空图（empty graph）和零图（null graph）可以分别表示为二值图（2-valued graphs）和三值图（3-valued graphs）。
• 每个边模糊图（edge-fuzzy graph）可以通过对边隶属度值进行阈值化处理转换为二值图。
• 每个模糊图可以通过将顶点和边的隶属度值映射到 { − 1 , 0 , 1 }转换为三值图。
• 每个直觉模糊图可以通过将所有顶点的非隶属函数 v A 设为 0 简化为模糊图。
• 每个中性图可以通过将不确定度分量设为 0 简化为直觉模糊图。
• 每个五部中性图是四部中性图的推广。
• 普利索真图（Plithogenic graphs）推广了模糊图、直觉模糊图、中性图、四部中性图和扩展五部中性图。
• 每个一般普利索真图可以转换为一般四部中性图、一般模糊图、一般直觉模糊图、四值模糊图、模糊图（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）可以转换为普利索真图。

此外，为了阐明这些图类之间的关系，我们作为副产品证明了针对个别类的几个额外定理，并研究了说明性的应用实例。

除了作为 [2] 的续篇和 [3] 的实质修订和扩展版本外，本卷与 [3] 的主要区别在于，它纳入了对超超图（SuperHyperGraphs）的扩展讨论，并用对四部中性图的讨论取代了对 Turiyam 中性图的讨论。我们还尽可能改进了证明和陈述的定义。

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