Трапецеидальный граф

В теории графов трапецеидальными графами называются графы пересечений трапеций, все параллельные стороны которых лежат на двух прямых. Этот класс графов содержится в классе графов косравнимости и содержат интервальные графы и графы перестановки в качестве подклассов. Граф является трапецеидальным в том и только в том случае, когда существует набор трапеций, соответствующих вершинам графа, и две вершины графа соединены ребром в том и только в том случае, когда соответствующие вершинам трапеции пересекаются. Трапецеидальные графы были введены в рассмотрение в 1988 году Даганом (Ido Dagan), Колумбиком (Martin Charles Golumbic) и Пинтером (Ron Pinter). Для этих графов существуют алгоритмы со временем работы ${O}(n\log n)$ для раскраски графа, для поиска взвешенных независимых множеств, кликовых покрытий и максимальных взвешенных клик.

Рис. 1 — Трапецеидальный граф.

Определение и характеристики

Рис. 2 Набор трапеций, соответствующих трапецеидальному графу.

Пусть заданы две параллельные прямые. На этих прямых задаются трапеции, у которых две вершины лежат на одной прямой, а две другие – на другой прямой. Граф является трапецеидальным в том и только в том случае, когда существует набор трапеций, соответствующих вершинам графа, и две вершины графа соединены ребром в том и только в том случае, когда соответствующие вершинам трапеции пересекаются. Размерностью частично упорядоченного множества $P=(X,<)$ называется наименьшее число d полных порядков $P_{1}...P_{d}$, таких, что $P=P_{1}\cap ...\cap P_{d}$. Граф несовместимости частично упорядоченного множества $P=(X,<)$ — это неориентированный граф $G=(X,E)$, в котором вершина x смежна вершине y в G в том и только в том случае, когда x и y несравнимы в P. Неориентированный граф является трапецеидальным графом в том и только в том случае, когда он является графом несравнимости частично упорядоченного множества с размерностью не более 2.

Приложения

Задачи поиска максимальных клик и раскраски трапецеидальных графов связаны с задачей прокладки проводящих каналов при проектировании интегральных схем. Если заданы некоторые помеченные точки на верхней и нижней сторонах платы, точки с одинаковыми пометками будут соединены в общую сеть. Эта сеть может быть представлена трапецией, которая содержит крайние (левые и правые) точки с одной и той же пометкой. Сети можно проложить без пересечения в том и только в том случае, если трапеции не пересекаются. Таким образом, число необходимых слоёв, нужных для прокладки проводников без пересечений, равно хроматическому числу графа.

Эквивалентные представления

Представление трапециями

Трапеции можно использовать для представления графа, исходя из определения.

Представление прямоугольниками

Представление доминирующими прямоугольниками отображает точки одной прямой как точки на оси x, а точки другой прямой — как точки на оси y евклидовой плоскости. Тогда любая трапеция соответствует прямоугольнику на плоскости. Говорят, что в R^K, x доминируется y, что записывается как x < y, если x_i меньше y_i для i = 1, …, k. Мы говорим, что прямоугольник b доминирует над b’, если нижний угол b доминирует над верхним углом b’. Мы говорим, что два прямоугольника сравнимы, если один доминирует над другим. Таким образом, две трапеции не пересекаются в точности тогда, когда соответствующие им прямоугольники сравнимы. Представление прямоугольниками полезно, поскольку отношение доминирования позволяет применять алгоритм развёртки. Представление графа с рисунка 1 в виде прямоугольников приведено на рисунке 3.

Рис. 3 — Представление трапецеидального графа в виде прямоугольников с порядком доминирования.

Битолерантные графы

Битолерантные графы — это графы несравнимости битолерантного порядка. Порядок называется битолерантным в том и только в том случае, когда существуют интервалы I_x и вещественные числа t₁(x) и t_r(x), присвоенные каждой точке x таким образом, что x < y в тои и только в том случае, когда перекрытие I_x и I_y меньше, чем t_r(x), и t₁(y) и середина I_x меньше, чем середина I_y. В 1993 Лэнгли (Langley) показал, что ограниченные битолерантные графы эквивалентны классу трапецеидальных графов.

Связь с другими семействами графов

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

Как и все графы несравнимости, трапецеидальные графы являются совершенными.

Круговые трапецеидальные графы

Рис. 4 — Представление трапецеидального графа в виде набора круговых трапеций.

Круговые трапецеидальные графы — это класс графов, предложенный Фелснером (Felsner) и др. в 1993. Эти графы являются суперклассом трапецеидальных графов и содержат циркулянтные графы и графы дуг окружности. Круговая трапеция — это область круга между двумя непересекающимися хордами, а круговой трапецеидальный граф — это граф пересечений семейства круговых трапеций. Круговое представление графа представлено на рисунке 4. Существует алгоритм со временем работы $O(n^{2})$ для решения задачи поиска независимого множества максимального веса и алгоритм со временем работы${O}(n^{2}\log n)$ для задачи поиска максимальной по весу клики.

k-трапецеидальные графы

k- трапецеидальные графы — это обобщение трапецеидальных графов на большие размерности пространства. Они были предложены Фелснером и основываются на определении доминантных многомерных прямоугольников. В этих графах вершина x соответствует вектору $(x_{1},\ldots ,x_{k})$. Используя (k − 1)-мерные сортировочные деревья для хранения и выборки координат, алгоритмы Фелснера решают задачи нахождения хроматического числа, максимальной клики и максимального независимого множества за время ${O}(n\log ^{k-1}n)$.

Алгоритмы

Алгоритмы для трапецеидальных графов следует сравнивать с алгоритмами более общих графов косравнимости. Для этого, более широкого класса графов, задачи поиска максимального независимого множества и минимального кликового покрытия можно решить за время ${O}(n^{2}\log n)$. Даган (Dagan) и др. сначала предложили алгоритм раскраски трапецеидальных графов за время ${O}(nk)$, где n — это число вершин, а k —хроматическое число графа. Позднее, используя представление трапецеидальных графов прямоугольниками, Фелснер опубликовал алгоритмы поиска хроматического числа, взвешенного независимого множества, кликового покрытия и максимальной взвешенной клики за время ${O}(n\log n)$. Все эти алгоритмы требуют память размером ${O}(n)$. Эти алгоритмы основываются на доминировании в представлении прямоугольниками, что позволяет применить алгоритмы развёртки. Предложенные Фелснером алгоритмы используют сбалансированные деревья, позволяющие выполнять операции вставки, удаления и запроса за время ${O}(\log n)$, что и даёт результирующее время ${O}(n\log n)$.

Распознавание

Для определения, является ли граф ${G}$ трапецеидальным, ищется транзитивная ориентация ${F}$ на дополнении графа ${G}$. Поскольку трапецеидальные графы являются подмножеством косравнимых графов, если ${G}$ является трапецеидальным, его дополнение ${G'}$ должно быть графом сравнимости. Если транзитивная ориентация ${F}$ на дополнении ${G'}$ не существует, граф ${G}$ не является трапецеидальным. Если же ${F}$ будет найдена, проверяется, будет ли порядок, задаваемый ${F}$ трапецеидальным порядком. Самый быстрый алгоритм распознавания трапецеидального порядка был предложен Макконнеллом (McConnell) и Спинрадом (Spinrad) в 1994 со временем работы $O(n^{2})$. Процесс сводит вопрос о размерности частичного порядка (не превышает ли он 2) к задаче покрытия соответствующего двудольного графа цепями (графами без порождённых 2K₂ подграфов). Как показали Мертциос (Mertzios) и Корнейл (Corneil), если использовать разделение вершин, задачу распознавания трапецеидальных графов можно решить за время $O(n(n+m))$, где $m$ обозначает число рёбер. Этот процесс использует расширение заданного графа ${G}$, а затем преобразование расширенного графа путём замены всех оригинальных вершин графа парой новых вершин. Этот “расщеплённый граф” является графом перестановок со специальными свойствами в том и только в том случае, когда ${G}$ является трапецеидальным.

Ссылки

• Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.