|
چکیده
|
فرض کنید G یک گراف بوده و f=(V0, V1, V2) یک تابع تعریف شده بر G باشد. گوییم تابع f یک تابع احاطه گر رومی است هرگاه هر رأس با وزن صفر حداقل با یک رأس با وزن دو مجاور باشد. راس v از گراف G را یک رأس بی دفاع نسبت به f گوییم هرگاه مجموع وزن های راس v با همسایگی هایش برابر صفر باشد. تابع f=(V0, V1, V2) را یک تابع احاطه گر رومی ضعیف گوییم هرگاه هر رأس v با وزن صفر دارای یک همسایگی مانند u با وزن حداقل یک بوده و تابع g با ضابطه g(v)=f(v)+1, g(u)=f(u)-1 و برای هر x از V(G)-{u, v} داشته باشیم: f(x)=g(x) بطوریکه هیچ رأس بی دفاع نسبت به g در G موجود نباشد. ﻋﺪﺩ ﺍﺣﺎﻃﻪ ﺍﯼ ﺭﻭمی ﺿﻌﯿف γr(G) ﮐﻤﺘﺮﯾﻦ ﻭﺯﻥ ﺗﻮﺍﺑﻊ ﺍﺣﺎﻃﻪ ﮔﺮ ﺭﻭمیﻣﻀﺎﻋﻒ ﺿﻌﯿﻒ ﺍﺳﺖ. ما در این طرح تلاش خواهیم کرد به برخی سوالات زیر پاسخ دهیم.
1- ﺁﯾﺎ ﮐﺮﺍﻥ ﻫﺎﯼ ﺑﺎﻻ ﻭ ﭘﺎﯾﯿﻦ ﺑﺮﺍﯼ ﻋﺪﺩ ﺍﺣﺎﻃﻪ ﺍﯼ ﺭﻭمی ﻣﻀﺎﻋﻒ ﺿﻌﯿﻒ ﺑﺮ ﺣﺴﺐ ﺑﯿﺸﺘﺮﯾﻦ ﺩﺭﺟﻪ ﻭ ﻣﺮﺗﺒﻪ ﮔﺮﺍﻑ ﻣﻮﺟﻮﺩ ﺍﺳﺖ؟
2-چه رﻭﺍﺑطی ﺑﯿﻦ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ﻋﺪﺩ ﺍﺣﺎﻃﻪ ﺍﯼ ﺭﻭمی ﺿﻌﯿﻒ ﻭﺳﺎﯾﺮﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼﺍﺣﺎﻃﻪ ﺍﯼ ﻭﺟﻮﺩ ﺩﺍﺭﺩ؟ ﺁﯾﺎ ﺍﯾﻦ ﺭﻭﺍﺑﻂ ﻗﺎﺑﻞ ﻭﺻﻮﻝﻫﺴﺘﻨﺪ؟
3-آیا مسئله احاطه ای رومی ضعیف ان پی سخت است؟
4-ﺁﯾﺎ ﻧﺎﻣﺴﺎﻭﯼ ﻫﺎﯼ ﻧﻮﺭﺩﻫﺎﻭﺱ⁃ﮔﺎﺩﻭﻡ ﺑﺮﺍﯼ ﻋﺪﺩ ﺍﺣﺎﻃﻪ ﺍﯼ ﺭﻭمی ﺿﻌﯿﻒ ﻣﻮﺟﻮﺩ ﺍﺳﺖ؟ ﻫﻤﭽﻨﯿﻦ ﺑﺮﺍﯼ ﮐﺪﺍﻡ ﮔﺮﺍﻑ ﻫﺎ ﺍﯾﻦ ﻧﺎﻣﺴﺎﻭﯼ ﻫا قابل وصول هستند؟
ﺁﯾﺎ ﺍﺭﺗﺒﺎﻃی ﺑﯿﻦ ﻋﺪﺩ ﺍﺣﺎﻃﻪ ﺍﯼ ﺭﻭمی ﺿﻌﯿﻒ ﻭ ﻋﺪﺩ ﺍﺣﺎﻃﻪ ﺍﯼ ﺭﻭمی ﻭﺟﻮﺩ ﺩﺍﺭﺩ؟
|