論邊元圖 On Edge-MetaGraph

https://www.preprints.org/frontend/manuscript/53fd0e94ffe98b3a4a6455745c537f2b/download_pub

摘要

本文研究與元圖及邊標(biāo)記層級(jí)網(wǎng)絡(luò)相關(guān)的基于圖的高階結(jié)構(gòu)。在回顧元圖和迭代元圖后，我們引入了邊元圖的概念，其中每條邊均由一個(gè)雙端口內(nèi)部圖標(biāo)記，允許通過端口粘合實(shí)現(xiàn)邊替換擴(kuò)展。隨后我們遞歸地定義迭代邊元圖，使得邊可以承載嵌套的邊元圖結(jié)構(gòu)。文中提出了來自生物醫(yī)學(xué)系統(tǒng)、軟件管道和物流的具體示例，以闡明所提框架的表達(dá)能力。

關(guān)鍵詞：邊元圖；元圖；迭代元圖

1. 預(yù)備知識(shí)

本節(jié)建立記號(hào)并總結(jié)后文所需的集合論和組合學(xué)概念。全文中，所有作為頂點(diǎn)域的集合均假定為有限的，我們記 N 0 : = N ∪ { 0 } 。

1.1. 元圖（圖的圖）

圖論研究由頂點(diǎn)和邊組成的數(shù)學(xué)結(jié)構(gòu)，用于建模關(guān)系和連通性 [1,2]。元圖是一種其頂點(diǎn)本身也是圖的圖，其邊表示這些圖之間指定的關(guān)系（參見 [3-6]）。

定義 1.1（元圖（圖的圖）） [7] 固定一個(gè)非空的有限圖（默認(rèn)為無(wú)向、無(wú)環(huán)）全域 G 和一個(gè)非空的二元關(guān)系族

1.2. 迭代元圖（圖的圖……的圖）

迭代元圖是一種其頂點(diǎn)為元圖的圖，它遞歸地將“圖之圖”結(jié)構(gòu)擴(kuò)展至多個(gè)層級(jí) [7–9]。相關(guān)概念，如元結(jié)構(gòu) [10,11]，也是已知的。

2. 結(jié)果

本節(jié)展示本文的結(jié)果。

2.1. 邊元圖（圖標(biāo)記的邊）

邊元圖是一種其邊承載雙端口內(nèi)部圖的圖，支持通過將端口粘合到端點(diǎn)來實(shí)現(xiàn)邊替換擴(kuò)展。

定義 2.1（雙端口圖）。 固定一個(gè)由有限圖（默認(rèn)為無(wú)向、無(wú)環(huán)）組成的非空全域 G 。一個(gè)雙端口圖是一個(gè)三元組

例 2.1（現(xiàn)實(shí)世界示例：具有邊級(jí)內(nèi)部依賴的軟件部署管道）?？紤]一家運(yùn)營(yíng)微服務(wù)平臺(tái)的公司。在粗粒度的操作層面上，我們將部署管道描述為一個(gè)有向多重圖

2.2. 迭代邊元圖

迭代邊元圖通過雙端口邊元圖遞歸地標(biāo)記每條邊，從而創(chuàng)建多層級(jí)的邊替換和擴(kuò)展層次結(jié)構(gòu)。

因此，整個(gè)系統(tǒng)形成了一個(gè)深度為 2 的迭代邊元圖：頂層貨物交接是由深度為 1 的邊元圖標(biāo)記的邊，而在其內(nèi)部，任務(wù)邊由捕獲服務(wù)級(jí)依賴的雙端口基圖標(biāo)記。展開該結(jié)構(gòu)（遞歸地）將為整個(gè)從工廠到客戶的交付管道生成一個(gè)單一的扁平化依賴圖。

原文鏈接：https://www.preprints.org/frontend/manuscript/53fd0e94ffe98b3a4a6455745c537f2b/download_pub