|
Abstract
|
چکیده
ﻣﯿﻨﯿﻢ ﺗﻌﺪﺍﺩ ﺭﺃﺱﻫﺎﯼ ﮔﺮﺍﻑ G ﮐﻪ ﺣﺬﻑ ﺁﻥﻫﺎ ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ ﮔﺮﺍﻑ ﺭﺍ ﺗﻐﯿﯿﺮ میﺩﻫﺪ، ﻋﺪﺩ ﭘﺎﯾﺎﯾﯽ ﺍﺣﺎﻃﻪﺍﯼ ﮔﺮﺍﻑ G ﻧﺎﻣﯿﺪﻩ ﻭ ﺁﻥ ﺭﺍ ﺑﺎ ﻧﻤﺎد
stγ(G) ﻧﺸﺎﻥ میﺩﻫﯿﻢ. ﻫﻤﭽﻨﯿﻦ ﻣﯿﻨﯿﻤﻢ ﺗﻌﺪﺍﺩ ﺭﺃﺱﻫﺎﯾﯽ کﻪ ﺑﺎ ﺣﺬﻑ ﺁﻥﻫﺎ ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ ﺗﺎﻡ ﮔﺮﺍﻑ G ﺗﻐﯿﯿﺮ میﮐﻨﺪ ﻋﺪﺩ ﭘﺎﯾﺎﯾﯽ ﺍﺣﺎﻃﻪﺍﯼ تام G ﻧﺎﻣﯿﺪﻩ ﻭ ﺁﻥ ﺭﺍ ﺑﺎ ﻧﻤﺎﺩ (G) stγt ﻧﺸﺎﻥ میﺩﻫﯿﻢ.
ﺗﺎﺑﻊ )3V ,2V ,1V ,0(V = f ﺭﺍ یک ﺗﺎﺑﻊ ﺍﺣﺎﻃﻪﮔﺮ ﺭﻭمی ﻣﻀﺎﻋﻒ (ⅮRⅮF) می ﻧﺎﻣﻨﺪ ﻫﺮ ﮔﺎﻩ ﻫﺮ ﺭﺃﺱ ﺑﺎ ﻭﺯﻥ ﺻﻔﺮ ﺣﺪﺍﻗﻞ ﺑﺎ یک ﺭﺃﺱ ﺑﺎ ﻭﺯﻥ
3 ﻭ ﯾﺎ ﺑﺎ ﺩﻭ ﺭﺃﺱ ﺑﺎ ﻭﺯﻥ 2 ﻣﺠﺎﻭﺭ ﺑﺎﺷﺪ. ﻫﻤﭽﻨﯿﻦ ﻫﺮ ﺭﺃﺱ ﺑﺎ ﻭﺯﻥ 1 ﺣﺪﺍﻗﻞ ﺑﺎ یک ﺭﺃﺱ ﺑﺎ ﻭﺯﻥ 2 ﯾﺎ 3 ﻣﺠﺎﻭﺭ ﺑﺎﺷﺪ. ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ ﺭﻭمی ﻣﻀﺎﻋﻒ ﮔﺮﺍﻑ G، γdR(G)، ﻣﯿﻨﯿﻤﻢ ﻭﺯﻥ ﺩﺭ ﺑﯿﻦ ﺗﻤﺎﻡ ﺗﻮﺍﺑﻊ ﺍﺣﺎﻃﻪﮔﺮ ﺭﻭﻣ ﻣﻀﺎﻋﻒ ﺩﺭ G ﺍﺳﺖ. ﯾ ﺗﺎﺑﻊ ﺍﺣﺎﻃﻪﮔﺮ ﺭﻭﻣ ﻣﻀﺎﻋﻒ ﺭﺍ می ﺗﻮﺍﻥ ﺑﻪ ﺻﻮﺭﺕ )3V ,2V ,1V ,0(V = f ﻧﺸﺎﻥ ﺩﺍﺩ ﮐﻪ ﺩﺭ ﺁﻥ ﺑﺮﺍﯼ ﻫﺮ }3 ,2 ,1 ,0{ ∈ i ﺩﺍﺭﯾﻢ i} = (v) (G)|f V ∈ {v = .Vi ﻫﻤﭽﻨﯿﻦ ﺗﺎﺑﻊ ﺍﺣﺎﻃﻪﮔﺮ ﺭﻭﻣ ﻣﻀﺎﻋﻒ )3V ,2V ,1V ,0(V = f ﺭﺍ ﻣﺴﺘﻘﻞ ﺑﯿﺮﻭﻧ ﮔﻮﯾﯿﻢ ﻫﺮﮔﺎﻩ ﻣﺠﻤﻮﻋﮥ 0V ﻣﺴﺘﻘﻞ ﺑﺎﺷﺪ. ﻣﯿﻨﯿﻤﻢ ﻣﻘﺪﺍﺭ ﯾ ﺗﺎﺑﻊ ﺍﺣﺎﻃﻪﮔﺮ ﺭﻭمیﻣﻀﺎﻋﻒ ﻣﺴﺘﻘﻞ ﺑﯿﺮﻭنی ﺭﺍ ﻋﺪﺩ ﺭﻭمی ﻣﻀﺎﻋﻒ ﻣﺴﺘﻘﻞ ﺑﯿﺮﻭنی ﮔﻮﯾﯿﻢ ﻭ ﺑﺎ ﻧﻤﺎﺩ γoidR(G) ﻧﻤﺎﯾﺶ می ﺩﻫﯿﻢ.
زیرﺗﻘﺴﯿﻢ ﯾﺎﻝ e ﺍﺯ ﮔﺮﺍﻑ G ﻋﺒﺎﺭﺕ ﺍﺳﺖ ﺍﺯ ﺍﯾﻨﮑﻪ ﺍﯾﻦ ﯾﺎﻝ ﺭﺍ ﺣﺬﻑ ﮐﺮﺩﻩ ﻭ ﺭﺃﺱ ﺟﺪﯾﺪ x ﺭﺍ ﺑﻪ ﺭﺃﺱﻫﺎﯼ u ﻭ v ﻭﺻﻞ ﮐﻨﯿﻢ. ﻭﺍضخ ﺍﺳﺖ ﮐﻪ ﺯﯾﺮ ﺗﻘﺴﯿﻢ یکﯾﺎﻝ ﺍﺯ یکﮔﺮﺍﻑ، ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ ﺁﻥ ﺭﺍ ﮐﺎﻫﺶ نمی ﺩﻫﺪ. ﻣﯿﻨﯿﻤﻢ ﺗﻌﺪﺍﺩ ﯾﺎﻝﻫﺎﯾﯽ ﺍﺯ ﮔﺮﺍﻑ G ﺭﺍ ﮐﻪ ﺑﺎ ﺯﯾﺮ ﺗﻘﺴﯿﻢ ﺁﻥﻫﺎ ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ ﺭﻭمی ﻣﻀﺎﻋﻒ ﺍﻓﺰﺍﯾﺶ ﯾﺎﺑﺪ، ﻋﺪﺩ ﺯﯾﺮ ﺗﻘﺴﯿﻢ ﺍﺣﺎﻃﻪﺍﯼ ﺭﻭمی ﻣﻀﺎﻋﻒ می ﻧﺎﻣﯿﻢ. ﺗﺎﮐﯿﺪ می ﺷﻮﺩ ﮐﻪ ﻫﺮ ﯾﺎﻝ ﻓﻘﻂ یک ﺑﺎﺭ می ﺗﻮﺍﻧﺪ ﺗﻘﺴﯿﻢ ﺷﻮﺩ. ﻋﺪﺩ ﺯﯾﺮ ﺗﻘﺴﯿﻢ ﺍﺣﺎﻃﻪﺍﯼ ﺭﻭﻣ ﻣﻀﺎﻋﻒ ﺭﺍ ﺑﺎ ﻧﻤﺎﺩ (G) sdγdR ﻧﻤﺎﯾﺶ می ﺩﻫﯿﻢ. ﺩﺭ ﺍﯾﻦ طرح ﻣﺎ ﻋﻼﻭﻩ ﺑﺮ ﻣﻄﺎﻟﻌﮥ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ﺍﺣﺎﻃﻪﺍﯼ، ﭘﺎﯾﺪﺍﺭﯼ ﺭﺃﺳ ﻭ ﯾﺎﻟ ﺍﯾﻦ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ﺍﺣﺎﻃﻪﺍﯼ ﺭﺍ ﻣﻮﺭﺩ ﺑﺮﺭﺳ ﻗﺮﺍﺭ ﻣ ﺩﻫﯿﻢ ﮐﻪ ﺑﻪ ﺑﺮﺧ ﺍﺯ ﺁﻥﻫﺎ ﻣ ﺗﻮﺍﻥ ﺑﻪ ﭘﺎﯾﺪﺍﺭﯼ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ γR(G)، γoiR(G) γtdR(G), R](G),3γ[ ﻭ γoidR(G) ﺍﺷﺎﺭﻩ ﮐﺮﺩ. ﺩﺭ ﺍﺩﺍﻣﻪ ﻣﺎ ﺿﻤﻦ ﺗﻌﯿﯿﻦ ﮐﺮﺍﻥﻫﺎﯼ ﺑﺎﻻ ﻭ ﭘﺎﯾﯿﻦ ﺑﺮﺍﯼ ﺁﻥﻫﺎ، ﺑﺮﺧ ﮐﺮﺍﻥﻫﺎﯼ ﻗﺎﺑﻞ ﻭﺻﻮﻝ ﺭﺍ ﻣﻌﺮﻓ ﮐﺮﺩﻩ ﻭ ﺩﺭ ﺻﻮﺭﺕ ﺍﻣ ﺎﻥ ﺑﻪ ﺩﺳﺘﻪ ﺑﻨﺪﯼ ﺁﻥﻫﺎ ﻣ ﭘﺮﺩﺍﺯﯾﻢ. ﻫﻤﭽﻨﯿﻦ ﭘﺎﯾﺪﺍﺭﯼ ﺯﯾﺮ ﺗﻘﺴﯿﻢ ﯾﺎﻝﻫﺎﯼ ﯾ ﮔﺮﺍﻑ ﺑﺮ ﻋﺪﺩ ﭘﺎﯾﺪﺍﺭﯼ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ﻣﻮﺭﺩ ﺍﺷﺎﺭﻩ ﺑﺮﺭﺳ می ﮔﺮﺩﺩ. ﺩﺭ ﺍﺩﺍﻣﻪ ﺭﻭﺍﺑﻂ ﻧﻮﺭﺩﻫﺎﻭﺱ⁃ﮔﺎﺩﻡ 11 ﻭ NP سختﺭﺍ ﺑﺮﺍﯼ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ﺫﮐﺮ ﺷﺪﻩ، ﻣﻮﺭﺩ ﻣﻄﺎﻟﻌﻪ ﻗﺮﺍﺭ می ﺩﻫﯿﻢ. همچنین ﻫﻤﺎﻥﻃﻮﺭ ﮐﻪ ﮔﻔﺘﻪ ﺷﺪ سعی ﺑﺮ ﺍﯾﻦ ﺍﺳﺖ ﮐﻪ ﻧﺘﺎﯾﺞ ﻣﺬﮐﻮﺭ
|