Interested Article - Два-граф

В математике два-граф это (неупорядоченное) множество троек, выбранных из конечного множества вершин 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 . Для любого элемента 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 ).

Примечания

↑ , с. 58—59.
G. Eric Moorhouse. Two-Graphs and Skew Two-Graphs in Finite Geometries // Linear Algebra and its Applications. — 1995.
, с. 876, примечание 13.2.
P. J. Cameron. Two-graphs and trees // Discrete Mathematics. — 1994. — Т. 127 . — С. 63—74 . — doi : . , как цитировано у , с. 876, заключение 13.12.
Peter J. Cameron. Counting two-graphs related and trees // The Electonic Journal of Combinatorics. — 1995. — Т. 2 . — ISSN .
, с. 62.
, с. 61.
, с. 878, #13.24.
, с. 62, теорема 4.11.
, с. 62, теорема 4.12.

Литература

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 .