✨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à $\backslash 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à $\backslash deg^-(v)$ và $\backslash deg^+(v)$. Do đó, $\backslash deg(v)\; =\; \backslash deg^+(v)\; +\; \backslash deg^-(v)$.

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

Một số định lý

Cho đồ thị G=(V,E), :$\backslash sum\_\{v\; \backslash in\; V\}\; \backslash 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.