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

آخرین ویرایش: 31 شهریور 1400
دسته‌بندی: گراف
امتیاز:
نظر کاربران: برای نظر دادن اولین باش!

مقدمه‌ای بر مجموعه‌های احاطه‌گر

فرض کنیم G گرافی با مجموعه راس‌ها و مجموعه یال‌های مختلف باشد.

راس v از گراف G را مجاور راس a از گراف G می‌نامیم، هرگاه یالی از v به a وجود داشته باشد.

وقتی راس v مجاور راس یا راس‌هایی از G است یعنی راس v خودش و راس‌های مجاورش را احاطه می‌کند، بنابراین می‌گوییم راس v از گراف G خودش و رئوس a و b و c از G احاطه می‌شود.  

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

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

در شکل فوق، گراف G با مجموعه راس‌های زیر مفروض است:

V=a,b,c,d,e,u,v

راس‌های c,b,a بنابر آنچه که بیان کردیم، هر کدام مجاور راس v یا منطبق بر v هستند، پس راس v خودش و سه راس c,b,a را احاطه کرده است. 

به‌همین ترتیب، راس u سه راس e,d,c و خود u را احاطه کرده است. 

اگر D=u,v را در نظر بگیریم، هر راس از گراف G یا در D باشد و یا حداقل هر راس از گراف G با یکی از رئوس موجود در D مجاور باشد.    

تعریف مجموعه‌های احاطه‌گر

فرض کنیم V مجموعه راس‌های گراف G و D زیرمجموعه‌ای از V باشد.

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

تمرین

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

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

آیا مجموعه D=v1,v3,v5,v7 با دور C7 یک مجموعه احاطه‌گر می‌باشد؟

بله.


v1 رئوس v7,v2 را احاطه کرده است.

 
v3 رئوس v4,v2 را احاطه کرده است.


 v5 رئوس v4,v6 را احاطه کرده است.


 v7 رئوس v1,v6 را احاطه کرده است.


توجه کنید که با چهار راس v1,v3,v5,v7 همه رئوس گراف را احاطه کرده‌ایم.

تمرین

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

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

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

راس‌هایی را انتخاب می‌کنیم که راس‌هایی در مجاور آن باشند.


معمولا راسی را انتخاب می‌کنیم که راس‌های بیشتری مجاور آن باشند.


مثلا راس b می‌تواند خودش و راس‌های u,c,a را احاطه کند.


راس z می‌تواند خودش و راس‌های y,v,d را احاطه کند.


اما مشاهده می‌کنیم که راس x از G توسط هیچ‌کدام از این دو راس احاطه نمی‌شود. پس خود راس x اید خودش را احاطه کند.


درنتیجه D=b,z,x یک مجموعه احاطه‌گر گراف G است.


به‌همین ترتیب می‌توانیم مجموعه‌های احاطه‌گر دیگری مانند d,u,y در نظر بگیریم.


نکته مهم در این تمرین آن است‌که: 


این گراف از مرتبه 9 است (تعداد رئوس گراف) و بزرگ‌ترین درجه در آن △=3 است.


اگر گراف G یک مجموعه احاطه‌گر دو عضوی داشته باشد، هر عضو از این مجموعه دو عضویِ احاطه‌گر، با خودش و سه راس دیگر، مجاور است پس حداکثر می‌تواند 4×2=8 راس G را احاطه کند.


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

تمرین

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

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

مشخص کنید کدام‌یک از مجموعه‌های زیر برای گراف فوق احاطه‌گر هست و کدام نیست؟

A=a,b,c,d,e

احاطه‌گر هست.

B=f,g,h,i,j

احاطه‌گر هست.

C=a,b,j,h,g

احاطه‌گر نیست.

D=a,i,h

احاطه‌گر هست.

E=f,g,h,e,d

احاطه‌گر هست.

F=f,g,h,e

احاطه‌گر هست.

H=g,h,e

احاطه‌گر هست.

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