Степень вершины (теория графов)
Материал из Википедии — свободной encyclopedia
Степень (валентность) вершины графа — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды.[1]
Степень вершины обычно обозначается как или . Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.