Bậc (lý Thuyết đồ Thị) – Wikipedia Tiếng Việt

Trong Lý thuyết đồ thị, bậc của một đỉnh v là số cạnh liên thuộc với v (trong đó, khuyên được tính hai lần). Bậc của v được ký hiệu là deg ⁡ ( v ) {\displaystyle \deg(v)} .

Trong một đồ thị có hướng, bậc trong của đỉnh v là số cung kết thúc tại v, còn bậc ngoài là số cung xuất phát từ v. Bậc trong và bậc ngoài của v được ký hiệu là deg − ⁡ ( v ) {\displaystyle \deg ^{-}(v)} và deg + ⁡ ( v ) {\displaystyle \deg ^{+}(v)} . Do đó, deg ⁡ ( v ) = deg + ⁡ ( v ) + deg − ⁡ ( v ) {\displaystyle \deg(v)=\deg ^{+}(v)+\deg ^{-}(v)} .

Đỉnh với deg ⁡ ( v ) = 0 {\displaystyle \deg(v)=0} được gọi là đỉnh cô lập. Đỉnh có deg ⁡ ( v ) = 1 {\displaystyle \deg(v)=1} được gọi là lá. Nếu mỗi đỉnh của đồ thị đều có bậc bằng nhau và bằng k thì đồ thị được gọi là đồ thị chính quy bậc k và đồ thị được coi là có bậc bằng k.

Đỉnh có deg + ⁡ ( v ) = 0 {\displaystyle \deg ^{+}(v)=0} được gọi là đỉnh phát, đỉnh có deg − ⁡ ( v ) = 0 {\displaystyle \deg ^{-}(v)=0} là đỉnh thu.

Một số định lý

Cho đồ thị G=(V,E),

∑ v ∈ V deg ⁡ ( v ) = 2 | E | , {\displaystyle \sum _{v\in V}\deg(v)=2|E|,}

Do mỗi cạnh liên thuộc với hai đỉnh nên số đỉnh bậc lẻ trong đồ thị là số chẵn.

Tham khảo