[МУЗЫКА] [МУЗЫКА] На прошлой лекции мы начали с вами говорить об автоморфизмах графов и также рассмотрели асимметричные графы. Сегодня мы с вами поговорим о транзитивном действии группы на графов и рассмотрим симметричные графы. Итак, действие группы G называется транзитивным на множестве X, если для любых двух его элементов, скажем, a и b этого множества X существует некоторый элемент G нашей группы такой, что будет выполняться условие транзитивности. И тогда граф называется симметричным, если его группа автоморфизмов действует транзитивно на упорядоченных парах смежных вершин. Примером кубического симметричного графа является граф Петерсена. Любая пара смежных вершин его переводится в любую другую пару вершин. Обоснованием этого факта является то, что любой 5-цикл графа Петерсена переводится в любой цикл длины 5. Известно также, что группа автоморфизмов этого графа изоморфна симметрической группе в степени 5. В целом же, всякий связный симметричный граф является вершинно-транзитивным и реберно-транзитивным. И вот эти два важных понятия мы с вами сейчас и определим. Итак, по определению, связный граф называется вершинно-транзитивным, если для любых двух вершин этого графа существует автоморфизм, который переводит одну вершину в другую. Всякий вершинно-транзитивный граф является регулярным. Но не всякий регулярный граф является вершинно-транзитивным. Первое утверждение следует непосредственно из определения вершинно-транзитивного графа, поскольку автоморфизм должен переводить только вершины одной и той же степени, значит, граф должен являться регулярным. А второе утверждение подтверждается тем фактом, что граф Фрухта, который мы с вами ввели на прошлой лекции, является регулярным, но не вершинно-транзитивным графом. В самом деле, вершина 1 графа Фрухта принадлежит циклу длины 3, в то время как вершина 3 не принадлежит ни одному циклу длины 3. Вот это и будет основанием того, чтобы сказать, что этот граф не является вершинно-транзитивным. Он у нас регулярный, но не вершинно-транзитивный. А теперь давайте с вами поговорим о реберно-транзитивных графах. По определению, связный граф называется реберно-транзитивным, если для любой пары его ребер существует автоморфизм, который переводит одно ребро в другое ребро. Эти свойства — вершинная транзитивность или реберная транзитивность — не являются взаимозаменяемые, поскольку имеются вершинно-транзитивные графы, которые не являются реберно-транзитивными, и наоборот. Так, например, полный двудольный граф с долями, размерности которых не совпадают, будут являться примером реберно-транзитивного графа, но не вершинно-транзитивного. При этом, если вы возьмете полный двудольный граф, у которого доли будут иметь одну и ту же размерность, то ваш граф тут же станет примером графа, который является вершинно-транзитивным и реберно-транзитивным. На слайде сейчас вы видите также вершинно-транзитивный граф, который не является реберно-транзитивным графом, поскольку в этом графе отсутствует автоморфизм, переводящий ребро uv в ребро u'v'. Как это можно показать? Это можно показать следующим образом. Давайте с вами посмотрим на окрестности этих двух ребер. В окрестность ребра uv попадают вершины 1, 2, 3, поскольку они смежны с вершиной u, а кроме этого, вершина v', поскольку она смежна с вершиной v. Далее, в окрестность ребра u' и v' попадают вершины 2, 3, 4, поскольку они смежны с вершиной u', а также вершины 1 и v, которые смежны с вершиной v'. Что мы с вами имеем? Мы с вами имеем две различные окрестности, даже мощности у них различны: в первом случае 4, во втором 5. И этот факт нам говорит о том, что не существует автоморфизма, переводящего одно ребро в другое. Теперь давайте мы с вами рассмотрим связь между вершинно-транзитивными и дистанционно-регулярными графами, которые были введены в первом модуле нашего цикла. Напомню, что связный k-регулярный граф называется дистанционно-регулярным с заданным массивом пересечений, если для любого i параметры этого массива пересечений bi и ci не зависят от выбора пары вершин, находящихся на расстоянии i. Если вы забыли, как определяются параметры bi и ci, то, пожалуйста, пересмотрите соответствующую лекцию первого модуля. А теперь мы возвращаемся к этой связи — связи между вершинно-транзитивными и дистанционно-регулярными графами. Тут возможны все варианты. Простейшими примерами вершинно-транзитивных и дистанционно-регулярных графов являются полные графы на n вершинах, цикл длины n, граф Петерсена. К более сложным относятся графы Хэмминга и графы Джонсона. И мы будем о них говорить в нашем курсе в самом конце. В самом конце мы также поговорим с вами о классе графов Кнезера, среди которых имеются примеры вершинно-транзитивных, но не дистанционно-регулярных графов. И наконец среди графов Мура, которые были введены также в первом модуле нашего цикла, возможно существование дистанционно-регулярного графа, который не будет являться вершинно-транзитивным. Это граф Мура с обхватом 5 и степенью 57. До сих пор неизвестно существование такого графа, но зато доказано, что если такой граф будет найден, то он будет являться примером дистанционно-регулярного, но не вершинно-транзитивного графа. Вот на этой открытой математической современной проблеме мы и завершаем с вами сегодняшнюю лекцию. В следующий раз мы с вами поговорим о дистанционно-транзитивных графах.