蔭度

蔭度((arboricity)是圖論中的一個不變數，設H₁，H₂，…，H_m是G的支撐子圖，且都是森，在G的所有森分解中，含森最少的森分解中森的數目，稱為G的蔭度。若H_i是線性森，即其每一連通片是一條路，則在G的所有線性森分解中，含森最少的分解中的線性森的數目，稱為G的線性蔭度，圖G的點-蔭度定義為符合如下條件的最小整數k：G的節點可分成k個不交的子集，每一個節點子集的導出子圖都是森，圖G的線性點-蔭度定義為符合下列條件的最小整數k：G的節點集可分成k個不交的子集，每一個節點子集的導出子圖是一個線性森。

基本介紹

• 中文名：蔭度
• 外文名：arboricity
• 所屬學科：數學
• 所屬問題：組合學(圖與超圖)
• 簡介：圖論中的一個不變數

線蔭度

將一個圖G分解成邊不交的生成森林時，生成森林的最少數目稱為G的線蔭度，用 表示。例如，K₅至少可分解成3個邊不交的生成森林，如圖1所示。

定理1 設G是一個非平凡圖，令m_s表示G的s階子圖的最多邊數，則

利用這個定理，可得完全圖和完全偶圖的線蔭度。

推論1 。

定理2 對於任意p階圖G，均有

點蔭度

除了上述線蔭度外，還有點蔭度和線性點蔭度等概念。

一個最大度不超過2的森林稱為線性森林。一個圖G的點蔭度和線性點蔭度分別記為a(G)和ρ(G)，其定義分別為

{為無圈圖)，

{為線性森林)。

關於圖的點蔭度，則有下面的結論：

定理3 對任意圖G，記為圖G的極大最小度，則

由上述定理直接可得下面兩個推論：

推論2 對任意圖G，記為圖G的最大度，則

推論3 對任意圖G，為圖G的極大最小度，則

定理4 對於任意p階圖G，均有