主題
Search

圖的平滑


GraphSmoothing

圖的平滑,也稱為消除平滑或平滑處理,是用單條新邊 e=v_iv_k 來替換在度為 2 的頂點 v_j 處關聯的邊 e^'=v_iv_je^('')=v_jv_k 並移除頂點 v_j 的過程 (Gross and Yellen 2006, p. 293)。

被平滑至不再存在度為 2 的頂點的樹被稱為串聯約簡樹。一般來說,一個簡單無標記圖,其連通性完全基於拓撲等價性(即,直至平滑和細分)來考慮,被稱為拓撲圖

平滑簡單環圖的過程不太明確,因為雖然對環圖 C_n 的單次平滑會得到對於 n>3 的圖 C_(n-1),但如果執行額外的平滑,則圖 C_3 會被平滑為偶極圖 D_2,後者不再是簡單圖,而是多重圖,因為它包含兩個頂點之間的兩條邊。 類似地,平滑 D_2 會得到花束圖 B_1,後者不再是簡單圖,而是偽圖,因為它由透過圖環連線到自身的單個頂點組成。 最後,根據 Gross 和 Yellen (2006, p. 293),不允許平滑掉 B_1 的唯一剩餘頂點。

圖的平滑與圖的細分相反。


另請參閱

圖的細分, 同胚圖, 串聯約簡樹, 拓撲圖

使用 探索

參考文獻

Gross, J. T. 和 Yellen, J. 《圖論及其應用》,第 2 版。 Boca Raton, FL: CRC Press, p. 293, 2006.

請按如下方式引用

Weisstein, Eric W. “圖的平滑”。 來自 Web 資源。 https://mathworld.tw/GraphSmoothing.html

主題分類