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

График грамм и соответствующий симплекс-граф κ (грамм). Узел синего цвета в κ (грамм) соответствует клике с нулевой вершиной в грамм (пустое множество), а пурпурный узел соответствует 3-вершинной клике.

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

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

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

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

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

Примечания

  1. ^ Бартелеми, Леклерк и Монжарде (1986), стр.200.
  2. ^ Пропп (1997).
  3. ^ Имрих, Клавжар и Малдер (1999) Следует отметить введение симплексных графов в более позднюю работу, также Бандельта и Ван де Веля, но это, похоже, ошибка.

Рекомендации

  • Bandelt, H.J .; Чепой, В. (2008), "Метрическая теория графов и геометрия: обзор", в Гудман, Дж.; Pach, J .; Поллак, Р. (ред.), Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя, Contemp. Математика, 453, Провиденс, Род-Айленд: AMS, стр. 49–86..
  • Bandelt, H.J .; ван де Вель, М. (1989), «Вложение топологических медианных алгебр в произведения дендронов», Труды Лондонского математического общества, s3-58 (3): 439–453, Дои:10.1112 / плмс / с3-58.3.439.
  • Barthélemy, J.P .; Leclerc, B .; Монжарде, Б. (1986), "Об использовании упорядоченных множеств в задачах сравнения и консенсуса классификаций", Журнал классификации, 3 (2): 187–224, Дои:10.1007 / BF01894188.
  • Имрих, Вильфрид; Клавжар, Санди; Малдер, Генри Мартин (1999), «Медианные графы и графы без треугольников», Журнал SIAM по дискретной математике, 12 (1): 111–118, CiteSeerX  10.1.1.28.5906, Дои:10.1137 / S0895480197323494, МИСТЕР  1666073.
  • Пропп, Джеймс (1997), "Создание случайных элементов конечных распределительных решеток", Электронный журнал комбинаторики, 4 (2): R15, arXiv:math.CO/9801066.