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