گراف دوبخشی

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

مقدمه‌ای بر گراف دوبخشی

فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می‌باشند، تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده‌اند حال این سوال مطرح می‌شود که آیا می‌توان به هر متقاضی شغلی متناسب آن اختصاص داد؟

برای حل چنین مساله‌ای که به مساله تخصیص موسوم است با استفاده از گراف می‌توان وضعیت‌های خاصی را پیاده‌سازی نمود، بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه VG و شغل‌های بدون متصدی را در مجموعه WG قرار می‌دهیم.

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

به‌عبارت دیگر، گراف به‌وجود آمده دارای یال‌ها viwj است که هر متقاضی vi از مجموعه VG را به‌شغل‌های متناسب wj از مجموعه WG متصل می‌کند.        

به‌عبارت دقیق‌تر هیچ دو راس متعلق به مجموع VG (متقاضیان) یا هیچ دو راس متعلق به مجموعه WG (مشاغل) توسط هیچ یالی به هم وصل نیستند، چنین گرافی را گراف دوبخشی یا دوپارچه می‌گویند.   

تعریف گراف دوبخشی

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

V(G)W(G)=

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

تمرین

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

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

یک گراف دوبخشی رسم کنید.

گراف دوبخشی - پیمان گردلو

 

دریافت مثال

قضایا گراف دوبخشی

قضیه

اگر گراف دوبخشی (r - منتظم) دارای دوبخش VG و WG باشد، آن‌گاه تعداد عناصر WG و VG باهم برابرند، یعنی:     

V(G)=W(G)

اثبات

فرض می‌کنیم VG دارای m راس و WG دارای n راس از راس‌های گراف دوبخشی (r - منتظم) باشند، ثابت می‌کنیم m=n است:      

از هر راس در مجموعه VG به‌تعداد r یال خارج می‌شود. (چون طبق فرض گراف مورد نظر (r - منتظم) است)  

پس تعداد کل یال‌ها برابر q=rm است.

چون جمعا m+n راس داریم، لذا مطابق قضیه مجموع درجه‌های راس‌ها و تعریف گراف (r - منتظم) داریم: 

deg(vi)=rm+rn=r(m+n)=2qr(m+n)=2qq=rm  r(m+n)=2(rm)rm+rn=2rmrn=rmn=m

قضیه

اگر در یک گراف ساده و دوبخشی، مرتبه p و اندازه q باشد، آن‌گاه:

qp24

اثبات

چون گراف G دوبخشی است، لذا بیش‌ترین تعداد یال‌های آن (مطابق قضایای گراف کامل دوبخشی) u=mn خواهد بود که m تعداد راس‌های بخش VG و n تعداد راس‌های بخش WG است.   

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

از طرفی می‌دانیم:

p=m+nm=pnu=mnu=(pn)nu=npn2

چون u آهنگ تغییرات تعداد یال‌ها را نشان می‌دهد، پس: 

dudn=0p2n=0n=p2d2udn2=02<0

پس بیش‌ترین مقدار u در نقطه n=p2 اتفاق می‌افتد، یعنی:

max(u)=p2pp22=p22p24max(u)=p24

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

qp24

دریافت مثال

نکته

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

تعداد دور به طول 2k در گراف کامل دوبخشی برابر است با:

mknkk!k-1!2

دریافت مثال

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

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

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

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

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

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

یک گراف کامل دوبخشی با m,n راس که به‌صورت km,n نمایش داده می‌شود که دومجموعه uG و wG در خاصیت‌های زیر صدق می‌کند:

  • یک یال از هر راس uG مانند ui به هر راس wG مانند wj موجود است.
  • یک یال از هر راس uG مانند ui به هر راس uG مانند uk موجود نباشد.
  • یک یال از هر راس wG مانند wj به هر راس دیگر wG مانند wf موجود نباشد.    

تمرین

یک گراف کامل دوبخشی k3,3 نشان دهید: 

گراف دوبخشی - پیمان گردلو

یک گراف کامل دوبخشی k3,4 نشان دهید: 

گراف دوبخشی - پیمان گردلو

یک گراف کامل دوبخشی k2,5 نشان دهید: 

گراف دوبخشی - پیمان گردلو

دریافت مثال

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

قضیه

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

qkm,n=mn

q اندازه گراف km,n است. 

اثبات

می‌دانیم گراف km,n دارای m راس در یک مجموعه و n راس در مجموعه دیگر است و از طرفی تعداد کل راس‌ها p=m+n (مرتبه گراف) می‌باشد: 

برای یافتن تعداد یال‌های گراف کامل دوبخشی km,n ابتدا تعداد کل یال‌های یک گراف کامل از مرتبه m+n را محاسبه می‌کنیم، سپس تعداد کل یال‌هایی که راس‌های دو مجموعه را در خود مجموعه‌ها به‌هم وصل می‌نماید از آن کم می‌کنیم، داریم:  

qkm,n=m+n     2m2+n2=(m+n)(m+n1)2m(m1)2+n(n1)2=(m+n)2(m+n)2m2+n2mn2=(m2+n2+2mn)mnm2n2+m+n2=2mn2=mn

دریافت مثال

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

تمام گراف‌های کامل دو‌بخشی به‌غیر از k1,1 قطر 2 دارند، زیرا برای هر دونقطه دل‌خواه در UG و WG دقیقا به‌فاصله 2 از یک‌دیگر قرار دارند (فاصله، کوتاه‌ترین مسیر بین دو راس بود). یک یال برای رفتن به زیر گروه دیگر از راس‌ها و یک یال هم برای برگشتن.

به‌عنوان نمونه، به گراف کامل دوبخشی زیر توجه کنید:

گراف دوبخشی - پیمان گردلو  

در این گراف اگر از راس W1 حرکت می‌کنیم، یک یال ما را به U1 می‌رساند و یک یال ما را از U1 مثلا به W3 می‌رساند یعنی با دو یال به دو راس W1 و W3 از WG رسیدیم.    

گراف کامل دوبخشی k1,1 تنها گرافی است که قطرش 1 می‌باشد، زیرا این گراف تنها دو راس دارد و کوتاه‌ترین مسیر بین آنها به طول یک است.

دریافت مثال

نکته

1- هر گراف دوبخشی، زیر گراف یک گراف دوبخشی کامل می‌باشد.

2- هر زیر گراف از یک گراف دوبخشی کامل، یک گراف دوبخشی است.

دریافت مثال

مثال‌ها و جواب‌ها

گراف دوبخشی

2,200تومان
خرید فایل PDF مثال ها و جواب ها

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