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

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

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

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

مجموعه D=b,d,f یک مجموعه احاطه‌گرِ گراف فوق است چون حداقل هر راس از گراف G با یکی از رئوس موجود در D مجاور است.

سوال- آیا با حذف برخی راس‌های آن (مثلا راس b) مجموعه d,f احاطه‌گر خواهد بود؟ 

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

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

در گراف فوق با حذف راس b مجموعه d,f احاطه‌گر نخواهد بود، بنابراین مجموعه احاطه‌گر D=b,d,f را به‌عنوان یک مجموعه احاطه‌گر مینیمال در نظر می‌گیریم.

به‌عنوان نمونه در گراف زیر:

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

a,b,e,d یک مجموعه احاطه‌گر است.

a,f,d یک مجموعه احاطه‌گرِ مینیمال است و با حذف d مجموعه احاطه‌گر نیست.

تمرین

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

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

آیا مجموعه D=c,f,i,g یک مجموعه احاطه‌گر است؟

مجموعه فوق یک مجموعه احاطه‌گر است چون حداقل هر راس از گراف G با یکی از رئوس موجود در D مجاور است.

آیا مجموعه F=c,f,g یک مجموعه احاطه‌گر مینیمال است؟

در مجموعه احاطه‌گر F=c,f,g با حذف هر یک از رئوسش، احاطه‌گر نیست، پس یک احاطه گر مینیمال است.

نکته

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

2- یک مجموعه احاطه‌گر را که با حذف حداقل یکی از راس‌هایش باز هم احاطه‌گر باشد، احاطه‌گر غیرمینیمال می‌نامیم.

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

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

تمرین

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

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

آیا مجموعه D=a,b,c,d,e,f یک مجموعه احاطه‌گر است؟

D یک مجموعه احاطه‌گرِ گراف فوق است چون حداقل هر راس از گراف G با یکی از رئوس موجود در D مجاور است. 

آیا این مجموعه احاطه گر غیر مینیمال است.

از آنجا که با حذف برخی راس‌های آن (مثلا راس a) این مجموعه باز هم احاطه‌گر خواهد بود، لذا مجموعه، احاطه گر غیر مینیمال است.

تمرین

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

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

در گراف شکل فوق مرتبه گراف 9 است و ماکزیمم درجه آن 4 است.

آیا D=a,b,c,e یک مجموعه احاطه‌گر است؟

بله.

آیا D=a,b,c,e یک مجموعه مینیمال است؟

با حذف راس b مجموعه C=a,c,e باز هم یک مجموعه احاطه‌گر است، پس D=a,b,c,e مینیمال نمی‌باشد.  

آیا C=a,c,e یک مجموعه مینیمال است؟

بله. با حذف هر راسی از C مجموعه احاطه‌گر نیست، پس C=a,c,e مجموعه احاطه‌گر مینیمال است. 

آیا یک مجموعه مینیمال دو عضوی می‌توان یافت؟

خیر.


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


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


بنابراین در این گراف هیچ مجموعه احاطه‌گر با حداکثر دو عضو وجود ندارد.


نتیجه این‌که γG≥3 و چون C=3 پس γG=3 است. 

نکته

3- در تعریف مجموعه احاطه‌گر مینیمم، بیان کردیم:

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

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

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

تمرین

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

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

آیا مجموعه v1,v2,v5,v6 یک مجموعه احاطه‌گر است.

بله.

آیا مجموعه v1,v2,v5,v6 یک مجموعه احاطه‌گر مینیمال است.

اگر هر راسی از این مجموعه احاطه‌گر را حذف کنیم، مجموعه باقی‌مانده، یک مجموعه احاطه‌گر نخواهد بود.


یعنی مجموعه v1,v2,v5,v6 یک مجموعه احاطه‌گر مینیمال است.

آیا این مجموعه احاطه‌گر مینیمم نیز هست؟

راس v1 را اختیار کنید این راس، راس‌های v2,v8 را احاطه می‌کند.


اکنون به‌طور دوری در جهت ساعت گرد، اگر راس v4 را به‌عنوان راس دوم مجموعه احاطه‌گر انتخاب کنیم، راس‌های v3,v5 را نیز احاطه می‌کند.


می‌توانیم با گذشتن از دو راس دیگر به‌راس احاطه‌گر سوم برسیم که راس v7 است.


پس v1,v4,v7 یک مجموعه احاطه‌گر مینیمم سه‌عضوی این گراف است. 

آیا این گراف مجموعه احاطه‌گری با دو عضو نیز دارد؟ چرا؟

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

تمرین

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

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

مجموعه‌های احاطه‌گر مینیمال و مینیمم گراف زیر را پیدا کنید؟

مجموعه‌های A=a,b,c,d,eB=i,j,h,g,f هر دو مجموعه‌های احاطه‌گر G هستند. 


در عین حال هر دو، مجموعه‌های احاطه‌گر مینیمال G محسوب می‌شوند، اما مینیمم نیستند زیرا مجموعه احاطه‌گر C=a,c,g را می‌توان به‌عنوان کم‌ترین تعداد عضو معرفی کرد.

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

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


چون سه منتظم است، پس هر راسِ یک مجموعه احاطه‌گر، حداکثر می‌تواند خود و سه راس دیگر را احاطه کند یعنی 1+3=4 راس.


با توجه به این‌که مجموعه احاطه‌گری k عضو دارد و تعداد راس‌های گراف 10 عضو است، بنابراین بایستی داشته باشیم:

4k≥10⇒k≥104


که کم‌ترین مقدار آن k=3 است.

پس امکان دارد این گراف دارای یک مجموعه احاطه‌گر مینیمم با عدد احاطه‌گری k=3 باشد.


با انتخاب سه راس D=a,i,h یک مجموعه احاطه‌گر مینیمال داریم.


چون γG≥3 پس γG=3 و D یک مجموعه احاطه‌گر مینیمم گراف فوق است.  

قضیه

فرض کنیم G یک گراف با راس غیرمنفرد باشد به‌طوری‌که γG≥1. 

اگر D یک مجموعه احاطه‌گر مینیمال G باشد، آن‌گاه D'=V−D به‌عنوان مکمل D نیز یک مجموعه احاطه‌گر G است که V مجموعه راس‌های G می‌باشد.

اثبات

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

در گراف G که V=a,b,c,u,v راس‌های این گراف می‌باشند، مشاهده می‌کنید که D=u,v یک مجموعه احاطه‌گر مینیمم و در نتیجه مینیمال است.

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

اکنون مجموعه D'=V−D=a,b,c به‌عنوان مکمل D نیز یک مجموعه احاطه‌گر G است.


اکنون به اثبات قضیه می‌پردازیم:

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

می‌خواهیم ثابت کنیم V-D یک مجموعه احاطه‌گر G است.

آن را به برهان خلف ثابت می‌کنیم:

فرض کنیم V-D مجموعه احاطه‌گر مینیمال از گراف G نباشد، چون هر مجموعه احاطه‌گر عضوهای خودش را احاطه می‌کند، پس اگر V-D احاطه‌گر نباشد، راسی مانند v از D وجود دارد که توسط V-D احاطه نمی‌شود، بنابراین v مجاور هیچ راسی از V-D نمی‌باشد.   

اما D یک مجموعه احاطه‌گر G است پس هر راس V-D مجاور راسی از D به‌جز v است، یعنی هر راس V-D توسط راسی از D-v احاطه می‌شود.    

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

نکته

1- اگر G گرافی با راس غیرمنفرد و V مجموعه راس‌های آن باشد، اگر D مجموعه احاطه‌گر مینیمم G باشد،آن‌گاه D'=V−D نیز یک مجموعه احاطه‌گر G است.  

2- هر گراف همبند G از مرتبه n≥2 یک مجموعه احاطه‌گر دارد که مکمل آن V−D نیز یک مجموعه احاطه‌گر G است.  

قضیه

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

اثبات

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

تمرین

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

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

آیا D=v1,v3,v5 مجموعه احاطه‌گر مینیمال است؟

مجموعه فوق یک مجموعه احاطه‌گر مینیمال است و هیچ دو راس D مجاور نیست.

آیا D=v1,v3,v5 مجموعه احاطه‌گر مینیمم است؟

مجموعه فوق یک مجموعه احاطه‌گر مینیمم نیست زیرا:

γG=2


v1,v4 احاطه‌گر مینیمم است.


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

نکته

عکس این قضیه درحالت کلی برقرار نمی‌باشد.

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

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

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