گراف کامل دوبخشی + کد (الگوریتم پریم)
صورت سوال: گرافهای کامل دوبخشی به گرافهای کاملی گفته میشود که در آنها مجموعه رأسها را بتوان به دو زیرمجموعه V1 و V2 افراز کرد، بهگونهای که هر رأس از مجموعه V1 به تمام رئوس مجموعه V2 متصل باشد. اگر تعداد رئوس موجود در V1 برابر n باشد و تعداد رئوس موجود در V2 برابر m باشد، گراف کامل دوبخشی که از این دو مجموعه رئوس ساخته میشود را معمولاً با km,n نمایش میدهند. شکل زیر یک گراف k2,3 را نشان میدهد. الف) فرض کنید ماتریس مجاورت گراف بدون جهت G(V,E) شامل n رأس موجود باشد. الگوریتم عقبگردی ارائه دهید که مشخص نماید آیا گراف مفروض G ، یک گراف دوبخشی کامل است یا خیر؟ ب) پیچیدگی زمانی الگوریتم ارائهشده در قسمت (الف) را محاسبه نمایید. سورس کد در زبان C++ و توضیحات کامل قسمتهای مختلف آن در فایل این مطلب موجود است. …
0 دیدگاه