Đồ thị hai phía (bipartite graph) là một loại đồ thị đặc biệt, được cấu tạo từ hai tập hợp đỉnh rời nhau, sao cho mọi cạnh chỉ nối một đỉnh ở tập này với một đỉnh ở tập kia. Nói cách khác, không có cạnh nào tồn tại giữa hai đỉnh trong cùng một tập hợp.

Một cách trực quan, chúng ta có thể hình dung đồ thị hai phía bằng cách tô màu các đỉnh bằng hai màu khác nhau. Mỗi cạnh sẽ luôn nối hai đỉnh có màu sắc khác nhau, và không có hai đỉnh cùng màu nào được nối với nhau.

Một đặc điểm quan trọng của đồ thị hai phía là không chứa chu trình có độ dài lẻ.

Kiểm tra Đồ thị hai phía bằng Phương pháp Tô màu

Để xác định xem một đồ thị có phải là đồ thị hai phía hay không, chúng ta có thể sử dụng thuật toán duyệt theo chiều sâu (DFS) kết hợp với tô màu. Bắt đầu bằng việc chọn một đỉnh chưa được tô màu, gán cho nó màu 1. Sau đó, duyệt qua tất cả các đỉnh lân cận của nó và gán cho chúng màu 2. Tiếp tục quá trình này, luân phiên gán màu 1 và màu 2 cho các đỉnh kế tiếp trong cùng một thành phần liên thông. Nếu trong quá trình tô màu, chúng ta phát hiện có hai đỉnh kề nhau cùng màu, thì đồ thị đó không phải là đồ thị hai phía.

Ví dụ: Kiểm tra tính hai phía của đồ thị

Cho một đồ thị vô hướng đơn giản, hãy xác định xem nó có phải là đồ thị hai phía hay không. Đầu vào:

• Dòng đầu tiên: Hai số nguyên n và m, lần lượt là số đỉnh và số cạnh. Đỉnh được đánh số từ 1 đến n.
• m dòng tiếp theo: Mỗi dòng gồm hai số nguyên x và y, biểu thị một cạnh nối đỉnh x và y. Đầu ra:
• Chuỗi "Yes" nếu là đồ thị hai phía, "No" nếu ngược lại. Dữ liệu mẫu:

4 4
1 2
2 3
3 4
1 4

Kết quả mẫu:

Yes

Ràng buộc: 2 ≤ n ≤ 1000, 0 ≤ m ≤ 10000, 1 ≤ x, y ≤ n, x ≠ y.

Mã nguồn

#include <iostream>
#include <vector>
#include <cstdio>

const int MAX_VERTICES = 1000 + 10;
int color[MAX_VERTICES]; // 0: chưa tô màu, 1: màu 1, 2: màu 2
std::vector<int> adj[MAX_VERTICES];
int num_vertices, num_edges;

bool is_bipartite_dfs(int u) {
    for (int v : adj[u]) {
        if (color[v] == 0) { // Nếu đỉnh v chưa được tô màu
            color[v] = 3 - color[u]; // Gán màu xen kẽ
            if (!is_bipartite_dfs(v)) {
                return false; // Nếu phát hiện xung đột ở nhánh con
            }
        } else if (color[v] == color[u]) {
            return false; // Nếu hai đỉnh kề có cùng màu
        }
    }
    return true; // Không có xung đột trong thành phần liên thông này
}

int main() {
    scanf("%d %d", &num_vertices, &num_edges);
    for (int i = 0; i < num_edges; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= num_vertices; ++i) {
        if (color[i] == 0) { // Nếu đỉnh i chưa được tô màu
            color[i] = 1; // Bắt đầu tô màu cho thành phần liên thông mới
            if (!is_bipartite_dfs(i)) {
                printf("No\n");
                return 0;
            }
        }
    }

    printf("Yes\n");
    return 0;
}

Tìm Khớp Lớn Nhất trong Đồ thị hai phía bằng Thuật toán Hungarian

Thuật toán Hungarian là một phương pháp hiệu quả để tìm số lượng cặp ghép nối lớn nhất trong một đồ thị hai phía. Ghép nối (matching) là một tập hợp các cạnh sao cho không có hai cạnh nào chung đỉnh. Mục tiêu là tìm một tập hợp các cạnh ghép nối có số lượng lớn nhất.

Nguyên tắc hoạt động: Thuật toán này duyệt qua từng đỉnh ở một trong hai tập hợp của đồ thị hai phía. Với mỗi đỉnh, nó cố gắng tìm một đỉnh chưa được ghép nối ở tập còn lại. Nếu đỉnh đó đã được ghép nối, thuật toán sẽ cố gắng tìm một cặp ghép nối mới cho đỉnh đang ghép nối nó. Quá trình này lặp lại một cách tham lam cho đến khi không thể tìm thêm cặp ghép nối nào nữa.

Ví dụ 1: Bài toán Khớp Lớn Nhất cơ bản

Cho một đồ thị hai phía với n1 đỉnh ở tập bên trái (đánh số từ 1 đến n1) và n2 đỉnh ở tập bên phải (đánh số từ 1 đến n2), cùng m cạnh. Tìm số lượng ghép nối lớn nhất. Đầu vào:

• Dòng đầu tiên: n1, n2, m.
• m dòng tiếp theo: Mỗi dòng chứa u (đỉnh bên trái) và v (đỉnh bên phải). Đầu ra: Số nguyên biểu thị số lượng ghép nối lớn nhất. Dữ liệu mẫu:

2 2 4
1 1
1 2
2 1
2 2

Kết quả mẫu:

2

Ràng buộc: 1 ≤ n1, n2 ≤ 500, 1 ≤ u ≤ n1, 1 ≤ v ≤ n2, 1 ≤ m ≤ 10^5.

Mã nguồn

#include <iostream>
#include <vector>
#include <cstring> // For memset

const int MAX_NODES_PART = 500 + 5;
std::vector<int> adj[MAX_NODES_PART]; // Adjacency list for the left part
bool visited_round[MAX_NODES_PART]; // Tracks visited nodes in the current DFS round
int match_partner[MAX_NODES_PART]; // Stores the matched partner for each node in the right part
int n1, n2, m;

bool can_find_match(int u) {
    for (int v : adj[u]) {
        if (!visited_round[v]) {
            visited_round[v] = true;
            // If v is not matched OR the current match of v can find another match
            if (match_partner[v] == 0 || can_find_match(match_partner[v])) {
                match_partner[v] = u; // Match u with v
                return true;
            }
        }
    }
    return false; // Cannot find a match for u
}

int main() {
    std::cin >> n1 >> n2 >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v); // Edges go from left part to right part
    }

    int max_matching = 0;
    for (int i = 1; i <= n1; ++i) {
        memset(visited_round, 0, sizeof(visited_round)); // Reset visited for each node in the left part
        if (can_find_match(i)) {
            max_matching++;
        }
    }

    std::cout << max_matching << std::endl;
    return 0;
}

Ví dụ 2: Bài toán Phủ Bàn Cờ

Cho một bàn cờ n x n. Một số ô đã bị chiếm bởi quân cờ và không thể phủ. Cần phủ tối đa bao nhiêu ô bằng các quân domino 1x2? Ý tưởng: Chúng ta có thể biểu diễn bàn cờ dưới dạng đồ thị hai phía. Các ô kề nhau trên bàn cờ sẽ được coi là có cạnh nối. Tô màu bàn cờ như bàn cờ vua (hai màu xen kẽ). Các ô cùng màu tạo thành một tập hợp trong đồ thị hai phía. Việc phủ bàn cờ bằng domino tương đương với việc tìm một cặp ghép nối lớn nhất trong đồ thị hai phía này. Số ô tối đa có thể phủ bằng 2 * (kích thước khớp nối lớn nhất). Đầu vào:

• Dòng đầu tiên: n, m (số ô bị chiếm).
• m dòng tiếp theo: Tọa độ (x, y) của các ô bị chiếm. Đầu ra: Số ô tối đa có thể phủ. Dữ liệu mẫu:

3 1
2 2

Kết quả mẫu:

8

Ràng buộc: 2 ≤ n ≤ 40, 0 ≤ m ≤ n^2.

Mã nguồn

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

const int MAX_BOARD_DIM = 40;
const int MAX_NODES = MAX_BOARD_DIM * MAX_BOARD_DIM + 5;

int board_state[MAX_BOARD_DIM + 1][MAX_BOARD_DIM + 1]; // 0: empty, 1: occupied
int partition_id[MAX_BOARD_DIM + 1][MAX_BOARD_DIM + 1]; // ID of node in its partition
std::vector<int> adj[MAX_NODES];
int match_partner[MAX_NODES];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int n_board, m_occupied;
int left_partition_count, right_partition_count;

bool find_domino_match(int u) {
    for (int v : adj[u]) {
        if (!partition_id[v]) { // Using partition_id as visited flag for this round
            partition_id[v] = 1; // Mark as visited
            if (match_partner[v] == 0 || find_domino_match(match_partner[v])) {
                match_partner[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d %d", &n_board, &m_occupied);
    for (int i = 0; i < m_occupied; ++i) {
        int r, c;
        scanf("%d %d", &r, &c);
        board_state[r][c] = 1; // Mark occupied cells
    }

    int node_idx_left = 0;
    int node_idx_right = 0;

    // Assign partitions and IDs based on chessboard coloring
    for (int i = 1; i <= n_board; ++i) {
        for (int j = 1; j <= n_board; ++j) {
            if (board_state[i][j] == 1) continue; // Skip occupied cells

            if ((i + j) % 2 == 0) { // Cells with even sum of coordinates (e.g., 'white' squares)
                left_partition_count++;
                partition_id[i][j] = left_partition_count;
            } else { // Cells with odd sum of coordinates (e.g., 'black' squares)
                right_partition_count++;
                partition_id[i][j] = right_partition_count;
            }
        }
    }

    // Build the bipartite graph
    for (int r = 1; r <= n_board; ++r) {
        for (int c = 1; c <= n_board; ++c) {
            if (board_state[r][c] == 1) continue;

            if ((r + c) % 2 == 0) { // If it's a 'white' square (left partition)
                int u_idx = partition_id[r][c];
                for (int k = 0; k < 4; ++k) {
                    int nr = r + dx[k];
                    int nc = c + dy[k];

                    if (nr >= 1 && nr <= n_board && nc >= 1 && nc <= n_board && board_state[nr][nc] == 0) {
                        int v_idx = partition_id[nr][nc]; // Neighbor is a 'black' square (right partition)
                        adj[u_idx].push_back(v_idx);
                    }
                }
            }
        }
    }

    // Apply Hungarian algorithm
    int max_matches = 0;
    for (int i = 1; i <= left_partition_count; ++i) {
        // Reset visited status for each iteration using partition_id temporarily
        // A more robust approach would use a separate 'visited' array cleared each time
        for(int r = 1; r <= n_board; ++r) {
            for(int c = 1; c <= n_board; ++c) {
                if (board_state[r][c] == 0 && partition_id[r][c] != 0 && (r + c) % 2 == 0) {
                     partition_id[r][c] = 0; // Resetting 'visited' flags
                }
            }
        }
        // Need to handle the case where the node index `i` might not correspond directly to partition_id values if partition_id are not contiguous.
        // However, given the construction, partition_id for the left side is contiguous from 1 to left_partition_count.
        if (find_domino_match(i)) {
            max_matches++;
        }
    }

    std::cout << max_matches * 2 << std::endl; // Each match covers 2 cells
    return 0;
}

Ví dụ 3: Bài toán Tập Độc Lập Lớn Nhất

Cho một đồ thị hai phía, tìm số lượng đỉnh lớn nhất sao cho không có hai đỉnh nào trong tập đó có cạnh nối trực tiếp. Mối liên hệ với Khớp Nối: Trong một đồ thị hai phía, số lượng đỉnh của tập độc lập lớn nhất bằng tổng số đỉnh trừ đi số lượng cạnh của khớp nối lớn nhất. Điều này xuất phát từ định lý Dilworth và các kết quả liên quan đến đồ thị hai phía. Đầu vào:

• Dòng đầu tiên: n (tổng số đỉnh), m (số cạnh).
• m dòng tiếp theo: Cặp đỉnh x, y tạo thành cạnh. Đầu ra: Kích thước của tập độc lập lớn nhất. Dữ liệu mẫu:

4 3
1 2
1 4
3 4

Kết quả mẫu:

2

Ràng buộc: 2 ≤ n ≤ 1000, 0 ≤ m ≤ 10000.

Mã nguồn

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

const int MAX_VERTICES = 1000 + 10;
std::vector<int> undirected_adj[MAX_VERTICES]; // For coloring
std::vector<int> directed_adj[MAX_VERTICES]; // For matching (directed from partition 1 to partition 2)
int color[MAX_VERTICES]; // 0: uncolored, 1: partition 1, 2: partition 2
int partition_id[MAX_VERTICES]; // Stores the mapped ID within its partition
int match_partner[MAX_VERTICES]; // Stores the matched partner for nodes in partition 2
bool visited_round[MAX_VERTICES]; // Visited flag for the current DFS round of matching
int n_total, m_edges;
int partition1_count, partition2_count;

// DFS for coloring
void color_graph_dfs(int u) {
    for (int v : undirected_adj[u]) {
        if (color[v] == 0) {
            color[v] = 3 - color[u]; // Assign alternate color
            color_graph_dfs(v);
        }
    }
}

// DFS for finding augmenting paths in matching
bool find_augmenting_path(int u) {
    for (int v : directed_adj[u]) {
        if (!visited_round[v]) {
            visited_round[v] = true;
            if (match_partner[v] == 0 || find_augmenting_path(match_partner[v])) {
                match_partner[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d %d", &n_total, &m_edges);
    for (int i = 0; i < m_edges; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        undirected_adj[u].push_back(v);
        undirected_adj[v].push_back(u);
    }

    // Step 1: Color the graph to identify the two partitions
    for (int i = 1; i <= n_total; ++i) {
        if (color[i] == 0) {
            color[i] = 1; // Start with color 1
            color_graph_dfs(i);
        }
    }

    // Step 2: Assign contiguous IDs within each partition and build directed graph for matching
    partition1_count = 0;
    partition2_count = 0;
    for (int i = 1; i <= n_total; ++i) {
        if (color[i] == 1) {
            partition_id[i] = ++partition1_count;
        } else {
            partition_id[i] = ++partition2_count;
        }
    }

    for (int u = 1; u <= n_total; ++u) {
        if (color[u] == 1) { // If u is in partition 1
            for (int v : undirected_adj[u]) {
                if (color[v] == 2) { // If v is in partition 2
                    directed_adj[partition_id[u]].push_back(partition_id[v]);
                }
            }
        }
    }

    // Step 3: Find the maximum matching using Hungarian algorithm
    int max_matching = 0;
    for (int i = 1; i <= partition1_count; ++i) {
        memset(visited_round, 0, sizeof(visited_round)); // Reset visited flags for each iteration
        if (find_augmenting_path(i)) {
            max_matching++;
        }
    }

    // Step 4: Calculate the size of the maximum independent set
    // Max Independent Set = Total Vertices - Max Matching
    std::cout << n_total - max_matching << std::endl;

    return 0;
}

Ví dụ 4: Số Lượng Đường Đi Không Giao Nhau Ít Nhất

Cho một đồ thị có hướng không có chu trình (DAG). Tìm số lượng đường đi rời nhau (không chia sẻ đỉnh nào) ít nhất để phủ hết tất cả các đỉnh của đồ thị. Kỹ thuật: Bài toán này có thể được giải quyết bằng cách chuyển đổi thành bài toán tìm khớp nối lớn nhất trên đồ thị hai phía. Chúng ta áp dụng kỹ thuật "tách đỉnh" (vertex splitting): mỗi đỉnh v trong đồ thị ban đầu được tách thành hai đỉnh, v_in và v_out. v_in thuộc tập bên trái của đồ thị hai phía mới, và v_out thuộc tập bên phải. Một cạnh (u, v) trong DAG ban đầu sẽ tương ứng với một cạnh nối từ u_out sang v_in trong đồ thị hai phía. Kết quả cuối cùng là: Số đỉnh tối thiểu = Số đỉnh ban đầu - Kích thước khớp nối lớn nhất. Đầu vào:

• Dòng đầu tiên: n (số đỉnh), m (số cạnh).
• m dòng tiếp theo: Cặp đỉnh x, y tạo thành cạnh có hướng từ x đến y. Đầu ra: Số lượng đường đi ít nhất. Dữ liệu mẫu:

5 4
1 3
2 3
3 4
3 5

Kết quả mẫu:

3

Ràng buộc: 2 ≤ n ≤ 1000, 0 ≤ m ≤ 10000.

Mã nguồn

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

const int MAX_VERTICES = 1000 + 10;
std::vector<int> adj[MAX_VERTICES]; // Adjacency list for the DAG
int match_partner[MAX_VERTICES]; // Stores the matched partner for nodes in the right partition
bool visited_round[MAX_VERTICES]; // Visited flag for the current DFS round of matching
int num_vertices_dag, num_edges_dag;

// DFS to find augmenting paths for matching
bool find_match_path(int u) {
    // In this context, 'u' represents a node from the 'left' partition (representing v_out in the split-node concept)
    for (int v : adj[u]) {
        // 'v' represents a node from the 'right' partition (representing v_in in the split-node concept)
        if (!visited_round[v]) {
            visited_round[v] = true;
            // If v is unmatched, or its current match can find another match
            if (match_partner[v] == 0 || find_match_path(match_partner[v])) {
                match_partner[v] = u; // Match u (from left partition) with v (from right partition)
                return true;
            }
        }
    }
    return false; // Cannot find a match for u
}

int main() {
    scanf("%d %d", &num_vertices_dag, &num_edges_dag);
    for (int i = 0; i < num_edges_dag; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        // We are building a bipartite graph where:
        // Left partition nodes are indexed 1 to n (representing v_out)
        // Right partition nodes are indexed 1 to n (representing v_in)
        // An edge (u, v) in the DAG becomes an edge from u (left) to v (right)
        adj[u].push_back(v);
    }

    int max_matching = 0;
    // Iterate through each node acting as the source of potential paths (left partition)
    for (int i = 1; i <= num_vertices_dag; ++i) {
        memset(visited_round, 0, sizeof(visited_round)); // Reset visited flags for each starting node i
        if (find_match_path(i)) {
            max_matching++;
        }
    }

    // By Dilworth's Theorem for DAGs, the minimum number of paths to cover all vertices
    // is equal to the size of the maximum antichain. This is also related to the
    // maximum matching in a derived bipartite graph.
    // The number of paths = Total vertices - Maximum Matching Size
    std::cout << num_vertices_dag - max_matching << std::endl;

    return 0;
}