Русская Википедия:Интервальная размерность графа
В теории графов интервальная размерность графа — это инвариант графа, введённый Фредом С. Робертсом в 1969.
Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины.
Примеры
На фигуре показан граф с шестью вершинами и представление этого графа в виде графа пересечений (обычных двумерных) прямоугольников. Этот граф нельзя представить в виде графа пересечений прямоугольников меньшей размерности (в данном случае — отрезков), так что интервальная размерность графа равна двум.
РобертсШаблон:Sfn показал, что граф с 2n вершинами, образованный удалением совершенного паросочетания из полного графа с 2n вершинами, имеет интервальную размерность в точности n — любая пара несоединённых вершин должна быть представлена в виде гиперпрямоугольников, которые должны быть разделены в отличной от другой пары размерности. Представление этого графа в виде гиперпрямоугольников с размерностью в точности n можно найти путём утолщения каждой из 2n граней n-мерного гиперкуба в гиперпрямоугольник. Вследствие этого результата такие графы начали называться графами Робертса[1], хотя они более известны как графы «вечеринки» и их можно трактовать также как графы Турана T(2n,n).
Связь с другими классами графов
Граф имеет интервальную размерность не больше единицы тогда и только тогда, когда он является интервальным графом. Интервальная размерность произвольного графа G — это минимальное число интервальных графов с тем же множеством вершин (что и у G), таких, что пересечение множеств рёбер интервальных графов даёт G. Любой внешнепланарный граф имеет интервальную размерность, не превосходящую двухШаблон:Sfn, а любой планарный граф имеет интервальную размерность, не превосходящую трёх Шаблон:Sfn.
Если двудольный граф имеет интервальную размерность два, его можно представить в виде графа пересечений параллельных осям отрезков на плоскостиШаблон:Sfn.
Алгоритмические результаты
Многие задачи на графах могут быть решены или аппроксимированы более эффективно на графах с ограниченной интервальной размерностью. Например, задача о наибольшей клике может быть решена за полиномиальное время для графов с ограниченной интервальной размерностью[2]. Для некоторых других задач на графах эффективное решение или аппроксимация могут быть найдены, если представление в виде пересечения гипермогогранников малой размерности [3].
Однако нахождение таких представлений может оказаться трудным делом — проверка, не превосходит ли интервальная размерность заданного графа некоторой наперёд заданной величины K, является NP-полной задачей, даже для K = 2[4]. Чандран, Фрэнсис и Сивадасан Шаблон:Sfn описали алгоритмы для нахождения представлений произвольных графов в виде графа пересечений гиперпрямоугольников с размерностью, которая находится в пределах логарифмического множителя наибольшей степени графа. Этот результат даёт верхнюю границу интервальной размерности графа.
Несмотря на трудность для естественных параметров, интервальная размерность графа является Шаблон:Не переведено 5, если параметризацию проводить по числу вершинного покрытия входного графаШаблон:Sfn.
Примечания
Литература
- Шаблон:КнигаШаблон:Недоступная ссылка
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- ↑ Например, см. статьи Чандрана, Фрэнсиса и Сивадасана (Шаблон:Harvtxt), Чандрана и Сивадасана Шаблон:Harvtxt.
- ↑ Чандран, Фрэнсис и Сивадасан (Шаблон:Harvtxt) заметили, что это следует из факта, что эти графы имеют полиномиальное число максимальных клик. Явное представление в виде пересечения гиперпрямоугольников не требует перечисления всех максимальных клик.
- ↑ См., например, статьи Шаблон:Harvtxt и Шаблон:Harvtxt для аппроксимациям наибольшего независимого множества для графов пересечений прямоугольников, и Шаблон:Harvtxt для обсуждения сложности аппроксимации этих задач для больших размерностей
- ↑ Коззенс (Шаблон:Harvtxt) показал, что вычисление интервальной размерности графа является NP-полной задачей. Яннакакис (Шаблон:Harvtxt) показал, что даже проверка, не превосходит ли интервальная размерность величины 3, является NP-трудной. Наконец, Краточвил (Шаблон:Harvtxt) показал, что распознавание интервальной размерности = 2 является NP-трудной задачей.
