Đây là một bài giới thiệu lí thuyết, cài đặt cũng nhẹ nhàng đơn giản.

Bạn có thể tìm hiểu 2 link sau :

https://en.wikipedia.org/wiki/Graph_realization_problem

https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem

Thuật toán tham

Sắp giảm dần dãy \(d\), tức \(d_1 \geq d_2 \geq d_3 \geq ... \geq d_k\)

Tại mỗi thời điểm, ta lấy đỉnh có bậc lớn nhất và nối nó vào những đỉnh có bậc lớn nhất tiếp theo. Như vậy sau mỗi bước, đảm bảo luôn có ít nhất một đỉnh bị giảm bậc xuống \(0\), vì thế độ phức tạp thời gian của thuật toán là \(O(n) * T(n)\) trong đó \(T(n)\) chính là số phép tính bạn thực hiện để mô phỏng thao tác trên. Dễ cài được \(T(n) = n*log_2(n)\). Tuy nhiên ở đây có cách cài khá khéo, sử dụng đếm phân phối, có thể mô phỏng thao tác trên trong \(T(n) = n\).

Có một cách cài cho ra thời gian tốt hơn : \(O(n * log_2(n))\), nhưng khó cài hơn nhiều : Dùng segment tree cải tiến, mô phỏng thuật toán tham? (lazy update).

Bất đẳng thức Edors - Gallai

Dãy bậc \(d\) đã cho có thể là dãy bậc của một đồ thị đơn, nếu :

Với mọi \(k\),
\(d_1 + d_2 + ... + d_k \leq k(k - 1) + min(k, d_{k+1}) + min(k, d_{k+2}) + ....\)

Giải thích công thức :

Vế trái \(d_1 + d_2 + ... + d_k\) : Số lượng cạnh cần để giảm bậc của \(k\) đỉnh bậc lớn nhất

Vế phải : Số lượng cạnh tối đa có thể nối tới \(k\) đỉnh này

• \(k * (k - 1)\) : Mỗi đỉnh trong \(k\) đỉnh có thể nối với \(k - 1\) đỉnh còn lại và giảm bậc đi \(1\), trong TH đồ thị đầy đủ thì giảm được tối đa là \(k(k - 1)\) bậc
• \(\sum(min(k, d_{i}))\) : Mỗi đỉnh bên ngoài chỉ có thể được nối với nhiều nhất là \(k\) đỉnh bên trong, nhưng cũng không quá bậc của chính nó.