[МУЗЫКА] [МУЗЫКА] В первом модуле мы с вами познакомились с таким классом графов, как сильно регулярные. Напомним, что это такое. Граф Γ называется сильно регулярным, если существует такой набор чисел k, λ и μ, что выполняются следующие условия: во-первых, граф является k-регулярным, во-вторых, любые две смежные вершины имеют в точности λ общих соседей, и в-третьих, любые две несмежные вершины имеют μ общих соседей. Стоит на всякий случай отметить одну тонкость терминологии. Сильный регулярный граф называют примитивным, если он и его дополнение являются связными графами. Если же это условие не выполняется, то граф называют непримитивным. Для непримитивных графов параметр μ либо равен 0, либо k, и в этом случае граф представляет собой либо объединение полных графов на, допустим, m вершинах, либо дополнение к такому объединению. Стоит отметить, что некоторые авторы в принципе выбрасывают из рассмотрения такие графы, мы так делать не будем, но все-таки в рамках нашего курса мы будем подразумевать обычно под сильно регулярными графами именно примитивные графы, то есть те графы, которые связаны вместе со своим дополнением. В данном месте лекции я бы очень хотела процитировать Питера Камерона, который в одной из своих работ пишет, что сильно регулярные графы в каком-то смысле находятся посередине между очень хорошо структурированными объектами и совершенно случайными. И очень ярко это демонстрирует следующий пример графа с параметрами (36, 10, 4, 2). Такой граф существует только один, а вот графов с параметрами (36, 15, 6, 6) — обратите внимание, параметры не сильно отличаются от предыдущих, — вот таких графов уже более, чем 3.000. Из этого следует, что какой-то единой асимптотики для всего семейства сильно регулярных графов не существует. То есть в зависимости от параметров сильно регулярные графы либо могут вести себя как очень симметричные структуры, либо как практически случайные. Например, графы Пэли — не путайте с графами Кэли, хотя графы Пэли являются графами Кэли, — так вот, графы Пэли часто используют для моделирования псевдослучайных графов. Пусть Γ — это сильно регулярный граф с параметрами (v, k, λ, μ), тогда граф Γ с чертой, являющийся дополнением к графу Γ, также будет сильно регулярным графом со следующими параметрами, представленными на экране. Вспомним, что граф Петерсена — это сильно регулярный граф с параметрами (10, 3, 0, 1), тогда дополнением к графу Петерсена будет являться следующий граф, и его параметры будут (10, 6, 5, 4). Могут ли быть параметры сильно регулярного графа прямо совсем произвольными? На самом деле нет. Следующее утверждение говорит нам о том, как связаны параметры между собой. Итак, пусть Γ — это сильно регулярный граф с параметрами (v, k, λ, μ), тогда при μ ≠ 0 справедливо следующее соотношение. Для доказательства этого соотношения нам достаточно посчитать число вершин на расстоянии 0, 1 и 2 от некоторой фиксированной вершины. Итак, зафиксируем какую-то вершину, на расстоянии 0 от нее находится только сама эта вершина, таким образом, первое слагаемое в правой части равно единицы, на расстоянии 1 находятся все вершины, смежные с выбранной, то есть мы получаем слагаемое k. А для того чтобы посчитать число вершин t, находящихся на расстоянии 2, мы вычислим двумя способами количество ребер между первым и вторым слоем в нашем слоевом представлении. С одной стороны это число равно μt, как указано на картинке, с другой стороны k * (k − λ − 1). Поскольку таким образом мы посчитали все вершины графа, мы получаем требуемое равенство. Давайте теперь посмотрим, что у нас происходит с матрицей смежности сильно регулярного графа. Пусть Γ — обыкновенный граф порядка v, не являющийся полным или безреберным с матрицей смежности A, тогда следующие утверждения являются эквивалентными. Первое: Γ является сильно регулярным графом с параметрами (v, k, λ, μ). Второе: квадрат матрицы смежности A² представляется следующим видом для некоторых вещественных чисел k, λ, μ. И третье условие: A имеет в точности три собственных значения. Итак, докажем эту эквивалентность. Сначала мы перепишем второе условие в следующем виде. Если мы теперь внимательно присмотримся к нему, то эквивалентность первых двух определений сразу станет очевидной. Действительно, слева у нас квадрат матрицы смежности. Как мы помним, элементы A² задают число путей длины 2 между вершинами, а справа мы считаем три вида таких путей: от вершины по ребру и обратно к самой, за это у нас отвечает слагаемое k, умноженное на единичную матрицу, второе слагаемое справа считает пути длины 2 между двумя смежными вершинами. Вспомним, что параметр λ говорит нам о числе треугольников в графе с выбранным основанием. И, наконец, третье слагаемое считает пути длины 2 между несмежными вершинами. Теперь покажем, что из второго условия у нас следует третье. Пусть θ — это не главное, то есть не максимальное собственное значение, а x — соответствующий ему собственный вектор. Тогда вектор x умноженный на матрицу из всех единиц, будет давать ноль. Умножаем равенство из второго условия на вектор x, получаем следующее соотношение — это у нас квадратное уравнение. Если мы проверим его дискриминант, мы увидим, что он строго положителен, а значит, наше квадратное уравнение будет иметь два решения. Теперь покажем, что из третьего условия у нас следует второе условие. Пусть r и s — это два неглавных собственных значения. Тогда имеем следующее соотношение для некоторого вещественного числа α. Следовательно, A² является линейной комбинацией матриц A единичной и матриц из всех единиц. В качестве следствия из предыдущей теоремы мы получаем следующую: Пусть Γ — сильно регулярный граф с матрицей смежности A и параметрами (v, k, λ, μ), пусть r и s — это не главные собственные значения, именно такие, что r > s, а f и g — это соответственно их кратности. Тогда справедливы следующие три соотношения. Для получения первого условия нам достаточно вспомнить теорему Виета о сумме корней квадратного уравнения и об их произведении, а также само квадратное уравнение, которое у нас возникло в предыдущей теореме. Чтобы получить второе условие, нам нужно также вспомнить, что сумма кратности всех собственных значений у нас равна n, то есть f + g + 1 = n, а кроме того, след матрицы A, равный сумме собственных значений, является нулевым, то есть k + f * r + g * s = 0. Последнее условие мы получаем из предыдущих двух. Если f ≠ g, то мы можем разрешить систему уравнений на параметры относительно r и s. В случае, когда f = g, у нас должно выполняться следующее соотношение, что возможно только при μ − λ = 1 и при v = 2k + 1, откуда и получаем требуемое представление о параметрах. Рассмотренные условия на параметры являются далеко не единственными. Довольно мощный инструмент проверки допустимости параметров — это так называемые условия Крейна, и с ними мы с вами познакомимся в шестом модуле. На этом лекция о сильно регулярных графах у нас завершается, хотя, конечно, мы еще будем вспоминать их по ходу курса, а в следующей лекции мы с вами посмотрим на дистанционно-регулярные графы и их спектры.
