論多線圖、多線超圖與多線超超圖

On MultiLine Graphs, MultiLineHyperGraphs, and MultiLine Super-HyperGraphs

https://www.preprints.org/manuscript/202603.0791

摘要

有限超圖通過允許超邊連接頂點(diǎn)的任何非空子集，推廣了普通圖，從而表示真正的多路交互。擴(kuò)展這一思想，有限超超圖是通過迭代冪集構(gòu)造獲得的，使得在某一層形成的集合值對象可以在下一層充當(dāng)頂點(diǎn)或邊端點(diǎn)，為層級和多層關(guān)系結(jié)構(gòu)提供了一個(gè)自然框架。相比之下，線圖將圖的每條邊轉(zhuǎn)換成一個(gè)頂點(diǎn)，其中兩個(gè)這樣的新頂點(diǎn)相鄰恰好當(dāng)對應(yīng)的原始邊共享一個(gè)端點(diǎn)時(shí)。在本文中，我們引入了多線圖的概念，其中多條邊可以被分配給一個(gè)頂點(diǎn)，然后發(fā)展其高階擴(kuò)展，即多線超圖和多線超超圖。我們進(jìn)一步研究了它們的基本性質(zhì)和結(jié)構(gòu)特征。

關(guān)鍵詞：超圖；超超圖；線圖，多線圖

1. 預(yù)備知識

本節(jié)建立全文所使用的記號，并回顧后續(xù)章節(jié)所需的基本集合論和組合學(xué)概念。

1.1 超超圖

我們首先從超超圖背后的集合論運(yùn)算開始，然后回顧相關(guān)的圖論定義。

V 的元素被稱為 n -超頂點(diǎn)， E 的元素被稱為超超邊；等價(jià)地，每條超超邊是超頂點(diǎn)集 V 的一個(gè)非空子集。

1.2. 線超超圖

線超圖將每條超邊替換為一個(gè)頂點(diǎn)；每個(gè)原始頂點(diǎn)生成一個(gè)由所有關(guān)聯(lián)超邊組成的超邊 [9–14]。線超超圖將超超邊變?yōu)轫旤c(diǎn)；每個(gè)超頂點(diǎn)誘導(dǎo)一個(gè)由所有遞歸關(guān)聯(lián)的超超邊組成的超邊 [15,16]。

定義 6（線超圖）。（參見 [9,14]）設(shè) H = ( V , E )
為一個(gè)（有限）超圖，即，

2. 主要結(jié)果

在本節(jié)中，我們展示主要結(jié)果。

2.1. 多線圖

在普通圖中，鄰接關(guān)系僅在頂點(diǎn)層面記錄。相比之下，在多線圖中，每個(gè)頂點(diǎn)配備了幾條可區(qū)分的局部線（local lines），一條邊由配對兩條這樣的局部線形成。這提供了一個(gè)以頂點(diǎn)為中心的框架，在其中可以明確表示一個(gè)頂點(diǎn)可能承載多條關(guān)聯(lián)線的事實(shí)。

注記 2. 多線圖不同于經(jīng)典線圖。這里“多線”一詞意味著每個(gè)頂點(diǎn)承載幾條可區(qū)分的局部線。在這個(gè)意義上，該結(jié)構(gòu)更接近于具有明確逐頂點(diǎn)線重?cái)?shù)的半邊模型。

2.2. 多線超圖

多線超圖通過允許一條多線邊同時(shí)連接兩條以上的局部線，擴(kuò)展了多線圖的框架。因此，每個(gè)頂點(diǎn)可能承載若干條可區(qū)分的局部線，而一條多線超邊是通過選擇附著在兩兩互異頂點(diǎn)上的此類局部線的一個(gè)有限集而形成的。

2.3. 多線超超圖

多線超超圖將之前的構(gòu)造從普通頂點(diǎn)擴(kuò)展到更高層級的超頂點(diǎn)。在此設(shè)定下，每個(gè) n-超頂點(diǎn)承載幾條可區(qū)分的局部線，且每條多線超超邊是附著在兩兩互異的 n-超頂點(diǎn)上的局部線的有限集。

原文鏈接：https://www.preprints.org/manuscript/202603.0791