Степени вершин графа

Степенью вершины графа называется число инцидентных ей ребер, т. е. число вершин в ее окружении. Будем обозначать степень вершины через (или). Тем самым.

.

Максимальная и минимальная степени вершин графа обозначаются символами и соответственно:

.

Список степеней вершин графа называется его степенной последовательностью. Порядок членов в этой последовательности роли не играет.

Вершина степени 0 называется изолированной, вершина степени 1 — концевой (или висячей). Ребро, инцидентное концевой вершине, также называется концевым.

Рассмотрим сумму степеней всех вершин графа. Каждое ребро вносит в эту сумму 2, поэтому верно.

Утверждение 5.1 («лемма о рукопожатиях»). Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер:

Возможная интерпретация этой леммы такова: поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук четно (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала).

Следствие 5.2. В любом графе число вершин нечетной степени четно.

Понятие степени вершины и лемма о рукопожатиях cохраняются для мультии псевдографов. При этом каждая петля вносит в степень соответствующей вершины двойку.

Граф называется регулярным (или однородным), если степени всех его вершин равны; степенью регулярного графа называется степень его вершин. Степень регулярного графа обозначается через .

Последовательность целых неотрицательных чисел ниже называется —последовательностью и обозначается одной буквой. Произвольнаяпоследовательность называется графической, если существует граф, степенная последовательность которого совпадает с. Этот граф называется реализацией последовательности. Очевидно, что порядок членов в графическойпоследовательности несуществен, а каждый ее член удовлетворяет неравенствам. Часто удобно эти последовательности считать невозрастаюшими. Согласно лемме о рукопожатиях сумма всех членов графической последовательности является четным числом.

Назовемпоследовательность правильной, если выполняются два следующих условия:

1) ,.

2) — четное число.

Без ограничения общности графическую последовательность можно всегда считать правильной.

Рассмотрим последовательность. Существуют ровно пять графов (не обязательно связных), являющихся реализациями последовательности. Они имеют следующие компоненты: 1), и 2), и 3) и 4) и 5) и .

В общем случае графическая последовательность имеет много реализаций и их число определить сложно.

Итак, графическую последовательность всегда можно считать правильной. Кроме того, в ней должны быть равные члены (если длина ее), поскольку не существует графа, степени всех вершин которого попарно различны (почему Однако указанные условия отнюдь не являются достаточными для графичности последовательности. Очевидно, например, что последовательность не является графической, хотя и удовлетворяет упомянутым условиям. Известно несколько критериев графичности последовательности. Мы укажем один из них.

Теорема 5.3 (П. Эрдёш, Т. Галлаи, 1960 г.). Правильнаяпоследовательность является графической тогда и только тогда, когда для каждого верно неравенство.

При тестировании последовательности с помощью этого критерия нет необходимости проверять все неравенств. Обозначим. Тогда верно.

Утверждение 5.4. Если правильнаяпоследовательность удовлетворяет каждому из неравенств критерия Эрдеша-Галлаи при, то она удовлетворяет и каждому из оставшихся неравенств.