Симплексный график

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

Пустое множество включено как одна из клик графа G , которые используются для формирования графа клик, как и каждое множество из одной вершины и каждое множество из двух смежных вершин. Таким образом, симплексный граф содержит внутри себя подразделение самого графа G. Симплексный граф полного графа является графом гиперкуба , а симплексный граф графа цикла длины четыре или более является графом шестеренок . Симплексный граф графа дополнения графа пути является кубом Фибоначчи .

Полным подграфам графа G можно задать структуру медианной алгебры : медиана трех клик A , B и C образована вершинами, которые принадлежат большинству из трех клик. ^[1] Любые две вершины, принадлежащие этому медианному множеству, должны обе принадлежать по крайней мере одной из A , B или C и, следовательно, должны быть связаны ребром, поэтому медиана трех клик сама по себе является кликой. Симплексный граф является медианным графом, соответствующим этой структуре медианной алгебры. Когда G является дополнительным графом двудольного графа , кликам графа G можно задать более сильную структуру в виде дистрибутивной решетки , ^[2] и в этом случае симплексный граф является графом решетки. Как и в случае медианных графов в более общем случае, каждый симплексный граф сам по себе является двудольным .

Симплексный граф имеет одну вершину для каждого симплекса в кликовом комплексе X ( G ) графа G , и две вершины связаны ребром, когда один из двух соответствующих симплексов является гранью другого. Таким образом, объекты (вершины в симплексном графе, симплексы в X ( G ) ) и отношения между объектами (ребра в симплексном графе, отношения включения между симплексами в X ( G ) ) находятся во взаимно-однозначном соответствии между X ( G ) и κ( G ) .

Симплексные графы были введены Бандельтом и ван де Велем (1989), ^[3], которые заметили, что симплексный граф не имеет кубов тогда и только тогда, когда базовый граф не содержит треугольников , и показали, что хроматическое число базового графа равно минимальному числу n, такому, что симплексный граф может быть изометрически вложен в декартово произведение n деревьев . Вследствие существования графов без треугольников с высоким хроматическим числом они показали, что существуют двумерные топологические медианные алгебры , которые не могут быть вложены в произведения конечного числа действительных деревьев . Имрих, Клавжар и Малдер (1999) также используют симплексные графы как часть своего доказательства того, что проверка того, является ли граф свободным от треугольников или является ли он медианным графом, может быть выполнена одинаково быстро.

• Bandelt, H.-J.; Chepoi, V. (2008), «Метрическая теория графов и геометрия: обзор», в Goodman, JE ; Pach, J.; Pollack, R. (ред.), Обзоры дискретной и вычислительной геометрии: двадцать лет спустя , Contemp . Math., т. 453, Providence, RI: AMS, стр.  49–86.
• Бандельт, Х.-Й.; ван де Вел, М. (1989), «Вложение топологических медианных алгебр в произведения дендронов», Труды Лондонского математического общества , s3-58 (3): 439– 453, doi :10.1112/plms/s3-58.3.439, архивировано из оригинала 2013-04-15.
• Бартелеми, Ж.-П.; Леклерк, Б.; Монжарде, Б. (1986), «Об использовании упорядоченных множеств в задачах сравнения и консенсуса классификаций», Журнал классификации , 3 (2): 187– 224, doi :10.1007/BF01894188, S2CID  6092438.
• Имрих, Вильфрид; Клавжар, Сэнди; Малдер, Генри Мартин (1999), «Медианные графы и графы без треугольников», SIAM Journal on Discrete Mathematics , 12 (1): 111– 118, CiteSeerX  10.1.1.28.5906 , doi :10.1137/S0895480197323494, MR  1666073.
• Пропп, Джеймс (1997), «Генерация случайных элементов конечных дистрибутивных решеток», Электронный журнал комбинаторики , 4 (2): R15, arXiv : math.CO/9801066 , doi : 10.37236/1330, S2CID  13313188.