Распечатать запись Распечатать запись

Красота – редкая вещь

Здесь мы будем рассматривать графы. Напомним, что степенью вершины графа называется количество ребер, инцидентных этой вершине. Граф называется регулярным, если все его вершины имеют одинаковую степень. Обхватом графа называется наименьшая длина цикла в этом графе.

Рассмотрим графы обхвата 5. Какое наименьшее число вершин может иметь данный граф, если степень каждой его вершины равна r?

Возьмем вершину u. У нее r смежных вершин. Каждая из этих вершин имеет еще r-1 смежную вершину. Итак, имеем 1+r+r(r-1)=r^2+1 вершин. Они все должны быть различными, иначе появится цикл длины \le 4.

Возникает естественный вопрос: нужны ли нам еще вершины? Давайте посмотрим. Для r=2 имеем r^2+1=5, и получаем пятиугольник, один цикл длины 5. Для r=3 имеем r^2+1=10 вершин. Это опять-таки возможно. Такой граф единственен, и это граф Петерсена, который воистину замечателен большим количеством симметрий, или автоморфизмов (их 120):

Рисунок отсюда: http://ru.wikipedia.org/wiki/Граф_Петерсена

Для r=4,5,6 таких графов не существует. А вот для r=7 А. Хофман и Р. Синглетон в 1960 г. построили граф с 7^2+1=50 вершинами:

Рисунок отсюда: http://en.wikipedia.org/wiki/Hoffman–Singleton_graph

Однако, возможно, существует еще всего лишь один такой граф для r=573250 вершинами).

Теорема (Хофман, Сиглетон, 1960 г.). Если регулярный граф степени регулярности r и обхватом 5 содержит r^2+1 вершину, то r\in\{2,3,7,57\}.

Доказательство. Сначала выясним, сколько общих смежных вершин (т.е. вершин, которые соединены ребрами с вершинами u и v) может быть у двух вершин u и v такого графа {\cal G}. Если вершины u и v смежные, то у них не может быть общих смежных вершин, иначе у графа имелся бы цикл длины 3. Если же вершины u и v не смежные, то у них должна быть в точности одна общая смежная вершина, иначе число вершин графа превосходило бы r^2+1.

Свяжем с каждым графом (0,1)-матрицу n\times n — матрицу смежности. Элементы этой матрицы a_{ij} определим следующим образом:

a_{ij}=1, если вершины с номерами i и j смежные, и a_{ij}=0, если вершины с номерами i и j не смежные.

В частности, диагональные элементы матрицы A нулевые, и матрица A симметричная: A^T=A.

Легко заметить, что элементы матрицы A^2=\left[ b_{ij}\right] определяют число общих смежных вершин: b_{ij} равно числу общих смежных вершин для вершин i и j. В частности, диагональный элемент b_{ii} равен степени вершины i. Пусть \bar{A} обозначает матрицу смежности дополнительного графа (т.е. на тех местах, где у A стоят нули, у \bar{A} стоят единицы, и наоборот). Имеем

E+A+\bar{A}=J,

где E — единичная матрица порядка n, J — матрица порядка n, состоящая только из единиц, n=r^2+1 — число вершин графа.

Напомним, что в нашем графе смежные вершины не имеют общих смежных вершин, а несмежные вершины имеют ровно одну общую смежную вершину. В матричной форме это запишется так:

A^2=rE+\bar{A}.

Учитывая предыдущее равенство, получаем

A^2+A+(r-1)E=J.

Матрица A симметричная. Следовательно, существует ортогональный базис пространства \mathbb{R}^n, состоящий из ее собственных векторов. Обозначим через f вектор f=(1,1,\ldots,1)^T. Легко видеть, что для регулярного графа степени регулярности r

Af=rf,

т.е. f — собственный вектор, принадлежащий собственному числу r матрицы A. Теперь рассмотрим собственные векторы A, ортогональные f, т.е. векторы e: f^Te=0. Тогда и Je=\mathbb{O}. Поскольку e — собственный вектор A, имеем Ae=\lambda e. Домножим равенство с A^2 на e справа, получим

\lambda^2e+\lambda e-(r-1)e=\mathbb{O},

следовательно,

\lambda^2+\lambda-(r-1)=0.

Это уравнение имеет два корня

\displaystyle \lambda_{1,2}=\frac{-1\pm\sqrt{4r-3}}{2}.

Обозначим через m_i кратность корня \lambda_i (i=1,2). Сумма всех кратностей корней равна n, так что, не забывая собственный вектор f, имеем

1+m_1+m_2=n=r^2+1.

Поскольку сумма всех собственных чисел матрицы равна ее следу (т.е. сумме ее диагональных элементов), то получаем второе уравнение

r+m_1\lambda_1+m_2\lambda_2=0.

Подставим сюда выражения для \lambda_i:

2r-(m_1+m_2)+(m_1-m_2)s=0,

где s=\sqrt{4r-3}. Тогда, с первым уравнением вместе, имеем

2r-r^2+(m_1-m_2)s=0.

Заметим, что s — квадратный корень из натурального числа. Следовательно, это либо натуральное число, либо иррациональное число. В последнем случае m_1-m_2=0, и получаем уравнение 2r-r^2=0. Так как r\ne0, то r=2, и это дает пятиугольник.

Пусть теперь s — натуральное число. Выразим r через s: r=(s^2+3)/4. Тогда мы можем записать уравнение относительно s (раскрываем скобки и умножаем полученное уравнение на -16):

s^4-2s^2-16(m_1-m_2)s-15=0.

Возможные значения s — это лишь 1,3,5 и 15, поскольку натуральные корни являются делителями свободного члена. Находим соответствующие значения r=(s^2+3)/4=1,3,7,57. Отбрасываем 1, поскольку r\ge 2. Оставшиеся значения вместе с r=2 дают все возможные варианты.

Красивые графы — редкая вещь. И столь же редки такие красивые доказательства, как это.

Источник: László Babai, Péter Frankl, Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science, Preliminary Version 2 (September 1992), The University of Chicago.

Комментариев: 5

  1. 1 Корнеев В.Ф.:

    Не понял, почему граф Петерсена имеет 120 симметрий. Я насчитал только 5 осевых + одна центральная.

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Здесь имеются в виду автоморфизмы графа, т.е. отображения множества вершин на себя, сохраняющие смежность. Так, у пятиугольника 10 автоморфизмов: тождественное отображение, 4 поворота и 5 осевых симметрий. Поправила.

    [Ответить]

    Корнеев В.Ф. Reply:

    Может не симметрий, а движений. Тогда включатся и повороты, и повороты с симметрией. А автоморфизмы не сохраняют расстояний.

    [Ответить]

    Корнеев В.Ф. Reply:

    А, понял. Имеются в виду только вершины, а не весь пятиугольник. Значит автоморфизмы. И тогда их наберётся 120.

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Да, верно, только вершины и смежные ребра.

    [Ответить]

Оставьте свой отзыв

Добавить изображение