Ученая степень (теория графов)
- Степень вершины графа — число ребер, инцидентных этой вершине.
- Максимальная степень графа обозначается Δ(G), а минимальная — δ(G).
- В мультиграфе максимальная степень равна 5, а минимальная — 0.
- В обычном графе каждая вершина имеет одинаковую степень.
- Полный график (K
- n
- ) — особый вид правильного графа с максимально возможной степенью.
- В знаковом графе число положительных и отрицательных ребер связано с положительным и отрицательным градусом вершины.
- Лемма о рукопожатии утверждает, что число вершин с нечетной степенью четно в любом неориентированном графе.
- Последовательность степеней неориентированного графа является нерастущей последовательностью степеней его вершин.
- Последовательность степеней является инвариантом графа и может быть использована для идентификации графов.
- Задача о последовательности степеней заключается в нахождении графов с заданной нерастущей последовательностью натуральных чисел.
Полный текст статьи: