Основные числовые характеристики и матрицы графа.
Степени вершин графа
Степенью вершины v графа G называется число инцидентных ей рёбер, т.е. число рёбер, выходящих из данной вершины. (В случае псевдографов каждая петля добавляет 2 в степень вершины). Обозначается степень вершины v графа G: degGv или просто deg v, если ясно, о каком графе G идет речь.
Вершина степени 0 называется изолированной. Вершина степени 1
называется концевой (или висячей). Ребро, инцидентное концевой вершине также
называется концевым.
Вершина v графа G, смежная со всеми другими вершинами G, называется доминирующей. Её степень degGv очевидно равна |G| --1.
Граф G называется регулярным (или, по-другому, однородным), если степени всех его вершин равны. Эта общая степень всех вершин регулярного графа G называется степенью регулярного графа G и обозначается deg G.
Последовательность степеней вершин графа G, записанная в каком либо порядке называется степенной последовательностью графа G. Например, граф на рисунке справа имеет степенную последовательность (3, 3, 1, 0, 1, 2).
Понятно, что изоморфные графы имеют одинаковые (с точностью до порядка
следования элементов) степенные последовательности. Однако, из этого совпадения
степенных последовательностей двух графов ещё не следует их изоморфность.
На следующих двух рисунках изображены два неизоморфных регулярных графа степени
2.
Таким образом, степенная последовательность не определяет
граф полностью и не может
G
служить способом его задания.
Степенная последовательность не может быть произвольным набором чисел, а обладает определёнными свойствами.
Лемма 1 ("о рукопожатиях"). Сумма степеней всех вершин графа G есть число чётное, ровно в два раза большее числа рёбер графа G, т.е.
 |
Доказательство: Действительно, подсчитаем количество рёбер графа G, просматривая поочередно все вершины графа G и считая рёбра выходящие из этих вершин. Так как из каждой вершины v выходит degGv рёбер, то мы получим сумму:
Но при этом каждое ребро будет учтено 2 раза: один раз, когда рассматривался один его конец, другой раз, когда -- второй. Таким образом, лемма верна.
Из леммы 1 вытекает
Следствие. В любом графе число вершин нечётной степени является чётным.
Доказательство. В самом деле, иначе, если бы сумма целых чисел содержала нечётное число нечетных слагаемых, то она, очевидно, была бы нечётной, что противоречит лемме о рукопожатиях.
В ориентированных графах для каждой вершины v дополнительно рассматривается также полустепень исхода и полустепень захода. Полустепенью исхода вершины v называется число дуг графа G, для которых v является началом, а полустепенью захода – число дуг, для которых v является концом. Обозначаются полустепени захода и исхода графа G соответственно deg-v и deg+v. При этом полная степень degv = deg-v+ deg+v. Поскольку каждая дуга имеет ровно одно начало и один конец, то справедлива
 |
Лемма 2. Сумма полустепеней исхода всех вершин графа G равна сумме полустепеней захода, т.е.