C++ Program: Check if Graph Construction is Possible from Degree Sequence (Graphic Sequence)

Graphic Sequence (Degree Sequence) คือลำดับของ Degree ของ Vertex ทั้งหมดใน Graph โจทย์: กำหนด Sequence ของจำนวนเต็มบวก สามารถสร้าง Simple Graph (No Loops, No Multiple Edges) ที่มี Degree Sequence ตรงกันได้หรือไม่?

Erdős–Gallai Theorem (Necessary & Sufficient Condition)

Sequence d₁ ≥ d₂ ≥ ... ≥ dₙ เป็น Graphic Sequence ก็ต่อเมื่อ:

1. Sum of Degrees เป็นเลขคู่ (Handshaking Lemma: Σdᵢ = 2|E|)
2. สำหรับทุก k = 1..n: Σᵢ₌₁ᵏ dᵢ ≤ k(k-1) + Σᵢ₌ₖ₊₁ⁿ min(dᵢ, k)

Havel-Hakimi Algorithm (Constructive)

1. Sort Sequence Descending
2. Remove First Element d
3. ลบ 1 จาก d ตัวถัดไป
4. ถ้ามีค่าติดลบ → Not Graphic
5. Repeat จนหมด หรือเหลือแต่ 0 → Graphic

โค้ด C++ (Both Methods)

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

// Method 1: Erdős–Gallai Theorem (Fast Check)
bool isGraphicErdosGallai(vector deg) {
    int n = deg.size();
    sort(deg.begin(), deg.end(), greater());
    
    // Check Handshaking Lemma
    long long sum = accumulate(deg.begin(), deg.end(), 0LL);
    if (sum % 2 != 0) return false;
    
    // Prefix sums for efficiency
    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 left = prefix[k];
        
        // Find first index > k where deg[i] <= k
        int idx = upper_bound(deg.begin() + k, deg.end(), k, greater()) - deg.begin();
        
        long long right = 1LL * k * (k - 1);
        right += 1LL * k * (idx - k);           // deg[i] > k for i in [k, idx)
        right += prefix[n] - prefix[idx];       // deg[i] ≤ k for i in [idx, n)
        
        if (left > right) return false;
    }
    return true;
}

// Method 2: Havel-Hakimi Algorithm (Constructive)
bool isGraphicHavelHakimi(vector deg) {
    while (true) {
        sort(deg.begin(), deg.end(), greater());
        
        // Remove zeros
        while (!deg.empty() && deg.back() == 0) deg.pop_back();
        if (deg.empty()) return true;
        
        int d = deg[0];
        deg.erase(deg.begin());
        
        if (d > deg.size()) return false; // Not enough vertices to connect
        
        for (int i = 0; i < d; i++) {
            deg[i]--;
            if (deg[i] < 0) return false;
        }
    }
}

// Method 3: Construct Actual Graph (Havel-Hakimi with Edge Tracking)
vector> constructGraph(vector deg) {
    int n = deg.size();
    vector> edges;
    vector> vertices; // {degree, vertex_id}
    
    for (int i = 0; i < n; i++) vertices.push_back({deg[i], i});
    
    while (true) {
        sort(vertices.begin(), vertices.end(), 
             [](auto& a, auto& b) { return a.first > b.first; });
        
        while (!vertices.empty() && vertices.back().first == 0)
            vertices.pop_back();
        if (vertices.empty()) return edges;
        
        auto [d, u] = vertices[0];
        vertices.erase(vertices.begin());
        
        if (d > vertices.size()) return {}; // Impossible
        
        for (int i = 0; i < d; i++) {
            vertices[i].first--;
            if (vertices[i].first < 0) return {};
            edges.push_back({u, vertices[i].second});
        }
    }
}

int main() {
    // Test Cases
    vector> testCases = {
        {3, 3, 3, 3},        // K4 - Graphic
        {3, 3, 2, 2, 2},     // Graphic
        {4, 3, 2, 1},        // Not Graphic (Sum odd)
        {5, 5, 5, 5, 5, 5},  // Not Graphic (d > n-1)
        {3, 3, 3, 1},        // Not Graphic
        {2, 2, 2, 2, 2, 2},  // C6 - Graphic
        {7, 6, 5, 4, 3, 2, 1} // Not Graphic
    };
    
    cout << "Sequence\t\tEG\tHH\tConstructible\n";
    for (auto& seq : testCases) {
        auto seq1 = seq, seq2 = seq, seq3 = seq;
        bool eg = isGraphicErdosGallai(seq1);
        bool hh = isGraphicHavelHakimi(seq2);
        auto edges = constructGraph(seq3);
        bool constructible = !edges.empty() || (seq3.size() && all_of(seq3.begin(), seq3.end(), [](int d){ return d==0; }));
        
        cout << "[";
        for (size_t i = 0; i < seq.size(); i++) {
            cout << seq[i] << (i+1 input;
    int x;
    while (cin >> x && x != -1) input.push_back(x);
    
    if (!input.empty()) {
        cout << "Erdos-Gallai: " << (isGraphicErdosGallai(input) ? "GRAPHIC" : "NOT GRAPHIC") << "\n";
        cout << "Havel-Hakimi: " << (isGraphicHavelHakimi(input) ? "GRAPHIC" : "NOT GRAPHIC") << "\n";
        
        auto edges = constructGraph(input);
        if (!edges.empty() || (input.size() && all_of(input.begin(), input.end(), [](int d){ return d==0; }))) {
            cout << "Constructed Graph Edges:\n";
            for (auto [u, v] : edges) cout << "  " << u << " - " << v << "\n";
        } else {
            cout << "Cannot construct graph\n";
        }
    }
    
    return 0;
}

ผลลัพธ์

Sequence            EG  HH  Constructible
[3,3,3,3]           Y   Y   Y
[3,3,2,2,2]         Y   Y   Y
[4,3,2,1]           N   N   N
[5,5,5,5,5,5]       N   N   N
[3,3,3,1]           N   N   N
[2,2,2,2,2,2]       Y   Y   Y
[7,6,5,4,3,2,1]     N   N   N

Comparison

Note on Original Article

โค้ดต้นฉบับสร้าง Random Graph แล้วแสดง Degree Sequence ซึ่งเป็น การทำย้อนกลับ (Graph → Degree Sequence) ไม่ใช่การตรวจสอบว่า Degree Sequence ใดๆ เป็น Graphic ได้หรือไม่ โค้ดข้างต้นแก้ไขให้ตรงกับโจทย์จริง

Applications

• Network Topology Validation
• Social Network Analysis (Degree Distribution)
• Molecular Graphs (Chemical Valency)
• Random Graph Generation (Configuration Model)
• Graph Realization Problems

C++ Program: Detect Cycle in Directed Graph using Topological Sort (Kahn's Algorithm)

C++ Program: Print Diamond Shape Pattern