Chuỗi bậc

Chuỗi bậc trong lý thuyết đồ thị là danh sách bậc của các đỉnh thuộc đồ thị. Với đồ thị G và n đỉnh, chuỗi bậc của đồ thị là dãy (d₁, d₂,..., d_n), trong đó d_i (i=1, 2,..., n) là bậc của đỉnh i thuộc đồ thị G.

Hai đồ thị đẳng cấu có chuỗi bậc giống nhau; ngược lại hai đồ thị có chuỗi bậc giống nhau không nhất thiết là hai đồ thị đẳng cấu.

Định lý về chuỗi bậc

Với mọi dãy số D = (d₁ ≤ d₂ ≤... ≤ d_n) và D' = (d'₁ ≤ d'₂ ≤... ≤ d'_n) thoả mãn:

${d_i}^{\prime }=\{\begin{array}{cc}{d}_i,& i<n-d_n\\ d_i-1,& i\ge n-d_n\end{array}$

ta có D là chuỗi bậc của đồ thị, khi D' cũng là chuỗi bậc của đồ thị.

Nguồn tham khảo

Degree Sequence (Trang viết bằng tiếng Anh).