Bậc (lý thuyết đồ thị)

Bài này viết về thuật ngữ "bậc" dùng trong lý thuyết đồ thị. Mời xem các bài bậc (toán học) hoặc bậc để đọc về các nghĩa khác.

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à ${\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à ${\displaystyle \deg ^{-}(v)}$ và ${\displaystyle \deg ^{+}(v)}$. Do đó, ${\displaystyle \deg(v)=\deg ^{+}(v)+\deg ^{-}(v)}$.

Đỉnh với ${\displaystyle \deg(v)=0}$ được gọi là đỉnh cô lập. Đỉnh có ${\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ó ${\displaystyle \deg ^{+}(v)=0}$ được gọi là đỉnh phát, đỉnh có ${\displaystyle \deg ^{-}(v)=0}$ là đỉnh thu.

Một số định lý

Cho đồ thị G=(V,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