گراف دوبخشی را می‌توان با دو رنگ طوری رنگ کرد که دو سرِ هر یال رنگ متفاوت داشته باشند. اگر چنین رنگ‌آمیزی ممکن نباشد، یک چرخهٔ فرد گواهِ روشنِ شکست است. این تمرین فقط جوابِ بله یا خیر نمی‌دهد؛ یا رنگِ همهٔ گره‌ها را نگه می‌دارد، یا خودِ چرخهٔ بستهٔ فرد را بازسازی می‌کند.
چرخهٔ زوج مانع نیست
نمونهٔ اول مربعِ A–B–C–D–A به‌همراه U منزوی است. با شروعِ رنگِ صفر برای A، همسایه‌های B وD رنگِ یک می‌گیرند وC رنگِ صفر. تمام یال‌ها دو سرِ متفاوت دارند؛ وجودِ چرخه به‌تنهایی گراف را غیردوبخشی نمی‌کند، طولِ فرد مهم است.
U نیز باید در خروجی باشد. کد پس از پایانِ یک مؤلفه، از گرهٔ رنگ‌نشدهٔ بعدی پیمایشِ تازه آغاز می‌کند. رنگِ صفر یا یکِ یک مؤلفه را می‌توان کامل برعکس کرد و همان جدایی را داشت؛ نامِ رنگ هویت یا رتبهٔ واقعیِ گروه نیست.
BFS، رنگ و والد را کنار هم نگه می‌دارد
برای هر مؤلفه، صفِ FIFO و دفترِ parent وdepth داریم. وقتی همسایه‌ای تازه کشف می‌شود، رنگِ مخالفِ رأسِ فعلی می‌گیرد. اگر یالی به رأسِ ازقبلرنگ‌شده برسد و دو رنگ برابر باشند، همان یال تعارض است؛ فقط visited داشتن برای تشخیصِ این مسئله کافی نیست.
رنگ‌آمیزیِ موفق دوباره روی تمام یال‌های ورودی کنترل می‌شود. صرفِ خالی‌شدنِ صف یا بازدیدِ همهٔ گره‌ها گواهِ کافی نیست. در این فایل گراف ساده، بدون جهت و بی‌وزن است؛ جهتِ parent مربوط به درختِ پیمایش است، نه جهتِ یالِ مسئله.
پنج‌ضلعی یک گواهِ فرد می‌سازد
نمونهٔ دوم A–B–C–D–E–A وU است. یک یال، دو رأسِ هم‌رنگ را وصل می‌کند. مسیرِ parent هر دو سر را تا نخستین نیای مشترک دنبال می‌کنیم و با خودِ یالِ تعارض می‌بندیم؛ لازم نیست یکی از دو سر، نیای دیگری باشد.
در ترتیبِ ثابتِ این مثال، چرخهٔ C،B،A،E،D،C بازمی‌گردد. پنج یال دارد، ابتدا و انتها برابرند و هیچ رأسِ درونی تکرار نشده است. تابعِ مستقل تک‌تک یال‌ها، بسته‌بودن، فردبودن و یکتاییِ رأس‌های درونِ چرخه را کنترل می‌کند؛ نامِ یک رأسِ متعارض به‌تنهایی جای چرخه نیست.
همهٔ گراف‌های کوچک را با رنگ‌آمیزیِ کامل بسنجیم
oracleِ مستقل تمام۲^۵انتسابِ دو رنگ برای پنج رأس را می‌سازد و می‌پرسد آیا یکی همهٔ یال‌ها را رعایت می‌کند. این مسیر از BFS، parent یا بازسازیِ چرخه استفاده نمی‌کند. آن را روی تمام۱۰۲۴گرافِ سادهٔ پنج‌رأسی اجرا کرده‌ایم.
۳۷۶گراف دوبخشی و۶۴۸گراف غیردوبخشی‌اند. در هر خروجیِ مثبت، تمام گره‌ها و یال‌ها کنترل شده‌اند؛ در هر خروجیِ منفی، گواهِ چرخه واقعاً معتبر است. این پوششِ کاملِ جهانِ پنج‌رأسی است، نه اثباتِ برنامه برای اندازهٔ دلخواه یا اندازه‌گیریِ سرعت.
این حلِ عمومیِ قید یا تطبیق نیست
AC-3 دامنهٔ متغیرها را فیلتر می‌کند و ممکن است با دامنهٔ غیرخالی، جوابِ مشترک نداشته باشد. اینجا مسئلهٔ خاصِ دو رنگ، همراهِ گواه حل می‌شود. DPLL جست‌وجوی فرمولِ منطقی است؛ به آن حل‌کننده تبدیل نشده‌ایم.
دوبخشی‌بودن نیز خودش جفت‌سازیِ ترجیحی یا تخصیصِ کم‌هزینه تولید نمی‌کند. رنگ، معنایِ تجاریِ درستِ دو دسته را ثابت نمی‌کند؛ ابتدا باید بدانید یال و گره در مسئلهٔ واقعی چه معنایی دارند. از نتیجهٔ گراف، رضایت یا اختیارِ اقدام نتیجه نمی‌گیریم.
حالتِ خالی و منزوی کنترل می‌شود و پنج ورودیِ نامعتبر، از یالِ تکراری و self-loop تا جهت‌دار یا بیش از۸رأس، رد می‌شوند. منبعِ Princeton از DFS استفاده می‌کند؛ کدِ اصیلِ اینجا BFS و نیای مشترک دارد و Java اجرا نشده است. ادامه در مبانی هوش مصنوعی؛ این گراف ساختارِ واقعیِ محصولِ اپرا نیست.
فایل تمرین و منبع
کد مستقل تمرین و تمام کنترل‌ها؛ Python · ورودی و تمام نتایج اجرای واقعی؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.