مدل‌ سازی (گراف‌ های دو‌ بخشی و احاطه‌ گری)

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

یادآوری

گراف دو بخشی

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

V(G)W(G)=

کل رئوسV(G)W(G)=

به‌عنوان نمونه:

اگر داشته باشیم:

V(G)={V1,...,V5}W(G)={W1,...,W4}

گراف زیر دوبخشی است: 

گراف‌های دو‌بخشی و احاطه‌گری - پیمان گردلو

گرافی دوبخشی است، اگر و تنها اگر شامل هیچ دور با طول فرد نباشد.


گراف کامل دو بخشی

در دسته‌ای دیگر از گراف‌های ساده G=V,E مجموعه راس زیر را:

VG=u1,...um,w1,...wn

می‌توان به دو زیر مجموعه زیر تجزیه کرد:

uG=u1,...,umwG=w1,...wn

هر راس داخلی یکی از زیر مجموعه‌ها، دقیقا به‌وسیله یک یال به هرراس داخل زیر مجموعه دیگر متصل شده باشد، اما بر هر راس خود آن زیرمجموعه متصل نباشد، به‌چنین گراف‌هایی گراف کامل دوبخشی گویند.

یک گراف کامل دوبخشی با m,n راس که به‌صورت km,n نمایش داده می‌شود. 

گراف زیر دوبخشی است: 

گراف‌های دو‌بخشی و احاطه‌گری - پیمان گردلو

تعریف گراف دوبخشی و احاطه‌گری

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

فرض کنیم G گراف دوبخشی کامل kp,q باشد به‌طوری‌که 1qp.

اگر q=1 باشد،آن‌گاه γkp,q=1:

گراف‌های دو‌بخشی و احاطه‌گری - پیمان گردلو

اگر  n2 باشد، آن‌گاه γkp,q=2:

گراف‌های دو‌بخشی و احاطه‌گری - پیمان گردلو

برای انتخاب مجموعه احاطه‌گر فقط کافی است یک راس از مجموعه راس‌های اولی (راس‌های خانواده q) و یک راس از مجموعه راس‌های دومی (راس‌های خانواده p) را انتخاب کنیم.

این مجموعه احاطه‌گر، هم مینیموم و هم مینیمالِ دو عضوی است.

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