Đồ thị hai phía (Bipartite Graph)

Khái niệm

Đồ thị hai phía (Bipartite Graph) là đồ thị mà tập đỉnh có thể chia thành hai nhóm sao cho mọi cạnh đều nối một đỉnh nhóm này với một đỉnh nhóm kia — không có cạnh nào nối hai đỉnh cùng nhóm.

Tính chất: Đồ thị là hai phía khi và chỉ khi nó không chứa chu trình lẻ (chu trình có số cạnh lẻ).

Ứng dụng thực tế:

Phân công công việc: nhóm công nhân ↔ nhóm công việc
Khớp cặp (matching): sinh viên ↔ trường đại học
Mô hình hoá quan hệ: người dùng ↔ sản phẩm (trong hệ thống gợi ý)

graph LR; subgraph Nhóm A A1((1)) A2((2)) A3((3)) end subgraph Nhóm B B4((4)) B5((5)) B6((6)) end A1 --- B4; A1 --- B5; A2 --- B4; A2 --- B6; A3 --- B5; A3 --- B6;

Kiểm tra đồ thị hai phía bằng BFS (2-Tô màu)

Gán màu 0 / 1 xen kẽ cho từng đỉnh khi duyệt BFS. Nếu hai đỉnh kề nhau cùng màu → không phải hai phía.

from collections import defaultdict, deque

def kiem_tra_hai_phia(n, canh):
    """
    Kiểm tra đồ thị vô hướng có phải hai phía không.
    Trả về (la_hai_phia, mang_mau) — mang_mau[v] = 0 hoặc 1.
    """
    graph = defaultdict(list)
    for u, v in canh:
        graph[u].append(v)
        graph[v].append(u)

    mau = [-1] * n    # -1: chưa tô màu

    for start in range(n):
        if mau[start] != -1:
            continue
        queue     = deque([start])
        mau[start] = 0

        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if mau[v] == -1:
                    mau[v] = 1 - mau[u]   # Tô màu ngược
                    queue.append(v)
                elif mau[v] == mau[u]:     # Cùng màu → không hai phía
                    return False, []

    return True, mau


# Đồ thị hai phía: đường đi 0-1-2-3-4 (không có chu trình lẻ)
canh1 = [(0,1),(1,2),(2,3),(3,4)]
la_hp, mau = kiem_tra_hai_phia(5, canh1)
print(f"Hai phía: {la_hp}, Màu: {mau}")   # True, [0,1,0,1,0]

# Đồ thị có chu trình lẻ: tam giác 0-1-2-0
canh2 = [(0,1),(1,2),(2,0)]
la_hp, _ = kiem_tra_hai_phia(3, canh2)
print(f"Hai phía: {la_hp}")               # False

Kiểm tra bằng DFS

from collections import defaultdict

def kiem_tra_hai_phia_dfs(n, canh):
    """Kiểm tra bằng DFS — cách tiếp cận đệ quy."""
    graph = defaultdict(list)
    for u, v in canh:
        graph[u].append(v)
        graph[v].append(u)

    mau = [-1] * n

    def dfs(u, c):
        mau[u] = c
        for v in graph[u]:
            if mau[v] == -1:
                if not dfs(v, 1 - c):
                    return False
            elif mau[v] == mau[u]:
                return False
        return True

    for i in range(n):
        if mau[i] == -1:
            if not dfs(i, 0):
                return False, []
    return True, mau

# Kiểm tra lưới 3x3 (rõ ràng là hai phía theo màu bàn cờ)
canh = []
for r in range(3):
    for c in range(3):
        if c + 1 < 3:
            canh.append((r*3+c, r*3+c+1))
        if r + 1 < 3:
            canh.append((r*3+c, (r+1)*3+c))
la_hp, mau = kiem_tra_hai_phia_dfs(9, canh)
print(f"Lưới 3x3 là hai phía: {la_hp}")   # True

Bài tập luyện tập

Dễ — Tô màu đồ thị hai phía

from collections import defaultdict, deque

def to_mau_hai_phia(n, canh):
    """
    Tô màu đồ thị hai phía bằng đúng 2 màu.
    Trả về dict {0: [các đỉnh nhóm 0], 1: [các đỉnh nhóm 1]}
    hoặc None nếu không phải hai phía.
    """
    graph = defaultdict(list)
    for u, v in canh:
        graph[u].append(v)
        graph[v].append(u)
    mau = [-1] * n
    for start in range(n):
        if mau[start] != -1:
            continue
        q = deque([start])
        mau[start] = 0
        while q:
            u = q.popleft()
            for v in graph[u]:
                if mau[v] == -1:
                    mau[v] = 1 - mau[u]
                    q.append(v)
                elif mau[v] == mau[u]:
                    return None
    nhom = {0: [], 1: []}
    for i, c in enumerate(mau):
        if c != -1:
            nhom[c].append(i)
    return nhom

# Phân công: người 0,1,2 và công việc 3,4,5
canh = [(0,3),(0,4),(1,3),(1,5),(2,4),(2,5)]
nhom = to_mau_hai_phia(6, canh)
print("Nhóm người:", nhom[0])    # [0, 1, 2]
print("Nhóm việc:",  nhom[1])    # [3, 4, 5]

Trung bình — Khớp cặp tối đa (Maximum Bipartite Matching)

from collections import defaultdict

def khop_cap_toi_da(n_trai, n_phai, canh):
    """
    Tìm khớp cặp tối đa trong đồ thị hai phía.
    Thuật toán Augmenting Path (Hungarian cơ bản).

    n_trai: số đỉnh nhóm trái (0..n_trai-1)
    n_phai: số đỉnh nhóm phải (0..n_phai-1)
    canh  : [(u, v)] — cạnh từ u (trái) đến v (phải)
    """
    graph = defaultdict(list)
    for u, v in canh:
        graph[u].append(v)

    khop_phai = [-1] * n_phai    # khop_phai[v] = u đang được ghép với v

    def dfs_augment(u, tham):
        for v in graph[u]:
            if tham[v]:
                continue
            tham[v] = True
            if khop_phai[v] == -1 or dfs_augment(khop_phai[v], tham):
                khop_phai[v] = u
                return True
        return False

    count = 0
    for u in range(n_trai):
        tham = [False] * n_phai
        if dfs_augment(u, tham):
            count += 1

    khop = [(khop_phai[v], v) for v in range(n_phai) if khop_phai[v] != -1]
    return count, khop

# 3 sinh viên, 3 trường
# sv0→tr0,tr1; sv1→tr1,tr2; sv2→tr0,tr2
canh = [(0,0),(0,1),(1,1),(1,2),(2,0),(2,2)]
cnt, pairs = khop_cap_toi_da(3, 3, canh)
print(f"Số cặp khớp tối đa: {cnt}")       # 3
for u, v in pairs:
    print(f"  sv{u} → tr{v}")

Khó — Bao phủ đỉnh tối thiểu (König’s Theorem)

from collections import defaultdict, deque

def bao_phu_dinh_toi_thieu(n_trai, n_phai, canh):
    """
    Tìm tập đỉnh bao phủ tối thiểu trong đồ thị hai phía.
    Theo định lý König: |bao phủ tối thiểu| = |khớp cặp tối đa|.

    Thuật toán:
    1. Tìm khớp cặp tối đa
    2. Tìm tập đỉnh độc lập tối đa bằng BFS từ đỉnh chưa được khớp
    3. Bổ sung bao phủ = V - tập độc lập
    """
    graph_trai = defaultdict(list)
    graph_phai = defaultdict(list)
    for u, v in canh:
        graph_trai[u].append(v)
        graph_phai[v].append(u)

    khop_phai = [-1] * n_phai
    khop_trai = [-1] * n_trai

    def dfs(u, tham):
        for v in graph_trai[u]:
            if tham[v]: continue
            tham[v] = True
            if khop_phai[v]==-1 or dfs(khop_phai[v], tham):
                khop_phai[v]=u; khop_trai[u]=v; return True
        return False

    for u in range(n_trai):
        dfs(u, [False]*n_phai)

    # BFS từ đỉnh trái chưa được khớp
    tham_trai = [False]*n_trai
    tham_phai = [False]*n_phai
    q = deque(u for u in range(n_trai) if khop_trai[u]==-1)
    for u in q: tham_trai[u]=True

    while q:
        u = q.popleft()
        for v in graph_trai[u]:
            if not tham_phai[v]:
                tham_phai[v]=True
                w=khop_phai[v]
                if w!=-1 and not tham_trai[w]:
                    tham_trai[w]=True; q.append(w)

    # Bao phủ: đỉnh trái KHÔNG tham, đỉnh phải CÓ tham
    bao_phu_T = [u for u in range(n_trai) if not tham_trai[u]]
    bao_phu_P = [v for v in range(n_phai) if tham_phai[v]]
    return bao_phu_T, bao_phu_P

canh = [(0,0),(0,1),(1,1),(1,2),(2,0),(2,2)]
trai, phai = bao_phu_dinh_toi_thieu(3, 3, canh)
print("Đỉnh bao phủ (trái):", trai)
print("Đỉnh bao phủ (phải):", phai)
print("Tổng:", len(trai)+len(phai))   # = số cặp khớp tối đa = 3

Kết luận

Đồ thị hai phía là nền tảng của nhiều bài toán phân công và kết cặp thực tế. Kiểm tra hai phía bằng BFS/DFS tô màu là kỹ thuật cần nắm chắc. Chúc mừng bạn đã hoàn thành phần Lý thuyết đồ thị — hãy tiếp tục thú vị với các chủ đề khác trong mục Dev!

Trong series này: