В математике , two-граф - это набор неупорядоченных троек, выбранных из конечного множества вершин X , таким образом, что каждая неупорядоченная четверка из X содержит четное число троек two-графа. Правильный two-граф обладает тем свойством, что каждая пара вершин лежит в том же числе троек two-графа. Two-графы изучались из-за их связи с равноугольными линиями и, для правильных two-графов, сильно регулярными графами , а также конечными группами , поскольку многие правильные two-графы имеют интересные группы автоморфизмов .
Два-граф не является графом и его не следует путать с другими объектами, называемыми 2-графами в теории графов , такими как 2-регулярные графы .
На множестве вершин {1,...,6} следующий набор неупорядоченных троек является двумерным графом:
Этот двумерный граф является правильным двумерным графом, поскольку каждая пара различных вершин встречается вместе ровно в двух тройках.
Если задан простой граф G = ( V , E ), то множество троек множества вершин V , индуцированный подграф которого имеет нечетное число ребер, образует двуграф на множестве V . Каждый двуграф может быть представлен таким образом. [1] Этот пример называется стандартным построением двуграфа из простого графа.
В качестве более сложного примера, пусть T будет деревом с множеством ребер E. Множество всех троек E , которые не содержатся в пути T, образуют двумерный граф на множестве E. [2 ]
Два графа эквивалентны коммутационному классу графов, а также (знаковому) коммутационному классу знаковых полных графов .
Переключение набора вершин в (простом) графе означает изменение смежности каждой пары вершин, одна из которых входит в набор, а другая нет: таким образом, набор ребер изменяется так, что смежная пара становится несмежной, а несмежная пара становится смежной. Ребра, конечные точки которых обе находятся в наборе или обе не находятся в наборе, не изменяются. Графы являются эквивалентными по переключению, если один из них может быть получен из другого путем переключения. Класс эквивалентности графов при переключении называется классом переключения . Переключение было введено ван Линтом и Зайделем (1966) и разработано Зайделем; оно было названо переключением графа или переключением Зайделя , отчасти для того, чтобы отличить его от переключения знаковых графов .
В стандартном построении двумерного графа из простого графа, приведенного выше, два графа дадут один и тот же двумерный граф тогда и только тогда, когда они эквивалентны относительно переключения, то есть они находятся в одном классе переключения.
Пусть Γ будет двумерным графом на множестве X. Для любого элемента x из X определим граф с множеством вершин X, имеющим вершины y и z смежными тогда и только тогда, когда { x , y , z } принадлежит Γ. В этом графе x будет изолированной вершиной. Эта конструкция обратима; если задан простой граф G , присоединим новый элемент x к множеству вершин G , сохранив тот же набор ребер, и применим стандартную конструкцию выше. Этот двумерный граф называется расширением G с помощью x на языке теории дизайна . [3] В заданном классе переключения графов регулярного двумерного графа пусть Γ x будет единственным графом, имеющим x в качестве изолированной вершины (такой всегда существует, просто возьмите любой граф в классе и переключите открытую окрестность x ) без вершины x . То есть двумерный граф является расширением Γ x с помощью x . В первом примере выше регулярного 2-графа Γ x является 5-циклом для любого выбора x . [4]
Графу G соответствует знаковый полный граф Σ на том же множестве вершин, чьи ребра имеют отрицательный знак, если они в G , и положительный знак, если они не в G. Наоборот, G — это подграф Σ, состоящий из всех вершин и всех отрицательных ребер. Два-граф графа G также можно определить как множество троек вершин, которые поддерживают отрицательный треугольник (треугольник с нечетным числом отрицательных ребер) в Σ. Два знаковых полных графа дают один и тот же два-граф тогда и только тогда, когда они эквивалентны относительно переключения.
Переключение G и Σ взаимосвязано: переключение одних и тех же вершин в обоих графах даёт граф H и соответствующий ему знаковый полный граф.
Матрица смежности двухграфа является матрицей смежности соответствующего знакового полного графа; таким образом, она симметрична , равна нулю на диагонали и имеет элементы ±1 вне диагонали. Если G является графом, соответствующим знаковому полному графу Σ, эта матрица называется матрицей (0, −1, 1)-смежности или матрицей смежности Зейделя для G. Матрица Зейделя имеет нулевые элементы на главной диагонали, -1 элементы для смежных вершин и +1 элементы для несмежных вершин.
Если графы G и H находятся в одном и том же классе переключения, мультимножества собственных значений двух матриц смежности Зейделя графов G и H совпадают, поскольку матрицы подобны. [5]
Два-граф на множестве V является регулярным тогда и только тогда, когда его матрица смежности имеет всего два различных собственных значения ρ 1 > 0 > ρ 2 , скажем, где ρ 1 ρ 2 = 1 - | V |. [6]
Каждый 2-граф эквивалентен набору прямых в некотором размерном евклидовом пространстве, каждая пара которых пересекается под одним и тем же углом. Набор прямых, построенных из 2-графа на n вершинах, получается следующим образом. Пусть -ρ будет наименьшим собственным значением матрицы смежности Зейделя , A , 2-графа, и предположим, что она имеет кратность n - d . Тогда матрица ρ I + A является положительно полуопределенной ранга d и, таким образом, может быть представлена как матрица Грама скалярных произведений n векторов в евклидовом d -пространстве. Поскольку эти векторы имеют одинаковую норму (а именно, ) и взаимные скалярные произведения ±1, любая пара из n прямых, натянутых на них, пересекается под одним и тем же углом φ, где cos φ = 1/ρ. Наоборот, любой набор неортогональных равноугольных прямых в евклидовом пространстве может привести к 2-графу (см. равноугольные прямые для построения). [7]
При использовании обозначений, указанных выше, максимальная мощность n удовлетворяет условию n ≤ d (ρ 2 - 1)/(ρ 2 - d ), и граница достигается тогда и только тогда, когда двумерный граф является регулярным.
Два-графы на X, состоящие из всех возможных троек X и не содержащие троек X, являются регулярными два-графами и считаются тривиальными два-графами.
Для нетривиальных 2-графов на множестве X 2-граф является регулярным тогда и только тогда, когда для некоторого x из X граф Γ x является сильно регулярным графом с k = 2μ (степень любой вершины в два раза больше числа вершин, смежных с обеими из любой несмежной пары вершин). Если это условие выполняется для одного x из X , оно выполняется для всех элементов X . [8]
Отсюда следует, что нетривиальный регулярный два-граф имеет четное число точек.
Если G — регулярный граф, двуграфовое расширение которого — это Γ, имеющее n точек, то Γ является регулярным двуграфом тогда и только тогда, когда G — сильно регулярный граф с собственными значениями k , r и s, удовлетворяющими n = 2( k - r ) или n = 2( k - s ). [9]
