跳至內容

英文维基 | 中文维基 | 日文维基 | 草榴社区

用戶:Nnn009nnn/Sandbox 1

維基百科,自由的百科全書
這是維基百科用戶嘗試創建頁面的地方。這不是一個百科全書條目。

en:Expander_graph

組合數論中,擴展圖(英語:Expander graph)是一種具有強連通性質的疏鬆圖,具體而言,看可用邊、頂點或圖譜擴展性(expansion)三種方式定義。擴展圖的構造問題引導了多個數學分支上的研究,它還在計算複雜性理論計算機網絡設計和編碼理論上有諸多應用[1]

定義

[編輯]

簡而言之,擴展圖是一個有限無向多重圖,其中每一組不「太大」的頂點均具有「很大」的邊界(boundary)。不同的具體定義給出了不同種類的擴展圖,下文將討論邊擴展圖、頂點擴展圖和譜擴展圖(spectral expander)三個概念。

非連通圖不是擴展圖,因為每一個連通分量都沒有邊界——分量周圍沒有邊進出,每一個連通圖都是擴展圖,只是他們的擴展性強弱不同。完全圖具有最強的擴展性,但卻很稠密(dense)。一個好的擴展圖應具有強擴展性,並且頂點度數較小。

邊擴展度

[編輯]

包含 個頂點的圖 的邊擴展度 定義為

其中 為子集 的邊界。

注意在此一定義中,最小值取於所有非空、但包含不超過 個頂點的子集[2]

頂點擴展度

[編輯]

圖 G 的頂點擴展度 定義為

此處 是集合 的外邊緣,即所有不在 中但與一個 中的頂點相鄰的頂點[3]。頂點擴展度這一概念的一個變體稱作「唯一鄰點擴展度」(unique neighbor expansion),在這裏 指全部僅有一個相鄰頂點在 中的頂點[4]

腳註

[編輯]

參考來源

[編輯]

教科書和文獻綜述

研究論文

外部連結

[編輯]