Трапециевидный график

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

Рисунок 1: Трапецеидальное представление графа G.

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

Учитывая канал, пару двух горизонтальных линий, трапеция между этими линиями определяется двумя точками на верхней и двумя точками на нижней линии. Граф называется графом-трапецией, если существует набор трапеций, соответствующих вершинам графа, такой, что две вершины соединены ребром тогда и только тогда, когда соответствующие трапеции пересекаются.Размерность интервального порядка частично упорядоченного набора, $P=(X,<)$, — минимальное число d интервальных порядков P ₁ … P _d таких, что P = P ₁ ∩…∩P _d . Граф несравнимости частично упорядоченного множества $P=(X,<)$ это неориентированный граф $G=(X,E)$ где x смежна с y в G тогда и только тогда, когда x и y несравнимы в P. Неориентированный граф является графом-трапецией тогда и только тогда, когда он является графом несравнимости частичного порядка, размерность интервального порядка которого не превышает 2.

Приложения

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

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

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

Трапеции можно использовать для представления графа-трапеции, используя определение графа-трапеции. Представление трапециевидного графа можно увидеть на рисунке 1.

Представление коробки

Доминирующие прямоугольники, или прямоугольное представление, отображают точки нижней из двух линий представления трапеции как лежащие на оси x , а точки верхней линии как лежащие на оси y евклидовой плоскости. Каждая трапеция тогда соответствует прямоугольнику, параллельному оси, на плоскости. Используя понятие порядка доминирования (в R ^К , x говорят, что доминирует над y , обозначается x < y , если x _i меньше y _i для i = 1, …, k ), мы говорим, что ящик b доминирует над ящиком b', если нижний угол b доминирует над верхним углом b' . Более того, если один из двух ящиков доминирует над другим, мы говорим, что они сравнимы. В остальном они несравнимы. Таким образом, две трапеции не пересекаются ровно в том случае, если соответствующие им ящики сравнимы. Представление в виде прямоугольника полезно, поскольку связанный с ним порядок доминирования позволяет использовать алгоритмы развертки линии.

Графики битолерантности

Графы битотолерантности — это графы несравнимости порядка битотолерантности. Порядок является порядком битотолерантности тогда и только тогда, когда существуют интервалы I _x и действительные числа t ₁ ( x ) и t _r ( x ), назначенные каждой вершине x таким образом, что x < y тогда и только тогда, когда перекрытие I _x и I _y меньше, чем t _r ( x ) и t ₁ ( y ), а центр I _x меньше центра I _y . В 1993 году Лэнгли показал, что графы ограниченной битолерантности эквивалентны классу графов-трапеций.

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

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

Как и все графы несравнимости, графы-трапеции совершенны .

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

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

k -трапециевидные графики

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

Алгоритмы

Алгоритмы для графов-трапеций следует сравнивать с алгоритмами для общих графов сосравнимости. Для этого более широкого класса графов задача о максимальном независимом множестве и минимальном кликовом покрытии может быть решена в ${O}(n^{2}\log n)$ время. Даган и др. впервые предложил ${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}$ представляет собой трапециевидный порядок. Самый быстрый алгоритм распознавания порядка трапеций был предложен МакКоннеллом и Спинрадом в 1994 году со временем работы $O(n^{2})$. Этот процесс сводит вопрос об интервальной размерности 2 к проблеме покрытия связанного двудольного графа цепными графами (графами без индуцированного 2K ₂ ). Мерциос и Корней показали, что с помощью расщепления вершин проблема распознавания графов-трапеций успешно решается. $O(n(n+m))$ время, где $m$ обозначает количество ребер. Этот процесс включает в себя расширение данного графа ${G}$, а затем преобразуем расширенный граф, заменяя каждую вершину исходного графа парой новых вершин. Этот «разбитый граф» представляет собой граф перестановок со специальными свойствами, если и только если ${G}$ является графом-трапецией.

Ссылки

• Голумбик, Мартин Чарльз (1980). Алгоритмическая теория графов и совершенные графы . Академическая пресса. ISBN  0-444-51530-5 . Второе издание, Анналы дискретной математики 57, Elsevier, 2004.