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

Граф пересечения трапеций между параллельными прямыми

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

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

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

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

Приложения

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

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

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

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

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

Доминирующие прямоугольники, или представление коробок, отображают точки на нижней из двух линий представления трапеции как лежащие на оси x , а точки верхней линии как лежащие на оси y евклидовой плоскости. Каждая трапеция затем соответствует параллельному осям коробу на плоскости. Используя понятие порядка доминирования (в RK , 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 O(n^{2})}$ ${\displaystyle {O}(n^{2}\log n)}$

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

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

Алгоритмы

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

Признание

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

Примечания

1. Идо Даган, Мартин Чарльз Голумбик и Рон Яир Пинтер. Трапециевидные графы и их раскраска. Discrete Appl. Math., 35–46, 1988.
2. Стефан Фельснер, Рудольф Мюллер и Лоренц Верниш. Трапециевидные графы и обобщения, геометрия и алгоритмы. В Algorithm theory—SWAT '94 (Орхус, 1994), том 824 Lecture Notes in Comput. Sci., страницы 143–154. Springer, Берлин, 1994.
3. Кеннет П. Богарт, Гарт Айзек. Правильные и единичные битодопуски порядков и графов. Дискретная математика 181(1–3): 37–51 (1998).
4. Мартин Чарльз Голумбик и Ирит Б.-А. Хартман, ред., Теория графов, комбинаторика и алгоритмы: междисциплинарные приложения, Springer-Verlag, Нью-Йорк, 2005
5. Р. Макконнелл и Дж. Спинрад, Линейное модульное разложение и эффективная транзитивная ориентация неориентированных графов, Proc. 5. Ann. Symp. on Discr. Alg. (1994).
6. Голумбик, Мартин Чарльз и Энн Н. Тренк . Графики толерантности. Кембридж [ua: Cambridge Univ., 2004.
7. GB Mertzios и DG Corneil . Разделение вершин и распознавание трапециевидных графов. Discrete Applied Mathematics, 159(11), страницы 1131-1147, 2011.

Ссылки

• Golumbic, Martin Charles (1980). Алгоритмическая теория графов и совершенные графы. Academic Press. ISBN 0-444-51530-5.Второе издание, Annals of Discrete Mathematics 57, Elsevier, 2004.