Введение
В математике, двуграф — это множество (неупорядоченных) троек, выбранных из конечного множества вершин X, таких что каждая (неупорядоченная) четверка из X содержит четное число троек двуграфа. Регулярный двуграф обладает свойством, что каждая пара вершин содержится в одинаковом количестве троек двуграфа. Двуграфы изучались из-за их связи с эквиангулярными прямыми и, для регулярных двуграфов, со сильно регулярными графами, а также с конечными группами, поскольку многие регулярные двуграфы имеют интересные группы автоморфизмов. Двуграф не является графом и не следует путать с другими объектами, называемыми 2-графами в теории графов, такими как 2-регулярные графы.
Переключение и графики
Двухграф эквивалентен переключающемуся классу графов, а также (подписанному) переключающемуся классу подписанных полных графов. Переключение множества вершин в (простом) графе означает изменение связности каждой пары вершин, одна из которых входит в это множество, а другая – нет: таким образом, множество ребер изменяется так, что смежная пара становится несмежной, а несмежная пара – смежной. Ребра, концы которых находятся либо оба в множестве, либо оба вне его, не изменяются. Графы являются переключающимися эквивалентами, если один из них можно получить из другого переключением. Класс эквивалентности графов относительно переключения называется переключающим классом. Переключение было введено и развито Зайделем; его также называют переключением графов или переключением Зайделя, отчасти для того, чтобы отличать его от переключения подписанных графов. В стандартной конструкции двухграфа из простого графа, описанной выше, два графа дадут один и тот же двухграф тогда и только тогда, когда они эквивалентны относительно переключения, то есть принадлежат одному и тому же переключающему классу. Пусть Γ – двухграф на множестве X. Для любого элемента x из X определим граф с множеством вершин X, в котором вершины y и z смежны тогда и только тогда, когда {x, y, z} принадлежит Γ. В этом графе вершина x будет изолированной. Эта конструкция обратима; заданному простому графу G присоединим новый элемент x к множеству его вершин, сохраняя тот же набор ребер, и применим стандартную конструкцию, описанную выше. Этот двухграф называется расширением 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 является регулярным тогда и только тогда, когда его матрица смежности имеет ровно два различных собственных значения ρ1 > 0 > ρ2, например, таких, что ρ1ρ2 = |V|.
Равныхугольные линии
Каждый двухдольный граф эквивалентен набору прямых в некотором евклидовом пространстве, каждая пара которых пересекается под одним и тем же углом. Набор прямых, построенных из двухдольного графа на n вершинах, получается следующим образом. Пусть ρ – наименьшее собственное значение матрицы смежности Зайделя, A, этого двухдольного графа, и предположим, что его кратность равна d. Тогда матрица (1/ρ)I + A является положительно полуопределенной и имеет ранг d, и, следовательно, может быть представлена как матрица Грама скалярных произведений n векторов в d-мерном евклидовом пространстве. Поскольку эти векторы имеют одинаковую норму (а именно, ) и взаимные скалярные произведения равны ±1, любая пара из n прямых, заданных этими векторами, пересекается под одним и тем же углом φ, где cos φ = 1/ρ. Обратно, любой набор неортогональных равноугольных прямых в евклидовом пространстве может породить двухдольный граф (см. равноугольные прямые для построения). При указанных обозначениях максимальная мощность n удовлетворяет неравенству n ≤ d(ρ² – 1)/(ρ² – d), и эта граница достигается тогда и только тогда, когда двухдольный граф является регулярным.
Сильно регулярные графики
Два графа на X, состоящие из всех возможных троек из 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).