[МУЗЫКА] [МУЗЫКА] На прошлой лекции мы с вами говорили о семействе графов Хэмминга, которые являются как графами Кэли, так и дистанционно-транзитивными графами. Сегодня мы рассмотрим еще одно важное семейство дистанционно-транзитивных графов, но они далеко не всегда являются графами Кэли — это графы Джонсона. Итак, по определению, графом Джонсона с параметрами (n, m) называется граф, вершинами которого являются m-подмножества данного n-множества. И две вершины в этом графе смежны тогда и только тогда, когда они пересекаются по подмножествам размерности m − 1. Метрика Джонсона между m-подмножествами определяется как половина от размера их симметрической разницы, а соответственно, расстояние между вершинами в графе Джонсона равно половине четного расстояния Хэмминга между соответствующими m-множествами. Граф Джонсона обладает такими свойствами, как: во-первых, граф Джонсона с параметрами (n, m) изоморфен графу Джонсона с параметрами (n, n − m); он также является регулярным в степени m(n − m), а диаметр его вычисляется из двух — нужно выбрать минимальное значение между m и n − m. Этот граф является дистанционно-транзитивным, а раз он является дистанционно-транзитивным, значит, он является и дистанционно- регулярным: массив его пересечений сейчас вы видите на слайде. Но в целом этот граф не является графом Кэли. Давайте рассмотрим частные случаи графа Джонсона для того, чтобы убедиться, что это действительно так. Итак, при m = 1 граф Джонсона изоморфен полному графу на n вершинах, а значит, он будет являться графом Кэли. Мы с вами об этом говорили в четвертой лекции этого же модуля, когда рассматривали простейшие примеры графов Кэли. Теперь, пусть у нас m = 2, а n ⩾ 4, тогда граф Джонсона в этом случае называется треугольным графом, его вершинами являются двухэлементные подмножества множества из n-элементов. И две вершины смежны тогда, и только тогда, когда они пересекаются ровно по одному элементу. Такой граф является также сильно регулярным с параметрами число сочетаний n по 2, 2(n − 2), n − 2 и 4. На слайде сейчас представлен треугольный граф T(4). Он является графом Кэли на конечной аддитивной группе порядка 6, а порождающее множество этого графа состоит из элементов (1, 2, 4, 5). То есть мы нашли с вами граф Кэли. Теперь давайте мы покажем, что имеет место следующий факт: что граф Джонсона с параметрами (5, 3) не является графом Кэли. Из свойств графа Джонсона следует, что такой граф должен иметь регулярность, равной 6, а кроме этого, он является дистанционно регулярным графом диаметра 2 (то есть сильно регулярным), и параметр b₁ должен быть равен 2. Давайте с вами воспользуемся вот этим последним свойством графа Джонсона (5, 3), чтобы показать, что на самом деле он не является графом Кэли. То есть нельзя подобрать подходящую группу и подходящее порождающее множество такие, что найденный граф Кэли был бы изоморфен графу Джонсона (5, 3). Ну будем исходить из противного. Давайте предположим, что есть такой граф Кэли, это значит, что можно найти подходящую группу и подходящее порождающее множество. При этом порядок группы должен быть равен 10, а порождающее множество должно содержать шесть элементов. Как мы с вами знаем, что существуют только две неизоморфные группы на десяти элементах: это аддитивная группа и диэдральная. Возьмем первую группу. Она содержит один элемент порядка 2, четыре элемента порядка 10, и четыре элемента порядка 5. Поскольку по определению графа Кэли всякое порождающее множество должно удовлетворять двум условиям, а именно оно должно быть свободным от единичного элемента и быть симметричным, тогда порождающее множество с шестью элементами может содержать либо четыре элемента порядка 10 и два элемента порядка 5, либо два элемента порядка 10 и четыре элемента порядка 5. Ну в первом случае без ограничения общности, можно считать, что порождающее множество будет содержать элементы (±1, ±2 и ±3). Давайте рассмотрим граф Кэли, который возникает на этой группе с этим порождающим множеством и будем его строить относительно вершины 0. Тогда у нас первый слой будет содержать элементы порождающего множества, а второй слой содержит элементы ±4 и 5. И единственной вершиной из второго слоя, которая будет смежна вершине 1 из первого слоя, будет являться вершина 4. Это означает, что b₁ будет равно единице в этом случае. Но мы с вами знаем, что на самом деле для графа Джонсона (5, 3) это значение должно быть равно двум. Тем самым мы имеем противоречие. Следовательно, рассмотренное нами порождающее множество не дает нам граф Кэли, который был бы изоморфен нужному нам графу Джонсона. Второй случай рассматривается точно таким же образом, и я вам предлагаю это сделать самостоятельно. Также попробуйте самостоятельно убедиться в том, что на диэдральной группе вы тоже не получите граф Кэли, который был бы изоморфен нужному нам графу Джонсона. Нужно сказать, что из свойства графа Джонсона также следует, что граф Джонсона с параметрами (5, 3) будет изоморфен графу Джонсона с параметрами (5, 2). А это значит, что мы имеем следующий факт: граф Джонсона с параметрами (5, 2) не является графом Кэли. Известен также еще один факт, который говорит нам следующее: что граф Джонсона с параметрами (n, 2) является дополнением графа Кнезера с параметрами (n, 2). Вот последний граф мы сейчас с вами определим. Итак, по определению, графом Кнезера с параметрами (n, k), где k ⩾ 1, а n ⩾ 2k + 1, задается следующий граф: в нем вершины соответствуют k-элементным подмножествам n-элементного множества, и вершины соединены тогда и только тогда, когда соответствующие подмножества не пересекаются. Граф Кнезера обладает следующими свойствами: он является регулярным, и степень его равна числу сочетаний из (n − k / k), он является дистанционно транзитивным тогда и только тогда, когда он совпадает с нечетным графом с параметрами (2n − 1, n − 1). Интересующий нас граф Кнезера с параметрами (n, 2) является дистанционно регулярным с массивом пересечений, которые вы сейчас видите на слайде. Там же представлен граф Кнезера с параметрами (5, 2), он изоморфен дополнению Джонсона с параметрами (5, 2). А кроме этого, он еще изоморфен графу Петерсена, который, как нам было показано ранее на четвертой лекции, также не является графом Кэли. Приведем еще один факт о графах Кнезера. Граф Кнезера с параметрами (n, k) не является графом Кэли за исключением следующих двух случаев. Если у нас k = 2, а n является степенью простого числа, и при этом n еще равно 3 (mod 4), а во втором случае если k = 3, а n = 8 или 32. Этот факт дает нам характеризацию графов Кнезера, являющихся графами Кэли. На этом мы завершаем с вами модуль номер три. Многие из рассмотренных в этом модуле примеров будут не раз еще возникать в последующих лекциях нашего курса. Много интересных примеров графов Кэли, имеющих в том числе разнообразное приложение, задаются на симметрической группе. И один такой пример и его связь со спектральной теорией целочисленных графов и теорией представлений симметрической группы мы будем рассматривать в пятом модуле. А о спектральной теории графов мы подробно поговорим в следующем модуле.
