Два-граф (:fg-ijgs)

В математике два-граф это (неупорядоченное) множество троек, выбранных из конечного множества вершин X таким образом, что любая (неупорядоченная) четвёрка из X содержит чётное число выбранных троек два-графа. В регулярном (однородном) два-графе любая пара вершин лежит в одном и том же числе троек два-графа. Два-графы изучаются ввиду их связи с равноугольными прямыми, связи регулярных два-графов с сильно регулярными графами, а также ввиду связи регулярных два-графов с конечными группами, поскольку многие из этих графов имеют интересные группы автоморфизмов.

Два-графы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».

Два-графы были введены Хигманом (G. Higman) как естественные объекты, возникающие при работе с некоторыми простыми группами. С тех пор их изучали интенсивно Зайдель, Тэйлор и другие при изучении множеств равноугольных прямых, сильно регулярных графов и других объектов.

Примеры

На множестве вершин {1, ..., 6} следующий неупорядоченный набор троек является два-графом:

123  124  135  146  156  236  245  256  345  346

Этот два-граф является регулярным, поскольку любая пара различных вершин оказывается вместе в точности в двух тройках.

Если дан обычный граф G = (V, E), то набор троек вершин из V, у которых порождённый подграф имеет нечётное число рёбер, образует два-граф на V. Любой два-граф можно представить в таком виде. Этот пример показывает стандартный путь построения два-графа из обычного графа.

Приведём более сложный пример. Пусть T — дерево с множеством рёбер E. Множество всех троек рёбер, не лежащих на одном пути в T образуют два-граф на множествеt E.

Переключение и графы

Переключение {X,Y} в графе

Два-граф эквивалентен классу переключения графов, а также (знаковому) классу переключения знаковых полных графов.

Переключение множества вершин в (обычном) графе означает смену смежности каждой пары вершин, одна из которых в множестве, а другая не в множестве — смежная пара становится несмежной, а несмежная пара становится смежной. Рёбра, конечные вершины которых находятся в множестве, или оба конца находятся вне множества, не меняются. Графы являются эквивалентными по переключению, если один может быть получен из другого путём переключения. Класс эквивалентности по переключению называется классом переключения. Переключение было введено Ван Линтом и Зайделем (van Lint, Seidel 1966) и развито Зайделем. Название переключение графов или переключение Зайделя было введено, в частности, чтобы отличить от переключения знаковых графов.

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

Пусть Γ — два-граф на множестве X. Для любого элемента x из X определим граф с множеством вершин X, в котором вершины y и z смежны в том и только том случае, когда {x, y, z} принадлежит Γ. В этом графе x будет изолированной вершиной. Это построение обратимо. Если задан обычный граф G, добавим новый элемент x к множеству вершин G и определим два-граф, во всех тройках {x, y, z} которого вершины y и z являются смежными вершинами в G. Этот два-граф на языке блок-схем называется расширением графа G вершиной x. В заданном классе переключения регулярного два-графа пусть Γ_x — единственный граф, имеющий вершину x как изолированную (таковой всегда существует, просто нужно взять любой граф в классе и переключить относительно несмежных x вершин), и не включающий саму вершину x. То есть, два-граф является расширением Γ_x вершиной x. В примере регулярного два-графа Γ_x является циклом из 5 вершин для любого выбора x.

Графу G соответствует знаковый полный граф Σ на том же множестве вершин, рёбра которого отрицательны, если принадлежат G, и положительны, если не принадлежат G. И обратно, G является подграфом Σ и состоит из всех вершин и отрицательных рёбер. Два-граф G можно определить также как множество троек вершин, которые образуют отрицательный треугольник (треугольник с нечётным числом отрицательных рёбер) в Σ. Два знаковых полных графа дают тот же самый два-граф в том и только том случае, если они эквивалентны по переключению.

Переключения G и Σ связаны — переключение одних и тех же вершин даёт граф H и соответствующий ему знаковый полный граф.

Матрица смежности

Матрица смежности два-графа это матрица смежности соответствующего знакового полного графа. То есть, она симметрична, имеет нули на диагонали, и значения вне диагонали равны ±1. Если G является графом, соответствующим знаковому полному графу Σ, эта матрица называется (0, −1, 1) матрицей смежности или матрицей смежности Зайделя графа G. Матрица Зайделя имеет нули на главной диагонали, −1 для элементов, соответствующих смежным вершинам, и +1 для элементов, соответствующих несмежным вершинам.

Если графы G и H находятся в одном классе переключения, мультимножества собственных значений двух матриц смежности Зайделя для G и H совпадают, поскольку матрицы подобны.

Два-граф на множестве V является регулярным в том и только том случае, если её матрица смежности имеет только два различных собственных значения, скажем ρ₁ > 0 > ρ₂, где ρ₁ρ₂ = 1 − |V|.

Равноугольные прямые

Основная статья: Равноугольные прямые

Любой два-граф эквивалентен множеству прямых в некотором многомерном евклидовом пространстве, и угол между любой парой прямых из этого множества один и тот же. Множество прямых можно построить из два-графа с n вершинами следующим образом. Пусть −ρ — наименьшее собственное значение матрицы смежности Зайделя A два-графа, и предположим, что его кратность равна n − d. Тогда матрица ρI + A является положительно полуопределённой матрицей ранга d, и её можно представить как матрицу Грама скалярных произведений n векторов в евклидовом пространстве размерности d. Эти вектора также имеют одну и ту же норму (а именно, ${\sqrt {\rho }}$) и попарное скалярное произведение ±1, а угол между любой парой из n прямых, натянутых на эти вектора, равен φ, где cos φ = 1/ρ. Обратно, любое множество неортогональных прямых в евклидовом пространстве, угол между любой парой которых одинаков, даёт два-граф.

В обозначениях, приведённых выше, максимальная мощность n удовлетворяет неравенству n ≤ d(ρ² − 1)/(ρ² − d), и граница достигается в том и только том случае, когда два-граф регулярен.

Сильно регулярные графы

Основная статья: Сильно регулярный граф

Два-графы на X, состоящие из всех возможных троек из X, и пустые (не имеющие троек) являются регулярными два-графами, но их принято считать тривиальными два-графами и, как правило, они исключаются из рассмотрения.

Нетривиальный два-граф на множестве X является регулярным тогда и только тогда, когда для любого x из X граф Γ_x является сильно регулярным с k = 2μ (степень любой вершины вдвое больше числа вершин, смежных обеим из любой несмежной пары вершин). Если это условие выполняется для одного x из X, оно выполняется для всех элементов из X.

Отсюда следует, что нетривиальный регулярный два-граф имеет чётное число вершин.

Если G является регулярным графом, расширенный два-граф Γ которого имеет n вершин, то Γ является регулярным два-графом в том и только том случае, когда G является сильно регулярным графом с собственными значениями k, r и s, для которых выполняется n = 2(k − r) или n = 2(k − s).

Литература

• A. E. Brouwer, A. M. Cohen, A. Neumaier. Параграфы 1.5, 3.8, 7.6C // Distance-Regular Graphs. — Berlin: Springer-Verlag, 1989.

• P. J. Cameron, J. H. van Lint. Designs, Graphs, Codes and their Links. — Cambridge University Press, 1991. — Т. 22. — (London Mathematical Society Student Texts). — ISBN 978-0-521-42385-4.

• Charles J. Colbourn, Jeffrey H. Dinitz. Handbook of Combinatorial Designs. — 2nd. — Boca Raton: Chapman & Hall/ CRC, 2007. — С. 875—882. — ISBN 1-58488-506-8.

• Chris Godsil, Gordon Royle. Глава 11 // Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics).

• J. J. Seidel. Colloquio Internazionale sulle Teorie Combinatorie. — Rome, 1973. — Т. I. — С. 481—511.

• D. E. Taylor. Proceedings of the London Mathematical Society. — 1977. — Т. 35. — С. 257—274.

• J. H. van Lint, J. J. Seidel. Equilateral point sets in elliptic geometry // Indagationes Mathematicae. — 1966. — Т. 28. — С. 335—348.