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:

${\displaystyle d_{i}'={\begin{cases}d_{i},&i<n-d_{n}\\d_{i}-1,&i\geq n-d_{n}\;\end{cases}}}$

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).

Tham khảo