گراف کامل دوبخشی + کد (الگوریتم پریم)

گراف کامل دوبخشی + کد (الگوریتم پریم)

صورت سوال:

گراف­های کامل دوبخشی به گراف­های کاملی گفته می‌شود که در آن­ها مجموعه رأس‌ها را بتوان به دو زیرمجموعه V1 و V2 افراز کرد، به‌گونه‌ای که هر رأس از مجموعه V1 به تمام رئوس مجموعه V2 متصل باشد. اگر تعداد رئوس موجود در V1 برابر n باشد و تعداد رئوس موجود در V2 برابر m باشد، گراف کامل دوبخشی که از این دو مجموعه رئوس ساخته می‌شود را معمولاً با km,n نمایش می‌دهند. شکل زیر یک گراف k2,3 را نشان می‌دهد.

الف) فرض کنید ماتریس مجاورت گراف بدون جهت G(V,E) شامل n رأس موجود باشد. الگوریتم عقب‌گردی ارائه دهید که مشخص نماید آیا گراف مفروض G، یک گراف دوبخشی کامل است یا خیر؟

ب) پیچیدگی زمانی الگوریتم ارائه‌شده در قسمت (الف) را محاسبه نمایید.

 

سورس کد در زبان C++ و توضیحات کامل قسمتهای مختلف آن در فایل این مطلب موجود است.

دانلود

پیشگوی اعظم

من از دوران نوجوانی رویایی داشتم! رویای تاسیس یک مکان برای به اشتراک گذاشتن ایده ها و نظرات خودم و همچنین جایی برای دانشجویان و دانش آموزان عزیز که بتوانند تمامی مقالات و جزوات مورد نیاز خودرا از طریق یک سایت مرجع تامین کنند.اکنون،این رویا،godofdoc (خدای داکیومنت) نام دارد D:a

شاید این مطالب را هم دوست داشته باشید

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *