Русская Википедия:Два-граф
В математике два-граф это (неупорядоченное) множество троек, выбранных из конечного множества вершин X таким образом, что любая (неупорядоченная) четвёрка из X содержит чётное число выбранных троек два-графа. В регулярном (однородном) два-графе любая пара вершин лежит в одном и том же числе троек два-графа. Два-графы изучаются ввиду их связи с равноугольными прямыми, связи регулярных два-графов с сильно регулярными графами, а также ввиду связи регулярных два-графов с конечными группами, поскольку многие из этих графов имеют интересные группы автоморфизмов.
Два-графы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2»[1].
Два-графы были введены Хигманом (G. Higman) как естественные объекты, возникающие при работе с некоторыми простыми группами. С тех пор их изучали интенсивно Зайдель, Тэйлор и другие при изучении множеств равноугольных прямых, сильно регулярных графов и других объектов[2][1].
Примеры
На множестве вершин {1, ..., 6} следующий неупорядоченный набор троек является два-графом:
- 123 124 135 146 156 236 245 256 345 346
Этот два-граф является регулярным, поскольку любая пара различных вершин оказывается вместе в точности в двух тройках.
Если дан обычный граф G = (V, E), то набор троек вершин из V, у которых порождённый подграф имеет нечётное число рёбер, образует два-граф на V. Любой два-граф можно представить в таком виде[3]. Этот пример показывает стандартный путь построения два-графа из обычного графа.
Приведём более сложный пример. Пусть T — дерево с множеством рёбер E. Множество всех троек рёбер, не лежащих на одном пути в T образуют два-граф на множествеt E.[4][5]
Переключение и графы
Два-граф эквивалентен классу переключения графов, а также (знаковому) классу переключения Шаблон:Не переведено 5.
Переключение множества вершин в (обычном) графе означает смену смежности каждой пары вершин, одна из которых в множестве, а другая не в множестве — смежная пара становится несмежной, а несмежная пара становится смежной. Рёбра, конечные вершины которых находятся в множестве, или оба конца находятся вне множества, не меняются. Графы являются эквивалентными по переключению, если один может быть получен из другого путём переключения. Класс эквивалентности по переключению называется классом переключения. Переключение было введено Ван Линтом и Зайделем Шаблон:Harv и развито Зайделем. Название переключение графов или переключение Зайделя было введено, в частности, чтобы отличить от переключения Шаблон:Не переведено 5.
В стандартном построении два-графов из обычного графа, данном выше, два графа дают тот же самый два-граф в том и только том случае, когда они эквивалентны по переключению, то есть, они принадлежат тому же классу переключения.
Пусть Γ — два-граф на множестве X. Для любого элемента x из X определим граф с множеством вершин X, в котором вершины y и z смежны в том и только том случае, когда {x, y, z} принадлежит Γ. В этом графе x будет изолированной вершиной. Это построение обратимо. Если задан обычный граф G, добавим новый элемент x к множеству вершин G и определим два-граф, во всех тройках {x, y, z} которого вершины y и z являются смежными вершинами в G. Этот два-граф на языке блок-схем называется расширением графа G вершиной x.[1] В заданном классе переключения регулярного два-графа пусть Γx — единственный граф, имеющий вершину x как изолированную (таковой всегда существует, просто нужно взять любой граф в классе и переключить относительно несмежных x вершин), и не включающий саму вершину x. То есть, два-граф является расширением Γx вершиной x. В примере регулярного два-графа Γx является циклом из 5 вершин для любого выбора x.[6]
Графу G соответствует знаковый полный граф Σ на том же множестве вершин, рёбра которого отрицательны, если принадлежат G, и положительны, если не принадлежат G. И обратно, G является подграфом Σ и состоит из всех вершин и отрицательных рёбер. Два-граф G можно определить также как множество троек вершин, которые образуют отрицательный треугольник (треугольник с нечётным числом отрицательных рёбер) в Σ. Два знаковых полных графа дают тот же самый два-граф в том и только том случае, если они эквивалентны по переключению.
Переключения G и Σ связаны — переключение одних и тех же вершин даёт граф H и соответствующий ему знаковый полный граф.
Матрица смежности
Матрица смежности два-графа это Шаблон:Не переведено 5 соответствующего знакового полного графа. То есть, она симметрична, имеет нули на диагонали, и значения вне диагонали равны ±1. Если G является графом, соответствующим знаковому полному графу Σ, эта матрица называется (0, −1, 1) матрицей смежности или Шаблон:Не переведено 5 графа G. Матрица Зайделя имеет нули на главной диагонали, −1 для элементов, соответствующих смежным вершинам, и +1 для элементов, соответствующих несмежным вершинам.
Если графы G и H находятся в одном классе переключения, мультимножества собственных значений двух Шаблон:Не переведено 5 для G и H совпадают, поскольку матрицы подобны.[7]
Два-граф на множестве V является регулярным в том и только том случае, если её матрица смежности имеет только два различных собственных значения, скажем ρ1 > 0 > ρ2, где ρ1ρ2 = 1 − |V|.[8]
Равноугольные прямые
Любой два-граф эквивалентен множеству прямых в некотором многомерном евклидовом пространстве, и угол между любой парой прямых из этого множества один и тот же. Множество прямых можно построить из два-графа с n вершинами следующим образом. Пусть −ρ — наименьшее собственное значение Шаблон:Не переведено 5 A два-графа, и предположим, что его кратность равна n − d. Тогда матрица ρI + A является положительно полуопределённой матрицей ранга d, и её можно представить как матрицу Грама скалярных произведений n векторов в евклидовом пространстве размерности d. Эти вектора также имеют одну и ту же норму (а именно, <math>\sqrt{\rho}</math>) и попарное скалярное произведение ±1, а угол между любой парой из n прямых, натянутых на эти вектора, равен φ, где cos φ = 1/ρ. Обратно, любое множество неортогональных прямых в евклидовом пространстве, угол между любой парой которых одинаков, даёт два-граф[9].
В обозначениях, приведённых выше, максимальная мощность n удовлетворяет неравенству n ≤ d(ρ2 − 1)/(ρ2 − d), и граница достигается в том и только том случае, когда два-граф регулярен.
Сильно регулярные графы
Два-графы на X, состоящие из всех возможных троек из X, и пустые (не имеющие троек) являются регулярными два-графами, но их принято считать тривиальными два-графами и, как правило, они исключаются из рассмотрения.
Нетривиальный два-граф на множестве X является регулярным тогда и только тогда, когда для любого x из X граф Γx является сильно регулярным с k = 2μ (степень любой вершины вдвое больше числа вершин, смежных обеим из любой несмежной пары вершин). Если это условие выполняется для одного x из X, оно выполняется для всех элементов из X.[10]
Отсюда следует, что нетривиальный регулярный два-граф имеет чётное число вершин.
Если G является регулярным графом, расширенный два-граф Γ которого имеет n вершин, то Γ является регулярным два-графом в том и только том случае, когда G является сильно регулярным графом с собственными значениями k, r и s, для которых выполняется n = 2(k − r) или n = 2(k − s).[11]
Примечания
Литература
- ↑ 1,0 1,1 1,2 Шаблон:Harvnb, с. 58—59.
- ↑ Шаблон:Статья
- ↑ Шаблон:Harvnb, с. 876, примечание 13.2.
- ↑ Шаблон:Статья, как цитировано у Шаблон:Harvnb, с. 876, заключение 13.12.
- ↑ Шаблон:Статья
- ↑ Шаблон:Harvnb, с. 62.
- ↑ Шаблон:Harvnb, с. 61.
- ↑ Шаблон:Harvnb, с. 878, #13.24.
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Harvnb, с. 62, теорема 4.11.
- ↑ Шаблон:Harvnb, с. 62, теорема 4.12.
