WikiDer > Токсичность

Boxicity
График пересечений прямоугольников с квадратичностью два

В теория графов, коробочка это инвариант графа, представлен Фред С. Робертс в 1969 г.

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

Примеры

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

Робертс (1969) показал, что график с 2п вершины, образованные удалением идеальное соответствие из полный график на 2п вершины имеют прямоугольность ровно п: каждая пара несвязных вершин должна быть представлена ​​блоками, которые разделены в другом измерении, чем каждая другая пара. Коробочное представление этого графа с размером точно п можно найти, утолщив каждый из 2п грани п-размерный гиперкуб в коробку. Из-за этих результатов этот график был назван Граф Робертса,[1] хотя он более известен как график коктейльной вечеринки и это также можно понимать как График Турана Т(2п,п).

Отношение к другим классам графов

Граф имеет коробчатость не более единицы тогда и только тогда, когда он интервальный график; коробчатость произвольного графа грамм - минимальное количество интервальных графов на одном и том же множестве вершин, такое что пересечение множеств ребер интервальных графов равно грамм. Каждые внешнепланарный граф имеет размер не более двух,[2] и каждый планарный граф имеет размер не более трех.[3]

Если двудольный граф имеет коробчатость два, он может быть представлен как граф пересечений параллельных осям отрезков прямых на плоскости.[4]

Адига, Боумик и Чандран (2011) доказал, что коробчатость двудольного графа грамм находится в пределах коэффициента 2 от размер заказа высоты-два частично заказанный набор связано с грамм следующим образом: набор минимальных элементов соответствует одному частному набору грамм, множество максимальных элементов соответствует второму частному набору грамм, причем два элемента сравнимы, если соответствующие вершины смежны в грамм. Эквивалентно размер заказа высоты-два частично заказанный набор п находится в 2 раза меньше квадратичного размера график сопоставимости из п (который является двудольным, поскольку п имеет высоту два).

Алгоритмические результаты

Многие задачи с графами могут быть решены или аппроксимированы более эффективно для графов с ограниченной прямоугольностью, чем для других графов; например, проблема максимальной клики может быть решена за полиномиальное время для графов с ограниченной коробчатостью.[5] Для некоторых других проблем с графами эффективное решение или приближение можно найти, если известно низкоразмерное блочное представление.[6] Однако найти такое представление может быть сложно: это НП-полный чтобы проверить, не превышает ли квадратность данного графа некоторое заданное значение K, даже для K = 2.[7]Чандран, Фрэнсис и Сивадасан (2010) описывать алгоритмы поиска представлений произвольных графов в виде графов пересечений ящиков с размерностью, которая находится в пределах логарифмический фактор максимальная степень графа; этот результат дает верхнюю границу коробчатости графа.

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

Границы

Если график грамм график имеет м края, то:.[9][10]

Если график грамм является k-выродиться (с участием ) и имеет п вершины, то грамм имеет боксерский вид .[11]

Если график грамм не имеет полного графика на т вершины как незначительный, тогда [12] а есть графики без полного графика на т вершины как незначительный, и с коробкой .[13] В частности, любой граф грамм hax boxicity , куда обозначает Инвариант Колена де Вердьера из грамм.

Связанные инварианты графа

  • Кубичность определяется так же, как прямоугольность, но с параллельными осям гиперкубы вместо гипер прямоугольников. Боксичность - это обобщение кубичности.
  • Сферичность определяется так же, как коробчатость, но со сферами единичного диаметра.


Примечания

  1. ^ Например, см. Чандран, Фрэнсис и Сивадасан (2010) и Чандран и Сивадасан (2007).
  2. ^ Шайнерман (1984).
  3. ^ Томассен (1986).
  4. ^ Bellantoni et al. (1993).
  5. ^ Чандран, Фрэнсис и Сивадасан (2010) заметим, что это следует из того факта, что эти графы имеют полиномиальное число максимальные клики. Явное блочное представление не требуется для эффективного перечисления всех максимальных клик.
  6. ^ См., Например, Агарвал, ван Кревельд и Сури (1998) и Berman et al. (2001) для приближений к максимальный независимый набор для графиков пересечений прямоугольников и Хлебик и Хлебикова (2005) за результаты о трудности аппроксимации этих задач в более высоких измерениях.
  7. ^ Cozzens (1981) показывает, что вычисление квадратичности является NP-полным; Яннакакис (1982) показывает, что даже проверка того, не превышает ли квадратичность 3, является NP-сложной задачей; наконец-то Краточвиль (1994) показал, что распознать коробчатость 2 NP-сложно.
  8. ^ Адига, Читнис и Саураб (2010).
  9. ^ Чандран, Фрэнсис и Сивадасан (2010)
  10. ^ Эсперет (2016)
  11. ^ Адига, Чандран и Мэтью (2014)
  12. ^ Эсперет и Вихерт (2018)
  13. ^ Эсперет (2016)

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