Круговой график

Диаграмму см. в разделе Круговая диаграмма .

Другие диаграммы см. в разделах Круговая диаграмма , Диаграмма Смита и График Найквиста .

Окружность с пятью хордами и соответствующий граф окружности.

В теории графов круговой граф — это граф пересечений хордовой диаграммы . То есть это неориентированный граф , вершинам которого можно сопоставить конечную систему хорд окружности , причем две вершины смежны тогда и только тогда, когда соответствующие хорды пересекаются друг с другом.

Алгоритмическая сложность

После более ранних с полиномиальным временем , алгоритмов Джоан и др. (2013) представили алгоритм распознавания круговых графов за почти линейное время. Их метод медленнее линейного в несколько раз обратной функции Аккермана и основан на лексикографическом поиске в ширину . Время выполнения определяется методом поддержания разбиения графа с приращением по мере добавления вершин, который используется в качестве подпрограммы в алгоритме.

Ряд других задач, которые являются NP-полными на общих графах, имеют алгоритмы с полиномиальным временем, если они ограничены круговыми графами. Например, Клокс (1996) показал, что ширина дерева кругового графа может быть определена и построено оптимальное разложение дерева за O( n ³ ) время. Кроме того, минимальное заполнение (то есть хордальный граф с как можно меньшим количеством ребер, содержащий данный круговой граф в качестве подграфа) может быть найдено в O( n ³ ) время. Тискин (2010) показал, что максимальную клику кругового графа можно найти за O( n log ² п ) время, пока Нэш и Грегг (2010) показали, что максимальный независимый набор невзвешенного кругового графа можно найти за время O( n min{ d , α }), где d — параметр графа, известный как его плотность, а α — число независимости кругового графа.

Однако существуют также проблемы, которые остаются NP-полными, если ограничиться круговыми графами. К ним относятся задачи о минимальном доминирующем множестве , минимальном связном доминирующем множестве и задаче о минимальном общем доминирующем множестве.

Хроматическое число

Хорды, образующие 220-вершинный 5-хроматический круговой граф без треугольников Агеева (1996) , нарисованный как расположение линий в гиперболической плоскости .

Хроматическое число окружного графа — это минимальное количество цветов, которыми можно раскрасить его хорды так, чтобы никакие две пересекающиеся хорды не имели одинаковый цвет. Поскольку можно сформировать круговые графы, в которых сколь угодно большие наборы хорд пересекают друг друга, хроматическое число кругового графа может быть сколь угодно большим, и определение хроматического числа кругового графа является NP-полным. Остаётся NP-полной проверка того, можно ли раскрасить круговой граф в четыре цвета. Унгер (1992) утверждал, что найти раскраску тремя цветами можно за полиномиальное время, но в его описании этого результата многие детали опущены.

Некоторые авторы исследовали проблемы раскраски ограниченных подклассов круговых графов небольшим количеством цветов. В частности, для круговых графов, в которых никакие наборы из k или более хорд не пересекаются друг с другом, можно раскрасить граф всего лишь с помощью $7k^{2}$ цвета. Один из способов выразить это состоит в том, что круговые графики $\chi$-ограниченный . В частном случае, когда k = 3 (то есть для круговых графов без треугольников ), хроматическое число не превышает пяти, и это очень точно: все круговые графы без треугольников можно раскрасить пятью цветами, и существуют треугольники. бесплатные круглые графики, требующие пяти цветов. Если круговой граф имеет обхват не менее пяти (т. е. в нем нет треугольников и четырехвершинных циклов), его можно раскрасить не более чем в три цвета. Задача раскраски квадратных графов без треугольников эквивалентна проблеме представления квадратных графов изометрических подграфов декартовых произведений деревьев как ; в этом соответствии количество цветов в раскраске соответствует количеству деревьев в представлении продукта.

Приложения

Круговые графы возникают при СБИС физическом проектировании как абстрактное представление особого случая маршрутизации проводов двухполюсной , известного как « маршрутизация распределительной коробки ». В этом случае область разводки представляет собой прямоугольник, все цепи двухполюсные, а клеммы расположены по периметру прямоугольника. Легко видеть, что граф пересечений этих сетей представляет собой круговой граф. Одной из целей этапа прокладки проводов является обеспечение того, чтобы различные цепи оставались электрически разъединенными, а их потенциально пересекающиеся части должны быть расположены в разных проводящих слоях. Таким образом, круговые графики отражают различные аспекты этой проблемы маршрутизации.

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

Связанные классы графов

Интервальная система с пятью интервалами и соответствующим графом перекрытий.

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

Граф пересечений множества интервалов на прямой называется графом интервалов .

Струнные графы , графы пересечения кривых на плоскости, включают в себя круговые графы как особый случай.

Каждый дистанционно-наследственный граф является круговым графом, как и любой граф перестановок и каждый граф безразличия . Любой внешнепланарный граф также является круговым графом.

Круговые графы обобщаются многоугольно -круговыми графами , графами пересечения многоугольников, вписанных в одну и ту же окружность.

Ссылки

• Агеев, А.А. (1996), «Круговой граф без треугольников с хроматическим числом 5», Discrete Mathematics , 152 (1–3): 295–298, doi : 10.1016/0012-365X(95)00349-2 .
• Агеев А.А. (1999), «Каждый круговой график обхвата не менее 5 раскрашивается в 3 цвета», Discrete Mathematics , 195 (1–3): 229–233, doi : 10.1016/S0012-365X(98)00192-7 .
• Бандельт, Х.-Ю.; Чепой, В.; Эппштейн, Д. (2010), «Комбинаторика и геометрия конечных и бесконечных квадратов», SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137/090760301 , S2CID   10788524 .
• Черны, Якуб (2007), «Раскраска графов кругов», Электронные заметки по дискретной математике , 29 : 357–361, doi : 10.1016/j.endm.2007.07.072 .
• Дэвис, Джеймс; McCarty, Rose (2021), «Кругные графики квадратично χ связаны», Бюллетень Лондонского математического общества , 53 ): 673–679 1905.11578 , doi : 10.1112 blms . : Arxiv   / , (   3 .
• Габор, Чаба П.; Суповит, Кеннет Дж.; Сюй, Вэнь-Лянь (июль 1989 г.), «Распознавание круговых графов за полиномиальное время», Журнал ACM , 36 (3): 435–473, doi : 10.1145/65950.65951
• Гэри, MR ; Джонсон, Д.С .; Миллер, ГЛ ; Пападимитриу, К. (1980), «Сложность раскраски дуг окружностей и хорд», SIAM Journal on Algebraic and Discrete Methods , 1 (2): 216–227, doi : 10.1137/0601025
• Джоан, Эмерик; Пол, Кристоф; Теддер, Марк; Корнейл, Дерек (март 2013 г.), «Практичное и эффективное распознавание круговых графов», Algorithmica , 69 (4): 759–788, arXiv : 1104.3284 , doi : 10.1007/s00453-013-9745-8
• Дьярфас, А. (1985), «О хроматическом числе графов с несколькими интервалами и графов перекрытия», Discrete Mathematics , 55 (2): 161–166, doi : 10.1016/0012-365X(85)90044-5 . Цитируется Агеевым (1996) .
• Дьярфас, А. ; Лехель, Дж. (1985), «Задачи покрытия и раскраски родственников интервалов», Discrete Mathematics , 55 (2): 167–180, doi : 10.1016/0012-365X(85)90045-7 . Цитируется Агеевым (1996) .
• Карапетян А. (1984), О графах пересечения совершенных дуг и хорд , канд. диссертация (на русском языке), Ин-т. Математика, Новосибирск . Цитируется Агеевым (1996) .
• Кейл, Дж. Марк (1993), «Сложность задач доминирования в круговых графах», Discrete Applied Mathematics , 42 (1): 51–63, doi : 10.1016/0166-218X(93)90178-Q .
• Клокс, Тон (1996), «Ширина круговых графов», Int. Дж. Нашел. Вычислить. наук. , 7 (2): 111–120, doi : 10.1142/S0129054196000099 .
• Клокс, Т.; Крач, Д.; Вонг, К.К. (1998), «Минимальное заполнение круговых и дуговых графов», Journal of Algorithms , 28 (2): 272–289, doi : 10.1006/jagm.1998.0936 .
• Косточка А.В. (1988), "Верхние оценки хроматического числа графов", Труды Института математики , 10 : 204–226, MR   0945704 . Цитируется Агеевым (1996) .
• Косточка, А.В.; Краточвил, Дж. (1997), «Покрытие и раскраска полигонально-круговых графов», Discrete Mathematics , 163 (1–3): 299–305, doi : 10.1016/S0012-365X(96)00344-5 .
• Нэш, Николас; Грегг, Дэвид (2010), «Алгоритм, чувствительный к выходу, для вычисления максимально независимого набора кругового графа», Information Processing Letters , 116 (16): 630–634, doi : 10.1016/j.ipl.2010.05.016 , hdl : 10344/2228 .
• Спинрад, Джереми (1994), «Распознавание круговых графов», Journal of Algorithms , 16 (2): 264–282, doi : 10.1006/jagm.1994.1012 .
• Тискин, Александр (2010), «Быстрое умножение матриц единичного Монжа на расстояние», Труды ACM-SIAM SODA 2010 , стр. 1287–1296 .
• Унгер, Уолтер (1988), «О k -раскраске круговых графов», STACS 88: 5-й ежегодный симпозиум по теоретическим аспектам информатики, Бордо, Франция, 11–13 февраля 1988 г., Труды , конспекты лекций по информатике , том. 294, Берлин: Springer, стр. 61–72, doi : 10.1007/BFb0035832 .
• Унгер, Уолтер (1992), «Сложность раскраски круговых графов», STACS 92: 9-й ежегодный симпозиум по теоретическим аспектам информатики, Качан, Франция, 13–15 февраля 1992 г., Труды , Конспекты лекций по информатике, том. 577, Берлин: Springer, стр. 389–400, doi : 10.1007/3-540-55210-3_199 .
• Вессель, В.; Пёшель, Р. (1985), «О круговых графах», в Саксе, Хорсте (ред.), Графы, гиперграфы и приложения: материалы конференции по теории графов, проходившей в Эйбе, с 1 по 5 октября 1984 г. , Teubner-Texte zur Mathematik, vol. 73, Б. Г. Тойбнер, стр. 207–210 . Цитируется Унгером (1988) .