پرش به محتویات

بررسی دو بخشی بودن یک گراف

گراف دو بخشی گرافی است که رئوس آن را می‌توان به دو مجموعه مجزا تقسیم کرد، به طوری که هر یال، دو رأس از مجموعه‌های متفاوت را به هم وصل کند (یعنی هیچ یالی وجود ندارد که دو رأس از یک مجموعه را به هم متصل کند). این مجموعه‌ها معمولاً «بخش» نامیده می‌شوند.

یک گراف بدون جهت به شما داده می‌شود. بررسی کنید که آیا این گراف دو بخشی است یا خیر، و اگر هست، بخش‌های آن را خروجی دهید.

الگوریتم

قضیه‌ای وجود دارد که بیان می‌کند یک گراف دو بخشی است اگر و تنها اگر تمام دورهای آن طول زوج داشته باشند. با این حال، در عمل استفاده از یک صورت‌بندی دیگر از تعریف راحت‌تر است: یک گراف دو بخشی است اگر و تنها اگر دو-رنگ‌پذیر باشد.

بیایید از یک سری جستجوی اول سطح استفاده کنیم که از هر رأسی که هنوز بازدید نشده شروع می‌شود. در هر جستجو، رأسی که از آن شروع می‌کنیم را به بخش ۱ اختصاص می‌دهیم. هر بار که همسایه هنوز بازدید نشده‌ی یک رأس که به یک بخش تخصیص داده شده را بازدید می‌کنیم، آن را به بخش دیگر اختصاص می‌دهیم. وقتی سعی می‌کنیم به همسایه‌ای از یک رأس که به یک بخش تخصیص داده شده و قبلاً بازدید شده است برویم، بررسی می‌کنیم که آیا به بخش دیگر تخصیص داده شده است یا خیر؛ اگر به همان بخش تخصیص داده شده باشد، نتیجه می‌گیریم که گراف دو بخشی نیست. هنگامی که تمام رئوس را بازدید کرده و با موفقیت به بخش‌ها تخصیص دادیم، می‌دانیم که گراف دو بخشی است و افراز آن را ساخته‌ایم.

پیاده‌سازی

int n;
vector<vector<int>> adj;

vector<int> side(n, -1);
bool is_bipartite = true;
queue<int> q;
for (int st = 0; st < n; ++st) {
    if (side[st] == -1) {
        q.push(st);
        side[st] = 0;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int u : adj[v]) {
                if (side[u] == -1) {
                    side[u] = side[v] ^ 1;
                    q.push(u);
                } else {
                    is_bipartite &= side[u] != side[v];
                }
            }
        }
    }
}

cout << (is_bipartite ? "YES" : "NO") << endl;

مسائل تمرینی: