Два графа - Two-graph

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

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

Примеры

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

123 124 135 146 156 236 245 256 345 346

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

Учитывая простой график грамм = (V,E) множество троек множества вершин V чей индуцированный подграф имеет нечетное число ребер, образует двумерный граф на множестве V. Таким образом можно представить любой двумерный граф.^[1] Этот пример называется стандартным построением двухграфа из простого графа.

В качестве более сложного примера пусть Т быть деревом с множеством ребер E. Набор всех троек E которые не содержатся в пути Т образуют двумерный граф на множестве E.^[2]

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

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

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

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

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

Пусть Γ - двумерный граф на множестве Икс. Для любого элемента Икс из Икс, определим граф с множеством вершин Икс имеющий вершины у и z смежно тогда и только тогда, когда {Икс, у, z} находится в Γ. На этом графике Икс будет изолированной вершиной. Эта конструкция обратима; учитывая простой график грамм, примыкаем к новому элементу Икс множеству вершин грамм и определим двумерный граф, все тройки которого суть {Икс, у, z} куда у и z смежные вершины в грамм. Этот двух-граф называется расширение из грамм к Икс в язык теории дизайна.^[3] Пусть в заданном переключающем классе графов регулярного двухграфа Γ_Икс уникальный граф, имеющий Икс как изолированную вершину (она всегда существует, просто возьмите любой граф в классе и переключите открытую окрестность Икс) без вершины Икс. То есть двуграф является расширением Γ_Икс к Икс. В первом приведенном выше примере регулярного двумерного графа Γ_Икс это 5-цикл для любого выбора Икс.^[4]

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

Переключение грамм и Σ связаны: переключение одних и тех же вершин в обеих дает граф ЧАС и соответствующий ему полный граф со знаком.

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

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

Если графики грамм и ЧАС принадлежат к одному классу переключения, мультимножества собственных значений двух Матрицы смежности Зейделя из грамм и ЧАС совпадают, поскольку матрицы подобны.^[5]

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

Равноугольные линии

Каждый двумерный граф эквивалентен набору линий некоторой размерности. евклидово пространство каждая пара встречается под одним углом. Множество линий, построенных из двух графов на п вершины получается следующим образом. Пусть -ρ наименьшее собственное значение из Матрица смежности Зейделя, А, двумерного графа, и предположим, что он имеет кратность п - d. Тогда матрица ρя + А положительно полуопределенный ранг d и поэтому может быть представлен как Матрица Грама внутренних продуктов п векторы на евклидовом языке d-Космос. Поскольку эти векторы имеют одинаковые норма (а именно, ${ displaystyle { sqrt { rho}}}$ ) и взаимные скалярные произведения ± 1, любая пара п натянутые на них прямые пересекаются под одним углом φ, где cos φ = 1 / ρ. И наоборот, любой набор неортогональных равноугольных линий в евклидовом пространстве может дать начало двухграфу (см. равносторонние линии для строительства).^[7]

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

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

Двухграфы на Икс состоящий из всевозможных троек Икс и никаких троек Икс являются регулярными двуграфами и считаются банальный двухграфы.

Для нетривиальных двух-графов на множестве Икс, двумерный граф является регулярным тогда и только тогда, когда для некоторого Икс в Икс граф Γ_Икс это сильно регулярный граф с k = 2μ (степень любой вершины в два раза больше числа вершин, смежных с обеими из любой несмежной пары вершин). Если это условие выполняется для одного Икс в Икс, это справедливо для всех элементов Икс.^[8]

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

Если грамм - регулярный граф, расширение двух графов которого - это Γ, имеющий п точек, то Γ является правильным двуграфом тогда и только тогда, когда грамм является сильно регулярным графом с собственными значениями k, р и s удовлетворение п = 2(k - р) или же п = 2(k - s).^[9]

Примечания

^ Колберн и Диниц 2007, п. 876, замечание 13.2
^ Кэмерон, П.Дж. (1994), "Два-графа и деревья", Дискретная математика, 127: 63–74, Дои:10.1016 / 0012-365x (92) 00468-7 цитируется в Колберн и Диниц 2007, п. 876, Строительство 13.12
^ Кэмерон и ван Линт 1991, стр. 58-59
^ Кэмерон и ван Линт 1991, п. 62
^ Кэмерон и ван Линт 1991, п. 61
^ Колберн и Диниц 2007, п. 878 # 13.24
^ van Lint & Seidel 1966 г.
^ Кэмерон и ван Линт 1991, п. 62 Теорема 4.11.
^ Кэмерон и ван Линт 1991, п. 62 Теорема 4.12.