蔭度

蔭度

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

基本介紹

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

線蔭度

將一個圖G分解成邊不交的生成森林時,生成森林的最少數目稱為G的線蔭度,用
表示。例如,K5至少可分解成3個邊不交的生成森林,如圖1所示。
定理1 設G是一個非平凡圖,令ms表示G的s階子圖的最多邊數,則
利用這個定理,可得完全圖和完全偶圖的線蔭度。
推論1
定理2 對於任意p階圖G,均有

點蔭度

除了上述線蔭度外,還有點蔭度和線性點蔭度等概念。
一個最大度不超過2的森林稱為線性森林。一個圖G的點蔭度和線性點蔭度分別記為a(G)和ρ(G),其定義分別為
{
為無圈圖),
{
為線性森林)。
關於圖的點蔭度,則有下面的結論:
定理3 對任意圖G,記
為圖G的極大最小度,則
由上述定理直接可得下面兩個推論:
推論2 對任意圖G,記
為圖G的最大度,則
推論3 對任意圖G,
為圖G的極大最小度,則
定理4 對於任意p階圖G,均有

相關詞條

熱門詞條

聯絡我們