مدل‌ سازی (عدد احاطه‌ گری)

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 31 شهریور 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 26 مرتبه

پیدا کردن مجموعه احاطه‌گر ماکزیمم جذابیتی ندارد، زیرا خود V به‌عنوان مجموعه رئوس یگ گراف، یک مجموعه احاطه‌گرِ خودش است که بیشترین تعداد عضو را دارد اما مجموعه احاطه‌گر مینیمم مهم است.

تمرین

گراف زیر را در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو   

برای G مجموعه‌های احاطه‌گری پیدا کنید.  

مجموعه b,e,y,u یک زیرمجموعه V است که یک مجموعه احاطه‌گر برای G با چهار عضو محسوب می‌شود.


مجموعه b,v,x,y یک زیرمجموعه V است که یک مجموعه احاطه‌گر برای G با چهار عضو محسوب می‌شود.  

آیا می‌توان یک مجموعه احاطه‌گر با تعداد عضو کمتر برای G پیدا کرد؟ 

با کمی دقت مشاهده می‌کنید که a,v,x یک مجموعه احاطه‌گر سه‌عضوی برای گراف G است.

آیا می‌توان یک مجموعه احاطه‌گری با کمتر از سه‌عضو برای G پیدا کنید؟

فرض کنیم بتوان گراف G را با یک مجموعه دوعضوی از راس‌های V احاطه کرد، این دو راس را p و q بنامیم.


راس p خودش و رئوس مجاور خود را احاطه می‌کند، به‌عبارتی راس p تعداد 1+degp راس را احاطه می‌کند.


راس q خودش و رئوس مجاور خود را احاطه می‌کند، به‌عبارتی راس q تعداد 1+degq راس را احاطه می‌کند.


پس این دو راس حداکثر به تعداد زیر می‌توانند رئوس گراف G را احاطه کنند:

1+degp+1+degq=2+degp+degq


اما ماکزیمم درجه در این گراف ΔG=4 است، پس:

2+degp+degq2+4+4=10


پس حداکثر این دو راس می‌توانند 10 راس از رئوس گراف G را احاطه کنند.


اما گراف G از مرتبه 11 است، در نتیجه لااقل یک راس آن به‌وسیله هیچ راسی از G احاطه نمی‌شود پس با هیچ مجموعه دوعضوی از راس‌های G نمی‌توان این گراف را احاطه کرد.


در نتیجه می‌گوییم، a,v,x یک مجموعه احاطه‌گر با کم‌ترین عضو یا مینیمم برای گراف G است.  

تعریف عدد احاطه‌گری

در بین تمام مجموعه‌های احاطه‌گرِ گراف G مجموعه یا مجموعه‌های احاطه‌گری که کمترین تعداد عضو را دارند، مجموعه احاطه‌گر مینیمم نامیده می‌شوند و تعداد اعضای چنین مجموعه‌ای را عدد احاطه‌گری گراف G می‌نامیم و آن را با γG نمایش می‌دهیم.

تمرین

گراف زیر را با دور C7 در نظر بگیرید: 

عدد احاطه‌گری - پیمان گردلو

عدد احاطه‌گری گراف G را به‌دست آورید.

مجموعه‌های v1,v4,v6v2,v5,v7 مجموعه‌های احاطه‌گر مینیمم می‌باشد.


با کمتر از سه راس، نمی‌توانیم رئوس دیگرِ گراف را احاطه کنیم، بنابراین عدد احاطه‌گری گراف G به‌صورت زیر است:

γG=3

تمرین

یک شبکه کامپیوتری شامل 16 کامپیوتر را در نظر بگیرید که در آن هر کامپیوتر مطابق شکل زیر به چند کامپیوترِ دیگر متصل است.

عدد احاطه‌گری - پیمان گردلو

گراف فوق یک مدل‌سازی از شبکه مورد نظر است که در آن هر راس نشان دهنده یک کامپیوتر و یال بین دو راس نشان دهنده آن است که کامپیوترهای نظیر به آن دو راس مستقیما با هم در ارتباط هستند.

مجموعه‌ای با کمترین تعداد ممکن از کامپیوترها (راس‌ها) انتخاب کنید به‌طوری‌که توسط این مجموعه از کامپیوترها به تمام کامپیوترهای این شبکه وصل باشیم.

p,k,b,e مجموعه انتخاب شده از رئوس برای گراف مورد نظر یک مجموعه احاطه‌گر مینیمم است. 


عدد احاطه‌گری - پیمان گردلو

نکته

1- برای راحتی، به یک مجموعه احاطه‌گرِ مینیمم از گرافِ G، (یک -γمجموعه) می‌گوییم. 

تمرین

گراف زیر را در نظر بگیرید: 

عدد احاطه‌گری - پیمان گردلو

دو مجموعه احاطه‌گر مینیمم، معرفی کنید.

مجموعه‌های دو‌عضوی c,ee,d دو مجموعه احاطه‌گر مینیمم یا اصطلاحا (دو -γمجموعه) هستند.

γG=2

تمرین

یک گراف شش راسی که -γمجموعه) آن با اندازه یک باشد را رسم کنید.  

عدد احاطه‌گری - پیمان گردلو


مجموعه v1 یک مجموعه احاطه‌گری است، پس عدد احاطه‌گری آن γG=1 است. 

یک گراف شش راسی که -γمجموعه) آن با اندازه دو باشد را رسم کنید.  

عدد احاطه‌گری - پیمان گردلو


مجموعه v1,v2 یک مجموعه احاطه‌گری است، پس عدد احاطه‌گری آن γG=2 است. 

نکته

2- عدد احاطه‌گری یک گراف ناهمبند به‌سادگی و با استفاده از یک عمل جمع ساده به‌دست می‌آید، در این بخش احاطه‌گری گراف‌های همبند مد نظر است.


3-
 چون مجموعه راس‌های یک گراف همواره یک مجموعه احاطه‌گر خودش است، برای هر گراف عدد احاطه‌گری تعریف می‌شود.


4- 
گراف تهی، گراف بدون یال است، به‌عبارت دیگر گراف (-0منتظم) از مرتبه n و بدون یال است و با kn نمایش می‌دهیم.

در این‌صورت VG تنها مجموعه احاطه‌گر G است که مینیمم نیز به‌حساب می‌آید، یعنی در گراف از مرتبه n داریم γG=n اگر و فقط اگر G گراف kn باشد.   


5-
 یک گراف G از مرتبه n دارای عدد احاطه‌گری 1 است، اگر و فقط اگر G شامل یک راس v از درجه n-1 باشد.

γG=1degv=n1

در این حالت v یک مجموعه احاطه‌گر مینیمم است.

عدد احاطه‌گری - پیمان گردلو

در گراف فوق داریم:

اگر γG=1 باشد، یک راس با ماکزیمم درجه وجود دارد. 

فرض کنیم گراف فوق n راسی باشد. از ویژگی‌های این گراف آن است که حداقل n-1  یال موجود است و در این وضعیت داریم: 

ΔG=n1

حداکثر تعداد یال‌ها:

n2=nn12

و در این وضعیت داریم: 

ΔG=n1


6- در هر گراف کامل، هر راس می‌تواند یک مجموعه احاطه‌گر گراف باشد زیرا هر راس به راس دیگر متصل است.

بنابراین در هر گراف کامل، مجموعه احاطه‌گر مینیمم فقط یک عضودارد یعنی n-1 عدد احاطه‌گری برابر 1 است.

عدد احاطه‌گری - پیمان گردلو

اما عکس آن همواره درست نیست، زیرا در هر گرافی از مرتبه n که درجه راس آن n-1 باشد، داریم:

γG=1

عدد احاطه‌گری - پیمان گردلو

اگر γG=1 باشد، گراف G حداقل یک راس از درجه n-1 دارد پس می‌تواند از  n-1 یال تا nn-12 یال وقتی گراف کامل است، داشته باشد.   


7-
 اگر G گرافی از مرتبه n باشد، آن‌گاه: 

1γGn

یادآوری

تابع کف و تابع سقف

تابع f:fx=x را تابع جزء‌صحیح یا تابع کف می‌نامیم و به‌صورت زیر تعریف می‌شود:

if   x=nnx<n+1

fx=x یک تابع پله ای است که مقدار آن در هر یک از فواصل n,n+1 مقداری ثابت است.

یکی از مهم‌ترین توابع پله ای، تابع جزء‌صحیح یا براکت (کف) است، که معمولا به‌جای x از نماد x استفاده می‌شود. 


تابع f:fx=x را تابع سقف می‌نامیم و به‌صورت زیر تعریف می‌شود.

if   x=nn<xn+1

fx=x یک تابع پله ای است که مقدار آن در هر یک از فواصل n,n+1 ثابت است.

معمولا در ریاضیات وقتی صحبت از براکت است منظور همان تابع کف است، که x به‌صورت x نمایش داده می‌شود نه تابع سقف x.   

قضیه

اگر G گرافی از مرتبه n و δG1، آن‌گاه: 

δGn2

اثبات

اگر D یک مجموعه احاطه‌گر مینیمال برای گراف G باشد که δG1 آن‌گاه V-D نیز یک مجموعه احاطه‌گر G است.   

اگر D یک مجموعه احاطه‌گر مینیمال برای گراف G باشد، مینیمال نیز هست و داریم:

VDD=γG


n=D+VDn2Dn2γGγGn2Gn2

نکته

1- اگر G بدون راس منفرد باشد به‌عبارتی δG1 آن‌گاه داریم:  

γGn2γG¯n2γG+γG¯n


2- اگر G دارای یک راس منفرد باشد آن‌گاه γG¯=1 و δGn در نتیجه:   

γG+γG¯n+1

اگر G دارای یک راس منفرد باشد آن‌گاه γG=1 و δGn در نتیجه: 

γG+γG¯n+1

قضیه

کران بالا و کران پایین برای عدد احاطه‌گری

اگر G گرافی از مرتبه n باشد که n2 آن‌گاه: 

nΔ+1γGnΔ

اثبات

اگر degv درجه هر راس v از گراف G باشد، واضح است که راس v به تعداد 1+degv از رئوس G را احاطه می‌کند. 

اگر v چنان انتخاب شده باشد که degv= آن‌گاه راس v می‌تواند 1+ راس G را احاطه می‌کند، به‌جز n-1+ راس G که باقی می‌ماند.     

چون هیچ‌کدام از n-1+ راس G به‌وسیله v احاطه نمی‌شوند، پس حداکثر به‌وسیله خودشان احاطه می‌شوند، در نتیجه G حداکثر به‌وسیله:   

n1+Δ+1=nΔ

راس احاطه می‌شود، یعنی داریم:

γGnΔ    ;     1

برای اثبات قسمت دیگر نامساوی، فرض کنیم γG=k باشد، یعنی  مجموعه زیر احاطه‌گر مینیمم G باشد: 

D=v1,v2,v3,,vk

چون راس vi به تعداد 1+degvi راس G را احاطه می‌کند که 1ik و راس‌های D همه n راس G را احاطه می‌کنند، پس داریم:  

i=1k1+degvin

به‌ازای هر i که 1ik باشد، 1+degvi1+Δ در نتیجه:

ni=1k1+degvik1+Δnk1+Δn1+Δk    ;    γG=kn1+ΔγG    ;    2

1      :   γGnΔ2    :   n1+ΔγGn1+ΔγGnΔ

نکته

1- اگر G گرافی k منتظم باشد، آن‌گاه =k بنابراین داریم:   

n1+ΔγGnΔn1+kγGnk


2- با توجه به قضیه 1 این بخش داریم:

n1+kγGn2

تمرین

گراف زیر را در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو

عدد احاطه‌گری گراف فوق را مشخص و ادعای خود را ثابت کنید.

مجموعه دوعضوی a,c یک مجموعه احاطه گر است.


عدد احاطه‌گری این گراف کوچک‌تر یا مساوی 2 است، یعنی:

γG2


اگر γG=1 یعنی یک راس در گراف فوق وجود دارد که به تنهایی تمام رئوس دیگر را احاطه می‌کند. (به تمام رئوس دیگر وصل است)


یعنی راسی با درجه چهار در گراف وجود دارد، که با توجه به گراف فوق چنین راسی وجود ندارد.

1<γG2γG=2


روش دیگر تحلیل این مساله به‌صورت زیر است:

nΔ+1γG53+1γG1.25γG2γG


با توجه به مجموعه احاطه‌گری دو عضوی a,c داریم:

γG=2

تمرین

عدد احاطه‌گری را برای هریک از گراف‌های زیر مشخص کنید:

عدد احاطه‌گری - پیمان گردلو

γGnΔ+1=103+1=3γG3


مجموعه سه‌عضوی a,c,h مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

γG=3

عدد احاطه‌گری - پیمان گردلو

γHnΔ+1=82+1=3γH3


مجموعه سه‌عضوی a,b,c مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

γG=3

عدد احاطه‌گری - پیمان گردلو

γGnΔ+1=83+1=2γG2


مجموعه دو ‌عضوی b,h مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

γG=2

عدد احاطه‌گری - پیمان گردلو

γGnΔ+1=104+1=2γG2


مجموعه دو ‌عضوی j,e مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

γG=2

عدد احاطه‌گری - پیمان گردلو

γGnΔ+1=125+1=2γG2


مجموعه سه ‌عضوی i,f,j مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

γG=3

عدد احاطه‌گری - پیمان گردلو

γGnΔ+1=195+1=4γG4


مجموعه پنج ‌عضوی g,i,k,l,e مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

γG=5

عدد احاطه‌گری - پیمان گردلو

γGnΔ+1=205+1=4γG4


از هر پنج ضلعی حداقل دو راس باید انتخاب کنیم:

γG=4×2=8

تمرین

گراف زیر را در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو

عدد احاطه‌گری گراف شکل فوق را به‌دست آورید و یک مجموعه احاطه‌گر مینیمم برای آن ارائه کنید.

ابتدا حداقل تعداد رئوس برای احاطه کردن رئوس دیگرِ گراف فوق را پیدا می‌کنیم:

nΔ+1=123+1=3


حال با تحلیل زیر γG را می‌یابیم:


برای احاطه کردن راس a لازم است یکی از دو راس a,b در مجموعه احاطه‌گر باشد.


به‌همین ترتیب یکی از رئوس e,f و نیز یکی از رئوس i,j باید در هر مجموعه احاطه‌گر باشند.


اما این سه راس انتخاب شده در هر حالت نمی‌توانند رئوس d,h,l را احاطه کنند، لذا حداقل یک راس دیگر یعنی حداقل 4 راس برای احاطه رئوسِ این گراف لازم است.

γG4


از طرفی b,f,j,h یک مجموعه احاطه‌گر است و γG4 بنابراین:

γG=4

تمرین

گراف زیر را در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو

عدد احاطه‌گری گراف شکل فوق را به‌دست آورید و یک مجموعه احاطه‌گر مینیمم برای آن ارائه کنید.

ابتدا حداقل تعداد رئوس برای احاطه کردن رئوس دیگرِ گراف فوق را پیدا می‌کنیم:

nΔ+1=83+1=2


برای احاطه کردن راس h حداقل یکی از رئوس h یا e باید در مجموعه احاطه‌گر باشند و با بودن هر کدام از آنها در مجموعه احاطه‌گر، رئوس a,b,c,g کماکان احاطه نشده باقی می‌مانند.


برای احاطه کردن رئوس a,b,c,g حداقل دو راس دیگر نیاز است، زیرا هیچ راسی به تنهایی نمی‌تواند هر چهارتای آنها را احاطه کند.


بنابراین حداقل 3 راس باید در هرمجموعه احاطه‌گر از گراف G باشد، یعنی:

γG3


از طرفی چون a,c,e یک مجموعه احاطه‌گر مینیمم است لذا:

γG=3

قضیه

به‌ازای هر عدد صحیح و مثبت n و عدد صحیح k که 1kn گرافی وجود دارد که:

γG=k

اثبات

فرض کنیم که G گرافی از مرتبه n باشد، مجموعه راس‌های آن به‌صورت زیر است:

V=a1,a2,a3,.....,an1,an

اگر G گرافی تهی kn باشد، واضح است که γG=n.  

اگر فقط یال a1a2 را رسم کنیم، n-2 راس باقی مانده که همه منفرد هستند، دارای عدد احاطه‌گری γG=n-2 است.   

اکنون v1=a1,a2 دارای عدد احاطه‌گری 1 است، پس در این گراف کلا عدد احاطه‌گری عبارت است از γG=n-1 .

اگر یال a3a4 را رسم کنیم، γG=n-2 خواهد بود و تا n2 می‌توان ادامه داد. بنابراین تا حالتی که kn2 این عدد مشخص می‌شود.   

اگر 1kn2 همواره می‌توان گرافی همبند پیدا کرد که:

γG=k

قضیه

برای هر دو عدد صحیح n و k که 1kn2 همواره یک گراف همبند از مرتبه n وجود دارد که:  

γG=k

اثبات

قبل از اثبات قضیه، به مثال عددی زیر توجه کنید:

فرض کنید n=9 و 1kn2<5 پس k می‌تواند اعداد زیر را اختیار کند:  

k=1,2,3,4

فرض کنیم k=4 باشد، پس گراف کامل k9-4=k5 را در نظر می‌گیریم که در آن γk5=1.

عدد احاطه‌گری - پیمان گردلو

اکنون چهار راس u4,u3,u2,u1 را به گراف k5 اضافه می‌کنیم و یال‌های v4u4,v3u3,v2u2,v1u1 را رسم می‌کنیم.

گراف همبند G از مرتبه 9 پدید می‌آید که: 

γG=4

عدد احاطه‌گری - پیمان گردلو


حال به اثبات قضیه می‌پردازیم:

گراف کامل Knk شامل n-k راس v1,v2,....,vnk را رسم می‌کنیم، واضح است که:  

γKnk=1

اکنون k راس جدید uk,....,u2,u1 را به آن اضافه می‌کنیم، پس گراف همبند G از مرتبه n پدید می‌آید.  

k یال جدید viui که 1ikn2 را رسم می‌کنیم.

پس از همه راس‌های uk,....,u2,u1 که k راس Knk یالی رسم شده، ممکن است به‌راسی از آن یالی متصل نشده باشد.   

چون kn-k پس کافی است مجموعه احاطه‌گر G را همان k راس از n-k راس Knk انتخاب کنیم، در این‌صورت:  

γG=k

تمرین

گرافی از مرتبه n4 مشخص کنید که در آن γG=2 باشد. 

کافی است دو گراف ستاره‌ای رسم و راس‌های ستاره‌ها را به‌هم وصل کنید اگر هم‌راس‌های دو ستاره را به‌هم وصل نکنیم، یک گراف ناهمبند پدید می‌آید.


عدد احاطه‌گری - پیمان گردلو

برای ارسال نظر وارد سایت شوید