Bipartitelikka tekshirish

Shart

Sizga yo‘naltirilmagan graf berilgan. U ikki bo‘lakli (bipartite) ekanligini tekshiring, va agar shunday bo‘lsa — uning bo‘laklarini chiqaring.

Yechim

Teorema mavjud: graf ikki bo‘lakli bo‘ladi faqat va faqat uning barcha sikllari juft uzunlikka ega bo‘lsa.
Biroq amaliyotda boshqa ta’rifdan foydalanish qulayroq: graf ikki bo‘lakli bo‘ladi faqat va faqat u ikki rangli bo‘lsa.

Har bir hali tashrif buyurilmagan cho‘qqidan boshlab DFSdan foydalanamiz (oldingi masaladagi kabi BFSdan ham foydalanish mumkin). Har bir qidiruvda biz boshlaydigan cho‘qqini 1 bo‘lakka (masalan, 0 rangga) tayinlaymiz. Har safar bir bo‘lakdagi cho‘qqining hali tashrif buyurilmagan qo‘shnisiga tashrif buyurganimizda, uni boshqa bo‘lakka tayinlaymiz.

Agar biz allaqachon tashrif buyurilgan qo‘shniga o‘tishga urinayotgan bo‘lsak, u boshqa bo‘lakda ekanligini tekshiramiz. Agar u o‘sha bo‘lakda bo‘lib chiqsa, graf ikki bo‘lakli emas degan xulosaga kelamiz.

Barcha cho‘qqilarga tashrif buyurib, ularni bo‘laklarga muvaffaqiyatli taqsimlaganimizdan so‘ng, graf ikki bo‘lakli ekanligini va uning bo‘linishini qurganimizni bilamiz.