Матрица смежности и матрица инцидентности графа

Пусть дан граф с множеством вершин и множеством рёбер

Матрица смежности графа – это матрица размера элементы которой определяются по формуле

Матрица инцидентности графа – это матрица размера элементы которой определяются по формуле

Следует отметить, что каждая из матриц определяет граф однозначно (с точностью до изоморфизма): графы, имеющие одинаковые матрицы (или изоморфны друг другу. Далее, перестановка строк или столбцов матрицы даёт граф, изоморфный первоначальному (это соответствует перенумерации вершин или рёбер графа ). Матрица симметрическая (т.е. или, другими словами, при любых ). На диагонали матрицы стоят нули ( ). Перестановка строк или столбцов матрицы вообще говоря, недопустима. Однако, можно делать синхронные перестановки строк и столбцов с одинаковыми номерами, т.е. переставлять между собой i-ю и j-ю строки, затем i-й и j-й столбец и т.д. – это соответствует перенумерации вершин графа.

Замечание. Для обобщённых графов (графов с петлями или кратными рёбрами) и для ориентированных графов также можно ввести понятие матрицы смежности и матрицы инцидентности. Тогда в матрице смежности могут появиться (у графов с кратными рёбрами), на диагонали могут быть элементы (у графов с петлями), у ориентированного графа матрица может не быть симметрической.

Упражнение 3.7. Построить матрицу смежности и матрицу инцидентности графа изображённого на рисунке 3.10.

Решение. Пусть вершины и рёбра занумерованы так, как показано на рисунке. Тогда по определению матриц и получаем:

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

Отметим ещё ряд свойств матриц и Количество единиц в i-й строке матрицы (или, что то же самое, сумма элементов i-й строки) равна степени вершины:

Кроме того, как уже отмечалось ранее,

Двойные суммы сводятся к однократным следующим образом: Поэтому а значит,

(4)

Аналогично получаем, что

Упражнение 3.8. Построить граф по его матрице смежности

Решение. Так как а остальные равны 0, то рёбрами соединяются лишь пары вершин 1-2 и 3-4. Мы получаем граф, изображённый на рисунке 3.11.

Этот граф несвязный, он имеет две компоненты связности: одна с вершинами 1, 2, другая – с вершинами 3, 4.

Упражнение 3.9. Изобразить граф, имеющий следующую матрицу инцидентности:

Решение. По матрице мы определяем, что граф имеет 5 вершин и 4 ребра. Так как в 1-й строке матрицы единицы стоят на 1-й и 5-й позициях, то ребро соединяет вершины 1 и 5. Рассматривая остальные строки матрицы и рассуждая аналогично, мы получим граф, изображённый на рисунке 3.12.

Упражнение 3.10. Выяснить, существует ли граф со следующим набором степеней вершин:

(а) 1, 1, 1, 2, 2, 3, 3, 4; (б) 1, 1, 1, 2, 2, 2, 3, 4.

Решение. По формуле (4) т.е. Это невозможно, так как Р – целое число. Следовательно, графа с набором степеней вершин (а) не существует.

Для набора (б) получаем поэтому можно попробовать построить граф. Начинать, конечно, нужно с вершины степени 4, затем подрисовывать вершины и рёбра. Вершин должно быть 8, так как даны 8 степеней вершин. Попытки построить граф оказываются успешными, более того, найдены даже два таких графа: и – см. рис. 3.13. Графы и не изоморфны, например, ввиду того, что у графа вершина степени 3 инцидентна двум вершинам степени 1, а в графе это не так.

Замечание. Предыдущее упражнение показывает, что набор степеней вершин не определяет граф однозначно.

Упражнение 3.11.Доказать, что в любом графе, содержащем более одной вершины, найдутся две различные вершины одинаковой степени.

Решение. Пусть – граф с вершинами. Тогда степени вершин могут принимать значения Этих чисел штук. Если все степени вершин различны, то для каждого существует вершина степени Значит, есть вершина степени 0 и есть вершина степени Так как то – изолированная вершина, она не соединена ребром ни с какой вершиной. А так как то вершина соединена со всеми остальными вершинами и, в частности, с вершиной Мы получили противоречие, а значит, графа с различными степенями всех вершин не существует.

Возникает естественный вопрос: как по матрице смежности или матрице инцидентности графа определить, является ли граф связным, и разбить его на компоненты связности? Ответ получить несложно: если матрицу синхронной перестановкой строк и столбцов можно превратить в блочную матрицу:

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

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

Приведём пример. Пусть

–

матрица инцидентности графа Поставим второй и третий столбцы в конец матрицы, а затем то же сделаем со второй и третьей строками. Мы получим:

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

Нумерация вершин на рисунке 3.14а соответствует новой матрице. На рисунке 14б приведён граф с первоначальной нумерацией вершин. Связь между двумя нумерациями видна из следующего преобразования: (столбцы и строки с номерами 2,3 отправляются в конец).

Степени матрицы смежности ( ) имеют интересный геометрический смысл. А именно, пусть Тогда равно количеству путей длины (т.е. из рёбер) из i-й вершины в j-ю. Приведём пример. Матрица является матрицей смежности графа изображённого на рисунке 3.15.

Возведём матрицу в квадрат. Получим: Так как то существуют ровно 2 пути длины 2 из вершины 2 в эту же вершину. Это 2-1-2 и 2-3-2.

Деревья и леса

Дерево – связный граф без циклов. Лес – произвольный граф без циклов.

Очевидно, связные компоненты леса являются деревьями. Необходимые и достаточные условия для графа “быть деревом” даёт следующая теорема.

Теорема.Связный граф является деревом в том и только том случае, если количества его вершин и рёбер связаны соотношением

Отметим ещё два свойства деревьев: 1) для любых вершин и дерева существует единственный путь из в 2) в любом дереве есть висячая вершина (если дерево имеет хотя бы одно ребро, то у него не менее двух висячих вершин).

Упражнение 3.12. Найти количество неизоморфных графов с 3 вершинами.

Решение. Если граф с 3 вершинами не имеет ни одного ребра, то он изоморфен Рассматривая далее случаи графов с 1, 2, 3 рёбрами, мы получим все неизоморфные графы с 3 вершинами – см. рис. 3.16. Их всего 4.

Упражнение 3.13.Найти все (с точностью до изоморфизма) связные графы с 4 вершинами.

Решение. Пусть – граф с 4 вершинами. Понятно, что если рёбер два или меньше, то несвязен. Следовательно, возможное количество рёбер – это 3, 4, 5, 6. Граф с 6 рёбрами – полный, он изоморфен графу Несложный перебор оставшихся вариантов показывает, что графов, удовлетворяющих требуемым условиям, ровно 6. Они изображены на рис. 3.17.

Упражнение 3.14. Найти все (с точностью до изоморфизма) деревья с 5 вершинами.

Решение. Пусть – дерево с 5 вершинами. Понятно, что возможны ровно 3 следующих случая: а) все степени вершин не превосходят 2; б) есть вершина степени 3; в) есть вершина степени 4. В каждом из этих случаев имеется по одному дереву – см. рисунок 3.18.

Существуют способы компактной записи (кодирования) деревьев. Из них мы рассмотрим два: двоичное (или бинарное) кодирование (т.е. составление кода из 0 и 1) и кодирование Прюфера (код из натуральных чисел).

При бинарном кодировании каждому дереву приписывается последовательность из 0 и 1 длины где – количество рёбер дерева. В этой последовательности ровно единиц и столько же нулей. Для составления кода представим себе, что граф представляет собой реку, по берегу которой мы совершаем её обход так, чтобы река оставалась всё время с одной стороны, для определённости будем считать, что слева. При проходе по ребру в первый раз в код записывается 0, а второй раз (по противоположному берегу) – пишется 1. На рисунке 3.19 показано на примере, как осуществляется бинарное кодирование.

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

Теорема. Пусть – последовательность, в которой нулей и единиц. Она является бинарным кодом некоторого дерева в том и только том случае, если в любом её начальном отрезке количество нулей не меньше количества единиц.

Например, последовательность 0011011100011 не является кодом никакого дерева (так как содержит начальный отрезок 00110111), а последовательность 00011010011011 является кодом дерева.

Декодирование (т.е. построение дерева по коду) можно осуществить, копируя процесс кодирования, т.е. восстанавливая “реку”, обход которой был совершён.

Упражнение 3.15. Построить дерево по его двоичному коду 00011010011011.

Решение показано на рисунке 3.20.

Для построения кода Прюфера вначале следует занумеровать вершины дерева натуральными числами (произвольным образом). Далее поступаем так. Берём висячую вершину с наименьшим номером. Пусть это будет вершина с номером Она инцидентна единственной вершине, которая имеет номер, скажем, Тогда записываем в код и удаляем вершину с ребром после чего возвращаемся к началу алгоритма. Это делается до тех пор, пока не останется одно ребро. Длина кода получается равной где – количество вершин дерева.

Упражнение 3.16. Построить код Прюфера дерева, изображённого на рисунке 3.21.

Решение. Применим описанный выше алгоритм (см. рисунок 3. 22):

1) висячая вершина с наименьшим номером – 2; пишем 1, удаляем вершину 2 и ребро (1,2);

2) висячая вершина – 1; пишем 3, удаляем вершину 1 и ребро (1,3);

3) висячая вершина – 5; пишем 4, удаляем вершину 5 и ребро (4,5);

4) висячая вершина – 4; пишем 3, удаляем вершину 4 и ребро (4,3).

Получится код 1343.

Декодирование кода Прюфера осуществляется следующим образом. Пусть дан код где Нарисуем на плоскости точек, занумерованных числами пока не соединённые друг с другом рёбрами. Далее рисуем рёбра одно за другим согласно следующему правилу:

1) находим – наименьшее число из множества которого нет в последовательности соединяем ребром вершины и

2) находим – наименьшее число из множества не встречающееся в последовательности соединяем ребром вершины и

3) находим – наименьшее число из множества не встречающееся в последовательности соединяем ребром вершины и

. . . . . . . . . . . .

находим – наименьшее число из множества не встречающееся в последовательности соединяем ребром вершины и

в последовательности отсутствуют ровно 2 числа из множества обозначим их и соединим соответствующие вершины.

Упражнение 3.17. Построить дерево по коду 1353.

Решение. Применим описанный выше алгоритм.

1) Так как длина кода равна 4, то дерево будет иметь 6 вершин. Нарисуем на плоскости точки 1,2,3,4,5,6.

2) Наименьшее число – это 2. Пишем его под 1:

3) Наименьшее число – это 1. Пишем его под 3:

4) Наименьшее число – это 4. Пишем его под 5:

5) Наименьшее число – это 5. Пишем его под 3:

6) Отсутствуют в последовательности 2145 числа 3 и 6.

Таким образом, в графе будут следующие рёбра: (1,2), (3,1), (5,4), (3,5), (3,6). Искомое дерево изображено на рисунке 3.23.

Замечание. В отличие от бинарного кода код Прюфера определяется деревом однозначно, если зафиксирована нумерация вершин дерева. Назовём дерево с заданной на нём нумерацией вершин помеченным деревом. Кодирование Прюфера определяет взаимно однозначное соответствие между помеченными деревьями и их кодами. Следовательно, число помеченных деревьев с вершинами (обозначим это число ) равно числу их кодов. Кодом является произвольная последовательность чисел, взятых из множества Таким образом, мы имеем:

(5)

Формула (5) называется формулой Кэли.

Циклы на графе