Смежность, инцидентность, степени

Если в графе имеется ребро , то говорят, что вершины a и b смежны в этом графе, ребро e инцидентно каждой из вершин a, b, а каждая из них инцидентна этому ребру.

Множество всех вершин графа, смежных с данной вершиной а, называется окрестностью этой вершины и обозначается через . Число этих вершин называется степенью вершины a и обозначается через .

Если сложить степени всех вершин некоторого графа, то каждое ребро внесет в эту сумму вклад, равный 2, поэтому справедливо следующее утверждение.

Теорема 2. .

Это равенство известно как «лемма о рукопожатиях». Из него следует, что число вершин нечетной степени в любом графе четно.

Вершину степени 0 называют изолированной. Граф называют регулярным степени d, если степень каждой его вершины равна d.

Набор степеней графа – это последовательность степеней его вершин, выписанных в неубывающем порядке.

Подграф

Граф называется подграфом графа G, если , . Всякий подграф может быть получен из графа удалением некоторых вершин и ребер. На рисунке 4 изображены граф G и его подграфы .

G

Рис. 4

Подграф графа G называется остовным, если . Остовный подграф может быть получен из графа удалением некоторых ребер, вершины же остаются в неприкосновенности. На рисунке 4 – остовный подграф графа G, а и не являются остовными подграфами.

Другая важная разновидность подграфов – порожденные подграфы. Пусть задан граф и в нем выбрано множество вершин . Рассмотрим подграф , где состоит из всех тех ребер графа G, у которых оба конца принадлежат U. Говорят, что этот подграф порожден множеством вершин U. Он обозначается через . Порожденный подграф может быть получен из графа удалением «лишних» вершин, т.е. вершин, не принадлежащих U, причем при удалении вершины удаляются и все инцидентные ей ребра.

На рисунке 4 – подграф графа G, порожденный множеством вершин {1,2,4,5}, т.е. , а подграф не является ни остовным, ни порожденным.

Некоторые специальные графы

Рассмотрим некоторые особенно часто встречающиеся графы.

Пустой граф – граф, не содержащий ни одного ребра. Пустой граф с множеством вершин {1,2,...,n} обозначается через .

Полный граф – граф, в котором каждые две вершины смежны. Полный граф с множеством вершин {1,2,...,n} обозначается через . Граф , в частности, имеет одну вершину и ни одного ребра.

Цепь (путь) – граф с множеством вершин {1,2,...,n} и множеством ребер .

Цикл – граф, который получается из добавлением ребра .

Дополнительный граф

Дополнительным графом (или дополнением) к обыкновенному графу G называется граф , у которого множество вершин то же, что у G, и две различные вершины смежны тогда и только тогда, когда они не смежны в G. Например, . Другой пример показан на рисунке 5. Очевидно, всегда .

G

Рис. 5

Изоморфизм

На рисунке 6 изображены два графа с одним и тем же множеством вершин . При внимательном рассмотрении можно обнаружить, что это разные графы – в левом имеется ребро , в правом же такого нет. В то же

Рис. 6

время, если не обращать внимания на наименования вершин, то эти графы явно

одинаково устроены: каждый из них – цикл из четырех вершин. Во многих случаях при исследовании строения графов имена или номера вершин не играют роли и такие графы, один из которых получается из другого переименованием вершин, можно считать одинаковыми. Для того, чтобы это можно было делать «на законном основании», вводится понятие изоморфизма графов.

Определение. Графы и называются изоморфными, если существует такая биекция f множества на множество , что тогда и только тогда, когда . Отображение f в этом случае называется изоморфизмом в .

Тот факт, что графы и изоморфны, записывается так: .

Для графов, изображенных на рисунке 6, изоморфизмом является, например, отображение, задаваемое таблицей:

x (вершина графа )	a	b	c	d
f(x) (вершина графа )	a	b	d	c

Заметим, что в этом примере есть и другие изоморфизмы первого графа во второй.

Это определение изоморфизма годится и для ориентированных графов, нужно только обе упоминаемые в нем пары вершин считать упорядоченными.

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

В общем случае узнать, изоморфны ли два графа, достаточно сложно. Если буквально следовать определению, то нужно перебрать все биекции множества вершин одного из них в множество вершин другого и для каждой из этих биекций проверить, является ли она изоморфизмом. Для n вершин имеется n! биекций и эта работа становится практически невыполнимой уже при не очень больших n (так, 10! = 3628800, ). Однако для многих конкретных пар графов их неизоморфность устанавливается довольно легко. Рассмотрим, например, графы, изображенные на рисунке 7. Так как при изоморфизме пара смежных вершин переходит в пару смежных, а пара несмежных – в пару несмежных, то ясно, что число ребер у двух изоморфных графов должно быть одинаковым. Поэтому сразу можно сказать, что графы и , у которых разное количество ребер, неизоморфны. У графов и одинаковое число ребер, но они тоже неизоморфны. Это можно установить, сравнивая степени вершин. Очевидно, при изоморфизме каждая вершина переходит в вершину той же степени. Но если выписать степени всех вершин графа в неубывающем порядке, то получится последовательность (2,2,3,3,3,3), а для графа получится последовательность (2,2,2,3,3,4). Из того, что эти последовательности различны, следует неизоморфность двух графов. С графами и дело обстоит немного сложнее – у них и наборы степеней одинаковы. Все же и эти графы неизоморфны: можно заметить, что в есть подграф, являющийся циклом длины 3, а в таких нет. Ясно, что при изоморфизме каждый подграф одного графа переходит в изоморфный ему подграф другого.

Рис.7

Характеристики графов, которые сохраняются при изоморфизме, называются инвариантами. В этом примере мы видели некоторые простые инварианты – число ребер, набор степеней, число циклов заданной длины, в дальнейшем будут введены еще многие другие. Если удается установить, что для двух исследуемых графов некоторый инвариант принимает разные значения, то эти графы неизоморфны. Изоморфность же двух графов можно доказать, только предъявив соответствующую биекцию.

Графы и матрицы

Пусть G – граф с n вершинами, причем . Построим квадратную матрицу A порядка n, в которой элемент , стоящий на пересечении строки с номером i и столбца с номером j , определяется следующим образом:

Она называется матрицей смежности графа. Матрицу смежности можно построить и для ориентированного графа, и для неориентированного, и для графа с петлями. Для обыкновенного графа она обладает двумя особенностями: из-за отсутствия петель на главной диагонали стоят нули, а так как граф неориентированный, то матрица симметрична относительно главной диагонали. Обратно, каждой квадратной матрице порядка n, составленной из нулей и единиц и обладающей двумя указанными свойствами, соответствует обыкновенный граф с множеством вершин .

Другая матрица, ассоциированная с графом – это матрица инцидентности. Для ее построения занумеруем вершины графа числами от 1 до n, а ребра – числами от 1 до m. Матрица инцидентности I имеет n строк и m столбцов, а ее элемент равен 1, если вершина с номером i инцидентна ребру с номером j, в противном случае он равен нулю. На рисунке 8 показан граф с занумерованными вершинами и ребрами и его матрицы смежности и инцидентности.

Рис. 8

Для ориентированного графа матрица инцидентности определяется несколько иначе: ее элемент равен 1, если вершина i является началом ребра j, он равен -1, если она является концом этого ребра, и он равен 0, если эта вершина и это ребро не инцидентны друг другу.

Взвешенные графы

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