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 (d1, d2,..., dn), trong đó di (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 = (d1 ≤ d2 ≤... ≤ dn) và D' = (d'1 ≤ d'2 ≤... ≤ d'n) thoả mãn:

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

Thể loại:Lý thuyết đồ thị