Мы с вами много говорили о матрице смежности, о ее каких-то свойствах и спектре. Однако, кроме матрицы смежности другой популярной матрицей является матрица Лапласа. Поскольку букву L у нас уже занял реберный граф, матрицу Лапласа далее мы будем обозначать буквой Q. Итак, что же это такое за матрица? Пусть Гамма — это произвольный граф, необязательно регулярный. Тогда матрицей Лапласа этого графа называется разность между матрицей степеней графа и его матрицей смежности. Иногда, кстати, матрицу Лапласа называют также матрицей Кирхгофа. Казалось бы, по определению матрица Лапласа не то чтобы как-то сильно отличается от матрицы смежности. Однако, на самом деле это впечатление очень обманчиво. Матрица Лапласа таит в себе очень много информации о структуре графа и не только о ней, но обо всем по порядку. Давайте прежде всего пощупаем новое определение на каком-нибудь осязаемом примере. Возьмем граф P3 и выпишем его матрицу Лапласа. Посчитаем собственные значения матрицы Лапласа — это будут 0, 1 и 3. Теперь вернемся в произвольный случай. Рассмотрим какой-то граф Гамма, и давайте теперь каждому из ребер назначим направление. В результате мы получим некоторый ориентированный граф, обозначим его Гамма', и построим для этого графа матрицу инцидентности следующим образом: если мы возьмем ребро ek, состоящее из вершин i и j, и пускай в этом ребре у нас направление от i к j. Тогда в матрице инцидентности на ik-той позиции мы поставим минус единичку, а на j-той позиции мы поставим единичку. Полученная таким образом матрица инцидентности B будет состоять из нулей, единиц и минус единиц. Пример представлен на экране. Следующая лемма говорит о том, что если граф Гамма на n вершинах имеет c компонент связности, то ранг матрицы инцидентности графа Гамма', где Гамма' — произвольная ориентация графа, равен n минус c. Для чего же мы вводили эту матрицу инцидентности B? Оказывается, несмотря на то, что мы выбирали произвольную ориентацию графа Гамма', мы тем не менее всегда можем выразить матрицу Лапласа через матрицу инцидентности B. Каким образом? Оказывается, Q равно B умноженное на B транспонированное. Проверьте это самостоятельно. Проиллюстрируем это также примером. Возьмем граф Гамма и построим по нему два графа — Гамма' и Гамма'', соответствующим, как мы видим, разным ориентациям ребер. Несмотря на то, что у нас получились разные матрицы инцидентности, при их перемножении на самих себя транспонированных мы получаем как раз таки матрицу Лапласа. Итак, что к этому времени мы можем сказать про спектр матрицы Лапласа? Во-первых, в случае неориентированного графа матрица Q у нас симметрична, а, следовательно, ее спектр, как мы помним, вещественный. Во-вторых, из того факта, что матрица Q у нас представляется в виде произведения матрицы B на матрицу B транспонированную, мы получаем, что она также является положительно полуопределенной. Кроме того, это означает, что все ее собственные значения не меньше нуля, и поскольку сумма элементов в каждой строке матрицы Лапласа равна нулю, то наша матрица еще является и вырожденной, и вектор из всех единиц будет собственным для собственного значения равного нулю. Следовательно, мы можем обозначать собственные значения матрицы Лапласа буквами Мю1, Мю2 и так далее Мю n в виде возрастающей последовательности, где Мю1 равно нулю. Нетрудно проверить, что если L с чертой — это матрица Лапласа дополнения графа Гамма, то L с чертой можно выразить следующим образом с соответствующими собственными значениями. Отсюда, в частности, следует, что Мю n у нас меньше либо равно n. Заметим, что если граф Гамма является k-регулярным с собственными значениями Тета1 и так далее Тета n, то Мю i выражается следующим образом. Как же будет выглядеть локальное определение собственного вектора в случае матрицы Лапласа? Итак, пускай Q умноженное на f равно Мю на f. Тогда значение в вершине i умноженное на степень вершины i минус собственное значение Мю равно сумме по окрестности этой вершины как указано на экране. Одним из ранних результатов алгебраической теории графов является связь между матрицей Лапласа и числом остовных деревьев в графе. Напомним, что остовным деревом в графе Гамма называется связный подграф без циклов, в который входят все вершины исходного графа. Остовные деревья используются в проектировании коммуникационных сетей, в протоколах маршрутизации, в кластерном анализе и других задачах. Каким же образом остовные деревья могут быть связаны с матрицей Лапласа? Прежде чем дать ответ на этот вопрос давайте на всякий случай вспомним, что такое алгебраическое дополнение элемента. Определение представлено на экране. Итак, мы готовы перейти к теореме Кирхгофа, также известной как матричной теореме о деревьях. Пусть Гамма — это неориентированный связанный граф. Тогда все алгебраические дополнения матрицы Лапласа равны между собой, а их общее значение равно числу остовных деревьев в графе Гамма. Кроме того, это значение может быть выражено через произведение всех ненулевых собственных значений матрицы Лапласа поделенное на n. Данная теорема в неявном виде появилась в работах Кирхгофа, посвященных расчетам электрических цепей. С помощью этой теоремы мы можем, например, посчитать число остовных деревьев в полном графе Kn. Вычислим спектр матрицы Лапласа полного графа. Отсюда получаем, что число остовных деревьев равно n в степени n минус два. Эта формула известна также как формула Кэли. Пусть Гамма — это неориентированный граф. Тогда кратность лапласова собственного числа ноль равна числу компонент связности графа Гамма. Значит, Мю2 равно нулю тогда и только тогда, когда граф у нас несвязный. Если у нас есть какая-то качественная характеристика, почему бы не перевести ее в количественную характеристику? Видимо, это и стало источником вдохновения для Мирослава Фидлера, чтобы дать второму собственному значению матрицы Лапласа название "алгебраическая связность". Фидлер показал, что чем дальше Мю2 отстоит от нуля, тем более связным является граф. Иными словами, для этого параметра выполняется свойство монотонности, то есть алгебраическая связность не уменьшается при добавлении ребер в граф. Что говорит нам следующая теорема? Алгебраическая связность используется для анализа устойчивости и синхронизации различных сетей. Кроме того, она является нижней оценкой на так называемую вершинную связность графа. Пусть Гамма — это граф на множестве вершин V, и W — это такое множество вершин, что граф, индуцированный на V без W, является несвязным. Тогда выполняется следующее соотношение. Эта теорема означает, что минимальное число вершин, которое нужно удалить из графа, чтобы у нас он стал несвязным, больше либо равно чем алгебраическая связность этого графа. Мы еще вернемся к собственному значению, собственному вектору Фидлера в следующей лекции и посмотрим, как можно их использовать. Но перед этим давайте познакомимся с одной весьма любопытной квадратичной формой, соответствующей матрице Лапласа. Рассмотрим выражение x транспонированное, умноженное на Q, умноженное на x. Давайте распишем его по определению матрицы Лапласа. После некоторых преобразований мы получаем, что это выражение равно сумме по ребрам, где под знаком суммирования у нас стоит разность между значениями на вершинах этого ребра, возведенные в квадрат. Что же это означает? Оказывается, у этого есть интересная комбинаторная интерпретация. Давайте рассмотрим произвольное подмножество вершин S в нашем графе. И пускай x — это будет характеристический вектор этого подмножества. Что это означает? Означает, что xi у нас равно единице, если вершина i принадлежит множеству S, и нулю, если вершина i не принадлежит множеству S. Чему же тогда в таком случае будет равно выражение нашей квадратичной формы? Если мы берем ребро из S, то оно не вносит вклада в сумму, так как обе вершины из этого ребра имеют значение единица. Аналогично, у нас не вносит вклад и ребра из дополнения к множеству S. А вот ребра, которые связывают вершины из множества S с остальными вершинами, не входящими в это множество, как раз таки вносят вклад по единичке. Таким образом, мы получаем, что квадратичная форма у нас равна в точности числу ребер между множеством S и оставшимися вершинами в нашем графе. Итак, мы уже достаточно познакомились с матрицей Лапласа и наконец готовы переходить непосредственно к ее использованию в различных задачах, чем мы с вами и займемся в следующей лекции.
