График трапеции

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

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

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

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

Приложения

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

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

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

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

Коробка представления

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

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

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

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

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

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

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

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

k -Трапеции

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

Алгоритмы

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

Признание

Чтобы определить, является ли граф трапециевидным графом, поищите транзитивную ориентацию в дополнении к . Поскольку графы трапеции являются подмножеством графов сопоставимости, если это граф трапеций, его дополнение должно быть графом сопоставимости. Если транзитивной ориентации дополнения не существует, это не трапециевидный граф. Если он существует, проверьте, является ли порядок, заданный в, порядком трапеции. Самый быстрый алгоритм распознавания порядка трапеций был предложен МакКоннеллом и Спинрадом в 1994 году с временем работы . Этот процесс сводит вопрос размерности интервала 2 к проблеме покрытия ассоциированного двудольного графа цепными графами (графами без индуцированных 2K ₂${\ displaystyle {G}}$${\ displaystyle {F}}$${\ displaystyle {G}}$${\ displaystyle {G}}$${\displaystyle {G'}}$${\displaystyle {F}}$${\displaystyle {G'}}$${\displaystyle {G}}$${\displaystyle {F}}$${\displaystyle {F}}$${\displaystyle O(n^{2})}$). ^[6] Используя разбиение вершин, Мерциос и Корнейл показали, что задача распознавания для трапециевидных графов успешно выполняется во времени, где обозначает количество ребер. Этот процесс включает расширение данного графа , а затем преобразование расширенного графа путем замены каждой из вершин исходного графа парой новых вершин. Этот «разбитый граф» является графом перестановок со специальными свойствами, если только если он является графом трапеций. ^[7]${\displaystyle O(n(n+m))}$${\displaystyle m}$${\displaystyle {G}}$${\displaystyle {G}}$

Примечания

использованная литература

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