Двухграфический

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

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

Примеры

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

123  124  135  146  156  236  245  256  345  346

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

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

В качестве более сложного примера пусть T дерево с множеством ребер E. — Множество всех троек E , не содержащихся в пути T, образует двойной граф на множестве E .

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

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

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

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

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

Пусть Γ — двуграф на множестве X . Для любого элемента x из X определите граф с множеством вершин X, имеющим смежные вершины y и z тогда и только тогда, когда { x , y , z } находится в Γ. В этом графе x будет изолированной вершиной. Эта конструкция обратима; учитывая простой граф G , присоедините новый элемент x к множеству вершин G , сохранив тот же набор ребер, и примените стандартную конструкцию, описанную выше. двухграф называется расширением G x посредством Этот на языке теории проектирования . В данном классе переключения графов регулярного двухграфа пусть Γ _x — единственный граф, имеющий x в качестве изолированной вершины (это всегда существует, просто возьмите любой граф в классе и поменяйте местами открытую окрестность x ) без вершины х . То есть двойной граф является расширением Γ _x посредством x . В первом примере регулярного двухграфа выше Γ _x является 5-циклом для любого выбора x .

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

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

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

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

Если графы и H находятся в одном классе переключения, мультимножества собственных значений двух матриц смежности Зейделя G G и H совпадают, поскольку матрицы подобны.

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

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

Основная статья: Равноугольные линии

Каждый двухграфик эквивалентен набору прямых в некотором размерном евклидовом пространстве, каждая пара которых пересекается под одним и тем же углом. Набор линий, построенный из двух графов на 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 граф Γ _x является сильно регулярным графом с k = 2μ (степень любой вершины в два раза больше числа вершин, смежных с обеими несмежными парами вершин). Если это условие выполняется для одного в X , оно выполняется для всех элементов X. x

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

Если G — регулярный граф, расширением которого на два графа является Γ, имеющий n точек, то Γ — регулярный граф с двумя графами тогда и только тогда, когда G — сильно регулярный граф с собственными значениями k , r и s, удовлетворяющими условиям n = 2( k - r ) или n = 2( k - s ).

Ссылки

• Брауэр А.Е. , Коэн А.М. и Ноймайер А. (1989), Дистанционно-регулярные графы. Шпрингер-Верлаг, Берлин. Разделы 1.5, 3.8, 7.6В.
• Кэмерон, Пи Джей; ван Линт, Дж. Х. (1991), Проекты, графики, коды и их связи , Тексты для студентов Лондонского математического общества 22, Cambridge University Press, ISBN  978-0-521-42385-4
• Колборн, Чарльз Дж; Корнейл, Дерек Г. (1980). «О решении коммутационной эквивалентности графов». Диск. Прил. Математика . 2 (3): 181–184. дои : 10.1016/0166-218X(80)90038-4 .
• Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007), Справочник по комбинаторным планам (2-е изд.), Бока-Ратон: Chapman & Hall/CRC, стр. 875–882 , ISBN  1-58488-506-8
• Годсил, Крис : Ройл, Гордон (2001), Алгебраическая теория графов. Тексты для аспирантов по математике, Vol. 207. Спрингер-Верлаг, Нью-Йорк. Глава 11.
• Маллоуз, CL; Слоан, Нью-Джерси (1975). «Два графа, классы переключения и графы Эйлера равны по количеству». СИАМ J. Appl. Математика . 28 (4): 876–880. CiteSeerX   10.1.1.646.5464 . JSTOR   2100368 .
• Зайдель, Дж.Дж. (1976), Обзор двух графов. В: Международный коллоквиум по комбинаторным теориям (Труды, Рим, 1973), Том I, стр. 481–511. Материалы Линцианских конференций, № 17. Национальная академия Линчеи, Рим. Перепечатано в Seidel (1991), стр. 146–176.
• Зайдель, Дж. Дж. (1991), Геометрия и комбинаторика: Избранные работы Дж. Дж. Зейделя , изд. Д. Г. Корней и Р. Матон. Академик Пресс, Бостон, 1991.
• Тейлор, DE (1977), Регулярные 2-графы. Труды Лондонского математического общества (3), том. 35, стр. 257–274.
• ван Линт, Дж. Х.; Зайдель, Дж. Дж. (1966), «Множества равносторонних точек в эллиптической геометрии», Indagationes Mathematicae , Proc. Конинкл. Нед. Акад. Ветеншап. Сер. А 69, 28 : 335–348.