Bipartite Graph

Sebuah graph disebut bipartite bila vertex-nya dapat dipartisi menjadi dua himpunan A dan B sedemikian sehingga setiap edge hanya menghubungkan vertex dari A ke B (tidak ada edge di dalam A atau di dalam B). Property ini memungkinkan kita mewarnai graph dengan dua warna — misalnya merah dan biru — sehingga setiap edge selalu menghubungkan dua warna berbeda. Pada Chapter ini kita akan mengimplementasikan algoritma 2-coloring dengan BFS dan DFS, lalu mengaplikasikannya pada masalah “graph is bipartite?” dan problem matching klasik. Pemahaman bipartite graph adalah kunci menuju algoritma maximum matching (Hungarian, Hopcroft-Karp) yang akan dibahas di Section lanjutan.

Definisi dan Properti #

Graph G = (V, E) disebut bipartite bila terdapat partisi V = A ∪ B dengan A ∩ B = ∅ sehingga setiap edge {u, v} memenuhi u ∈ A dan v ∈ B (atau sebaliknya). Beberapa properti penting:

Graph bipartite tidak mengandung cycle dengan panjang ganjil (triangle, pentagon, dll).
Setiap tree adalah bipartite (tidak ada cycle sama sekali → tidak ada cycle ganjil).
Complete bipartite graph K_{m,n}: m vertex di A, n vertex di B, setiap vertex A terhubung ke setiap vertex B.
Cycle genap (segiempat, segienam) dapat menjadi bipartite; cycle ganjil (triangle, pentagon) tidak bisa.

flowchart LR subgraph A[Partisi A] a0[0] a2[2] a4[4] end subgraph B[Partisi B] b1[1] b3[3] end a0 --- b1 a0 --- b3 a2 --- b1 a2 --- b3 a4 --- b1

Pada graph di atas, vertex {0, 2, 4} adalah partisi A dan {1, 3} adalah partisi B. Setiap edge menghubungkan vertex dari partisi berbeda — graph bipartite.

Mekanisme: 2-Coloring dengan BFS #

Algoritma 2-coloring:

Inisialisasi color[] = -1 (belum diwarnai).
Untuk setiap vertex s yang belum diwarnai:
- Beri warna 0 pada s.
- BFS: untuk setiap neighbor v dari u:
  - Bila v belum diwarnai → beri warna 1 - color[u] (warna lawan).
  - Bila v sudah diwarnai dan color[v] == color[u] → konflik → graph tidak bipartite.
Bila seluruh BFS selesai tanpa konflik → graph bipartite.

Kompleksitas: O(V+E).

Implementasi BFS #

Kode: Cek Bipartite dengan BFS #

cpp
#include <iostream>
#include <vector>
#include <queue>

class Graph {
public:
    explicit Graph(int n) : adj_(n) {}
    void add_edge_undirected(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

// Return true bila graph bipartite. color[] berisi assignment warna (0 atau 1).
bool is_bipartite_bfs(const Graph& g, std::vector<int>& color) {
    int n = g.v_count();
    color.assign(n, -1);
    std::queue<int> q;

    for (int s = 0; s < n; ++s) {
        if (color[s] != -1) continue;
        color[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g.neighbors(u)) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];   // warna lawan
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;               // konflik: edge same-color
                }
            }
        }
    }
    return true;
}

void print_result(const Graph& g, const std::string& name) {
    std::vector<int> color;
    bool bip = is_bipartite_bfs(g, color);
    std::cout << name << ": " << (bip ? "bipartite" : "TIDAK bipartite") << '\n';
    if (bip) {
        std::cout << "  Partisi A (warna 0):";
        for (int v = 0; v < g.v_count(); ++v) if (color[v] == 0) std::cout << " " << v;
        std::cout << '\n';
        std::cout << "  Partisi B (warna 1):";
        for (int v = 0; v < g.v_count(); ++v) if (color[v] == 1) std::cout << " " << v;
        std::cout << '\n';
    }
}

int main() {
    // Test 1: even cycle 0-1-2-3-0 (segiempat)
    Graph g1(4);
    g1.add_edge_undirected(0, 1);
    g1.add_edge_undirected(1, 2);
    g1.add_edge_undirected(2, 3);
    g1.add_edge_undirected(3, 0);
    print_result(g1, "Graph 1 (segiempat)");

    // Test 2: odd cycle 0-1-2-0 (triangle)
    Graph g2(3);
    g2.add_edge_undirected(0, 1);
    g2.add_edge_undirected(1, 2);
    g2.add_edge_undirected(2, 0);
    print_result(g2, "Graph 2 (triangle)");

    // Test 3: tree (selalu bipartite)
    Graph g3(7);
    g3.add_edge_undirected(0, 1);
    g3.add_edge_undirected(0, 2);
    g3.add_edge_undirected(1, 3);
    g3.add_edge_undirected(1, 4);
    g3.add_edge_undirected(2, 5);
    g3.add_edge_undirected(2, 6);
    print_result(g3, "Graph 3 (tree)");

    return 0;
}

Output yang Dihasilkan:

text
Graph 1 (segiempat): bipartite
  Partisi A (warna 0): 0 2
  Partisi B (warna 1): 1 3
Graph 2 (triangle): TIDAK bipartite
Graph 3 (tree): bipartite
  Partisi A (warna 0): 0 3 4 5 6
  Partisi B (warna 1): 1 2

Baris color.assign(n, -1);: inisialisasi array warna. -1 = belum diwarnai. Kita pakai 0 dan 1 sebagai dua warna.
Baris for (int s = 0; s < n; ++s): loop seluruh vertex untuk menangani graph disconnected. Setiap komponen diberi starting color 0.
Baris color[s] = 0; q.push(s);: beri warna 0 pada titik mulai komponen. Warna 0 adalah konvensi (bisa juga 1, hasil tetap valid).
Baris color[v] = 1 - color[u];: beri warna lawan — bila u berwarna 0, v berwarna 1, dan sebaliknya. Inilah inti 2-coloring.
Baris else if (color[v] == color[u]) return false;: bila v sudah diwarnai dengan warna yang sama dengan u, ada konflik — edge {u,v} menghubungkan dua vertex warna sama → bukan bipartite.
Hasil Graph 1 (segiempat): bipartite. Vertex {0, 2} berwarna 0, {1, 3} berwarna 1. Setiap edge menghubungkan partisi berbeda.
Hasil Graph 2 (triangle): TIDAK bipartite. BFS dari 0: warnai 0 (0), 1 (1), 2 (0). Saat cek edge 2-0, kedua vertex berwarna 0 → konflik → return false.
Hasil Graph 3 (tree): bipartite. Tree selalu bipartite karena tidak ada cycle → tidak ada cycle ganjil.

Implementasi DFS #

Versi DFS lebih ringkas dan memungkinkan rekursi natural.

Kode: Cek Bipartite dengan DFS #

cpp
#include <iostream>
#include <vector>

class Graph {
public:
    explicit Graph(int n) : adj_(n) {}
    void add_edge_undirected(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

// DFS rekursif: return false bila ada konflik warna
bool dfs_color(const Graph& g, int u, int c, std::vector<int>& color) {
    color[u] = c;
    for (int v : g.neighbors(u)) {
        if (color[v] == -1) {
            if (!dfs_color(g, v, 1 - c, color)) return false;
        } else if (color[v] == c) {
            return false;   // konflik
        }
    }
    return true;
}

bool is_bipartite_dfs(const Graph& g, std::vector<int>& color) {
    int n = g.v_count();
    color.assign(n, -1);
    for (int s = 0; s < n; ++s) {
        if (color[s] == -1) {
            if (!dfs_color(g, s, 0, color)) return false;
        }
    }
    return true;
}

int main() {
    // Test: pentagon (5-cycle, ganjil) -> tidak bipartite
    Graph penta(5);
    penta.add_edge_undirected(0, 1);
    penta.add_edge_undirected(1, 2);
    penta.add_edge_undirected(2, 3);
    penta.add_edge_undirected(3, 4);
    penta.add_edge_undirected(4, 0);
    std::cout << "Pentagon: " << (is_bipartite_dfs(penta, std::vector<int>()) ? "bipartite" : "TIDAK bipartite") << '\n';

    // Test: hexagon (6-cycle, genap) -> bipartite
    Graph hexa(6);
    hexa.add_edge_undirected(0, 1);
    hexa.add_edge_undirected(1, 2);
    hexa.add_edge_undirected(2, 3);
    hexa.add_edge_undirected(3, 4);
    hexa.add_edge_undirected(4, 5);
    hexa.add_edge_undirected(5, 0);

    std::vector<int> color;
    bool bip = is_bipartite_dfs(hexa, color);
    std::cout << "Hexagon: " << (bip ? "bipartite" : "TIDAK bipartite") << '\n';
    if (bip) {
        std::cout << "  Warna vertex:";
        for (int v = 0; v < hexa.v_count(); ++v) std::cout << " " << color[v];
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
Pentagon: TIDAK bipartite
Hexagon: bipartite
  Warna vertex: 0 1 0 1 0 1

Baris bool dfs_color(const Graph& g, int u, int c, ...): parameter c adalah warna yang akan diberikan ke u. Rekursi memanggil dfs_color(g, v, 1 - c, color) untuk memberi warna lawan.
Baris else if (color[v] == c) return false;: bila neighbor v sudah berwarna sama dengan c (warna u), konflik — edge {u,v} melanggar bipartite.
Hasil Pentagon: tidak bipartite. Cycle panjang 5 (ganjil) selalu melanggar bipartite. DFS mewarnai 0(0) → 1(1) → 2(0) → 3(1) → 4(0). Saat cek edge 4-0, kedua vertex berwarna 0 → konflik.
Hasil Hexagon: bipartite. Cycle panjang 6 (genap). Vertex 0,2,4 berwarna 0; vertex 1,3,5 berwarna 1. Setiap edge menghubungkan warna berbeda.

Aplikasi: Graph Coloring pada Grid #

Pada masalah grid 2D, vertex adalah sel (r, c) dan edge menghubungkan sel-sel yang adjacent (atas/bawah/kiri/kanan). Grid selalu bipartite — warnai dengan (r + c) % 2.

Kode: Grid 2-Coloring #

cpp
#include <iostream>
#include <vector>

int main() {
    const int R = 4, C = 4;
    // Grid 4x4. Warna sel (r, c) = (r + c) % 2
    std::cout << "Grid 4x4 (chessboard pattern):\n";
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            std::cout << (((r + c) % 2) ? 'B' : 'A') << ' ';
        }
        std::cout << '\n';
    }

    // Verifikasi: setiap pasangan adjacent berbeda warna
    bool valid = true;
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            int my_color = (r + c) % 2;
            // Cek neighbor kanan
            if (c + 1 < C) {
                int neighbor_color = (r + c + 1) % 2;
                if (my_color == neighbor_color) { valid = false; }
            }
            // Cek neighbor bawah
            if (r + 1 < R) {
                int neighbor_color = (r + 1 + c) % 2;
                if (my_color == neighbor_color) { valid = false; }
            }
        }
    }
    std::cout << "Verifikasi bipartite: " << (valid ? "YA" : "TIDAK") << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Grid 4x4 (chessboard pattern):
A B A B
B A B A
A B A B
B A B A
Verifikasi bipartite: YA

Baris (((r + c) % 2) ? 'B' : 'A'): rumus coloring grid — sel (r, c) berwarna A bila (r+c) genap, B bila ganjil. Inilah pola papan catur klasik.
Baris int my_color = (r + c) % 2;: warna sel saat ini. (r+c) % 2 menghasilkan 0 atau 1.
Baris int neighbor_color = (r + c + 1) % 2;: warna neighbor kanan = (r + c + 1) % 2 = 1 - (r + c) % 2. Selalu berbeda dengan warna saat ini.
Hasil: pola papan catur ABAB/BABA/ABAB/BABA. Verifikasi konfirmasi: setiap pasangan adjacent berbeda warna.

Aplikasi: Matching (Preview) #

Pada graph bipartite, masalah maximum matching (pasangan maksimal vertex A ke vertex B melalui edge) dapat diselesaikan dengan:

Hungarian algorithm — O(V³), optimal untuk weighted bipartite matching.
Hopcroft-Karp — O(E √V), optimal untuk unweighted.

Detail lengkap dibahas pada Section algoritma lanjutan. Pada Chapter ini, kita hanya menyentuh intuisi: bila graph bipartite, banyak problem optimasi menjadi lebih mudah.

Kompleksitas #

Aspek	BFS	DFS
Kompleksitas waktu	O(V+E)	O(V+E)
Kompleksitas memori	O(V) queue	O(V) call stack
Stack overflow risk	Tidak	Ya, untuk graph dalam
Implementasi	Sedikit lebih panjang	Lebih ringkas

Ringkasan #

Graph bipartite = vertex dapat dipartisi menjadi dua himpunan, setiap edge menghubungkan partisi berbeda.
Algoritma 2-coloring: BFS/DFS beri warna 0/1, bila konflik (edge same-color) → tidak bipartite.
Kompleksitas O(V+E) untuk kedua implementasi.
Hukum dasar: cycle ganjil → tidak bipartite; cycle genap atau tidak ada cycle → bipartite. Tree selalu bipartite.
Grid 2D selalu bipartite dengan formula warna (r + c) % 2.
Aplikasi: matching (Hopcroft-Karp, Hungarian), job assignment, scheduling, problem graph coloring pada grid.