|
چکیده
|
چکیده
ﻓﺮﺽ ﮐﻨﯿﺪ i ﻭ j ﺩﻭ ﻋﺪﺩ ﺻﺤﯿﺢ ﻣﺜﺒﺖ ﺑﺎﺷﻨﺪ ﻭ j ≤ i ≤ 0. ﺯﯾﺮ ﻣﺠﻤﻮﻋﮥ S ﺍﺯ (G) V ﺭﺍ ﯾ j] [i, ⁃ﻣﺠﻤﻮﻋﻪ ﮔﻮﯾﯿﻢ ﻫﺮﮔﺎﻩ ﺑﺮﺍﯼ ﻫﺮ ﺭﺃﺱ v
ﺍﺯ S \ (G) V، ﺩﺍﺷﺘﻪ ﺑﺎﺷﯿﻢ: j ≤ S| ∩ (v) |N ≤ .i ﺑﻪ ﻋﺒﺎﺭﺕ دیگر ﻫﺮ ﺭﺃﺱ S \ (G) V ∈ v ﺑﺎ ﺣﺪﺍﻗﻞ i ﻭ ﺣﺪﺍﮐﺜﺮ j ﺭﺃﺱ ﺍﺯ S ﻣﺠﺎﻭﺭ ﺑﺎﺷﺪ. ﮐﻤﺘﺮﯾﻦ ﺍﻧﺪﺍﺯﻩ j] ⁃[i, ﻣﺠﻤﻮﻋﻪﻫﺎﯼ ﺍﺣﺎﻃﻪﮔﺮ G ﺭﺍ ﻋﺪﺩ j] [i, ⁃ﺍﺣﺎﻃﻪﺍﯼ ﮔﺮﺍﻑ G ﻧﺎﻣﯿﺪﻩ ﻭ ﺑﺎ ﻧﻤﺎﺩ γ[i,j](G) ﻧﻤﺎﯾﺶ میﺩﻫﻨﺪ. ﺯﯾﺮ ﻣﺠﻤﻮﻋﮥ
S′ ﺍﺯ (G) V ﺭﺍ یک j] ⁃[i, ﻣﺠﻤﻮﻋﮥ ﺍﺣﺎﻃﻪﮔﺮ ﺗﺎﻡ ﮔﻮﯾﯿﻢ ﻫﺮﮔﺎﻩ ﺑﺮﺍﯼ ﻫﺮ ﺭﺃﺱ v ﺍﺯ (G) V، j ≤ S′| ∩ (v) |N ≤ .i ﮐﻤﺘﺮﯾﻦ ﺍﻧﺪﺍﺯﻩ j] ⁃[i, ﻣﺠﻤﻮﻋﻪﻫﺎﯼ ﺍﺣﺎﻃﻪﮔﺮ ﺗﺎﻡ G ﺭﺍ ﻋﺪﺩ j] [i, ⁃ﺍﺣﺎﻃﻪﺍﯼ ﺗﺎﻡ ﮔﺮﺍﻑ G ﻧﺎﻣﯿﺪﻩ ﻭ ﺑﺎ ﻧﻤﺎﺩ γt[i,j](G) ﻧﻤﺎﯾﺶ می ﺩﻫﻨﺪ. ﻓﺮﺽ ﮐﻨﯿﺪ 1 ≥ k ﯾ ﻋﺪﺩ ﺻﺤﯿﺢ ﺑﻮﺩﻩ ﻭ }1 + k , . . . ,2 ,1 ,0{ −→ (G) V : f یک ﺗﺎﺑﻊ ﺑﺎﺷﺪ. ﺑﺮﺍﯼ ﺭﺃﺱ v ﺍﺯ (G) V ﻣﺠﻤﻮﻋﮥ ﻫﻤﺴﺎیگیﻫﺎﯼ ﻓﻌﺎﻝ ﺁﻥ ﮐﻪ ﺑﺎ ﻧﻤﺎﺩ AN(v) ﻧﻤﺎﯾﺶ ﺩﺍﺩﻩ می ﺷﻮﺩ، ﻋﺒﺎﺭﺕ ﺍﺳﺖ ﺍﺯ ﻣﺠﻤﻮﻋﮥ ﺭﺋﻮﺱ (v) N ∈ w ﮐﻪ 1 ≥ (w) .f ﺗﺎﺑﻊ }1+ k , · · · ,2 ,1 ,0{ −→ (G) V : f ﺭﺍ یک ﺗﺎﺑﻊ ⁃k ﺍﺣﺎﻃﻪﮔﺮ ﺭﻭمی RⅮF) (k− ﮔﻮﯾﯿﻢ ﻫﺮﮔﺎﻩ ﺑﻪ ﺍﺯﺍﯼ ﻫﺮ ﺭﺃﺱ v ﺍﺯ (G) V
ﮐﻪ k < (v) f ﺩﺍﺷﺘﻪ ﺑﺎﺷﯿﻢ: k + |AN(v)| ≥ (NG[v]) .f ﻣﻘﺪﺍﺭ (v) (G)f Σv∈V = ) ω(f ﺭﺍ ﻭﺯﻥ ﺗﺎﺑﻊ f می ﻧﺎﻣﯿﻢ. ﺗﻮﺟﻪ ﺷﻮﺩ ﮐﻪ ﻭﺯﻥ یک k−RⅮF ﺭﺍ میﺗﻮﺍﻥ ﺍﺯ ﺗﺴﺎﻭﯼ |1)|Vk+1 + (k + . . . + |2|V2 + |1|V ﻣﺤﺎﺳﺒﻪ ﻧﻤﻮﺩ. ﻣﯿﻨﯿﻤﻢ ﻭﺯﻥ یک ﺗﺎﺑﻊ k−RⅮF ﺭﺍ ﻋﺪﺩ −k ﺍﺣﺎﻃﻪﺍﯼ ﺭﻭمی ﮔﺮﺍﻑ G ﻧﺎﻣﯿﺪﻩ ﻭ ﺑﺎ ﻧﻤﺎﺩ γ[kR](G) ﻧﻤﺎﯾﺶ میﺩﻫﻨﺪ ]1.[ ﺗﺎﺑﻊ f ﺭﺍ یک ﺗﺎﺑﻊ ﺍﺣﺎﻃﻪﮔﺮ ﺭﻭمی ﺩﺭ G ﮔﻮﯾﯿﻢ ﻫﺮﮔﺎﻩ 1 = .k ﺗﺎﺑﻊ }1 + k , . . . ,2 ,1 ,0{ −→ (G) V : f ﺭﺍ یک ⁃[k][i,j] ﺗﺎﺑﻊ ﺍﺣﺎﻃﻪﮔﺮ ﺭﻭمی ﮔﻮﯾﯿﻢ ﻫﺮﮔﺎﻩ ﺑﻪ ﺍﺯﺍﯼ ﻫﺮ ﺭﺃﺱ (G) V ∈ v ﮐﻪ k < (v) f، ﺩﺍﺷﺘﻪ ﺑﺎﺷﯿﻢ: j + k + (v)| |AN ≤ (NG[v]) f ≤ i + k + (v)| .|AN ﻣﯿﻨﯿﻤﻢ ﻭﺯﻥ یک ⁃[k][i,j] ﺗﺎﺑﻊ ﺍﺣﺎﻃﻪﮔﺮ ﺭﻭمی ﺭﺍ ﻋﺪﺩ ⁃[k][i,j] ﺍﺣﺎﻃﻪﺍﯼ ﺭﻭمی ﮔﺮﺍﻑ G ﻧﺎﻣﯿﺪﻩ ﻭ ﺁﻥ ﺭﺍ ﺑﺎ ﻧﻤﺎﺩ (G) γ[i,j] میﺩﻫﯿﻢ. ﺗﺎﺑﻊ }2 ,1 ,0{ −→ (G) V : f ﺭﺍ یک ﺗﺎﺑﻊ }2⁃{ ﺍﺣﺎﻃﻪ ﮔﺮ ﮔﻮﯾﯿﻢ ﻫﺮﮔﺎﻩ ﺑﻪ ﺍﺯﺍﯼ ﻫﺮ ﺭﺃﺱ v ﺍﺯ (G) V , 2≥ f(x) ﻭﺯﻥ ﺗﺎﺑﻊ }2⁃{ ﺍﺣﺎﻃﻪﮔﺮ ), w(f , ﺑﻪ ﺻﻮﺭﺕ (u) f (G) u∈V ﺗﻌﺮﯾﻒ میﺷﻮﺩ. ﻋﺪﺩ }2⁃{ ﺍﺣﺎﻃﻪﺍﯼ ﺑﺮﺍﺑﺮ ﮐﻤﺘﺮﯾﻦ ﻭﺯﻥ ﺗﻮﺍﺑﻊ }2⁃{ ﺍﺣﺎﻃﻪﮔﺮ ﺗﻌﺮﯾﻒ ﺷﺪﻩ ﻭ ﺑﺎ ﻧﻤﺎﺩ }(G)2γ{ ﻧﻤﺎﯾﺶ ﺩﺍﺩﻩ میﺷﻮﺩ تاﺑﻊ }2 ,1 ,0{ −→ (G) V : f ﺭﺍ یک }[i,j]2⁃{ ﺗﺎﺑﻊ ﺍﺣﺎﻃﻪﮔﺮ ﮔﻮﯾﯿﻢ ﻫﺮﮔﺎﻩ ﺑﻪ ﺍﺯﺍﯼ ﻫﺮ ﺭﺃﺱ (G) V ∈ v ﮐﻪ 2 < (v) f، ﺩﺍﺷﺘﻪ ﺑﺎﺷﯿﻢ: +j1 ≤ (NG[v]) f ≤ +
|