صورت سوال:

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

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

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

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