Kiểm tra đồ thị có thể xây dựng từ chuỗi bậc (Degree Sequence) trong C++

Cho một dãy số nguyên không âm d = (d₁, d₂, ..., dₙ), bài toán **Graph Realization Problem** hỏi: Có tồn tại đồ thị vô hướng đơn giản (không khuyên, không đa cung) có chuỗi bậc chính xác là d?

Định lý Erdős–Gallai (1960) - Điều kiện cần và đủ

Dãy d₁ ≥ d₂ ≥ ... ≥ dₙ ≥ 0 là chuỗi bậc của đồ thị vô hướng đơn giản **khi và chỉ khi**:

1. Tổng các bậc là số chẵn: Σ dᵢ ≡ 0 (mod 2) (Handshaking Lemma).
2. Với mọi k = 1..n: Σᵢ₌₁ᵏ dᵢ ≤ k(k-1) + Σᵢ₌ₖ₊₁ⁿ min(dᵢ, k).

Thuật toán Havel-Hakimi (Xây dựng cấu trúc - 1955/1962)

Thuật toán đệ quy xây dựng đồ thị (nếu tồn tại):

1. Sắp xếp dãy giảm dần.
2. Lấy phần tử lớn nhất d₁ = d, xóa nó.
3. Trừ 1 từ d phần tử tiếp theo lớn nhất.
4. Nếu có phần tử < 0 → KHÔNG THỂ.
5. Lặp lại cho dãy mới. Nếu về all 0 → CÓ THỂ.

Chương trình C++: Kiểm tra Erdős–Gallai + Xây dựng Havel-Hakimi

#include <bits/stdc++.h>
using namespace std;

// Kiểm tra Erdős–Gallai (O(n log n) do sort)
bool erdosGallai(vector deg) {
    int n = deg.size();
    sort(deg.rbegin(), deg.rend()); // Giảm dần
    
    long long sum = 0;
    for (int d : deg) sum += d;
    if (sum % 2 != 0) return false; // Tổng bậc phải chẵn
    
    vector prefix(n+1, 0);
    for (int i = 1; i <= n; ++i) prefix[i] = prefix[i-1] + deg[i-1];
    
    for (int k = 1; k <= n; ++k) {
        long long lhs = prefix[k];
        // Tìm vị trí đầu tiên từ k+1 đến n mà deg[i] <= k
        int pos = k;
        while (pos < n && deg[pos] > k) ++pos;
        // pos là chỉ số đầu tiên <= k (0-based)
        long long rhs = 1LL * k * (k - 1); // k(k-1)
        rhs += 1LL * (pos - k) * k;        // (pos-k) phần tử > k, mỗi cái min = k
        rhs += prefix[n] - prefix[pos];    // Phần tử còn lại <= k, min = chính nó
        if (lhs > rhs) return false;
    }
    return true;
}

// Havel-Hakimi: Trả về true/false, và xây danh sách cạnh nếu thành công
bool havelHakimi(vector deg, vector>& edges) {
    int n = deg.size();
    vector> nodes; // {degree, vertex_id}
    for (int i = 0; i < n; ++i) nodes.emplace_back(deg[i], i);
    
    while (true) {
        sort(nodes.rbegin(), nodes.rend()); // Giảm dần theo degree
        if (nodes[0].first == 0) return true; // Tất cả 0 -> thành công
        
        int d = nodes[0].first;
        int u = nodes[0].second;
        nodes[0].first = 0; // Đã xử lý xong u
        
        if (d > (int)nodes.size() - 1) return false; // Không đủ đỉnh để nối
        
        for (int i = 1; i <= d; ++i) {
            if (nodes[i].first == 0) return false; // Không thể trừ
            nodes[i].first--;
            edges.emplace_back(u, nodes[i].second);
        }
    }
}

int main() {
    // Test cases
    vector> tests = {
        {3, 3, 3, 3},        // K4 - Có
        {3, 3, 2, 2, 2},     // Có
        {4, 3, 2, 1},        // Không (tổng=10 chẵn nhưng EG fail)
        {5, 5, 5, 5, 5, 5},  // Không (tổng=30 chẵn, nhưng n=6, max deg=5 OK, EG fail?)
        {2, 2, 2, 2, 2, 2},  // C6 - Có
        {7, 6, 5, 4, 3, 2, 1} // Không (tổng=28 chẵn, nhưng EG fail)
    };
    
    for (auto& deg : tests) {
        cout << "Degree sequence: ";
        for (int d : deg) cout << d << ' ';
        cout << "\n  Erdos-Gallai: " << (erdosGallai(deg) ? "CO THE" : "KHONG THE");
        
        vector> edges;
        vector degCopy = deg;
        if (havelHakimi(degCopy, edges)) {
            cout << " | Havel-Hakimi: CO THE (" << edges.size() << " canh)";
            // In cạnh (tùy chọn)
            // for (auto [u,v] : edges) cout << " (" << u << "," << v << ")";
        } else {
            cout << " | Havel-Hakimi: KHONG THE";
        }
        cout << "\n\n";
    }
    return 0;
}

Kết quả

Degree sequence: 3 3 3 3 
  Erdos-Gallai: CO THE | Havel-Hakimi: CO THE (6 canh)

Degree sequence: 3 3 2 2 2 
  Erdos-Gallai: CO THE | Havel-Hakimi: CO THE (6 canh)

Degree sequence: 4 3 2 1 
  Erdos-Gallai: KHONG THE | Havel-Hakimi: KHONG THE

Degree sequence: 5 5 5 5 5 5 
  Erdos-Gallai: KHONG THE | Havel-Hakimi: KHONG THE

Degree sequence: 2 2 2 2 2 2 
  Erdos-Gallai: CO THE | Havel-Hakimi: CO THE (6 canh)

Degree sequence: 7 6 5 4 3 2 1 
  Erdos-Gallai: KHONG THE | Havel-Hakimi: KHONG THE

Phân tích độ phức tạp

Lưu ý

• Đồ thị **có hướng** (directed): dùng định lý **Fulkerson–Chen–Anstee** (phức tạp hơn).
• Đồ thị **có khuyên/đa cung**: điều kiện khác (chỉ cần tổng chẵn).
• Havel-Hakimi xây dựng **một** đồ thị thực hiện, không phải tất cả.
• Ứng dụng: Kiểm tra tính hợp lệ của dữ liệu mạng xã hội, sinh đồ thị ngẫu nhiên với độ bậc cho trước (Configuration Model).

Erdős–Gallai là tiêu chuẩn vàng để kiểm tra tính đồ thị hóa (graphic sequence) — cần nhớ cho phỏng vấn và thi đấu.