В теории графов круговой граф — это граф пересечений хордовой диаграммы . То есть это неориентированный граф , вершинам которого можно сопоставить конечную систему хорд окружности , причем две вершины смежны тогда и только тогда, когда соответствующие хорды пересекаются друг с другом.
После более ранних алгоритмов с полиномиальным временем [1] Gioan et al. (2013) представили алгоритм распознавания круговых графов за почти линейное время. Их метод медленнее линейного в несколько раз обратной функции Аккермана и основан на лексикографическом поиске в ширину . Время выполнения определяется методом поддержания разбиения графа с приращением по мере добавления вершин, который используется в качестве подпрограммы в алгоритме. [2]
Ряд других задач, которые являются NP-полными на общих графах, имеют алгоритмы с полиномиальным временем, если они ограничены круговыми графами. Например, Клокс (1996) показал, что ширина дерева кругового графа может быть определена и построено оптимальное разложение дерева за время O( n3 ). Кроме того, минимальное заполнение (то есть хордальный граф с как можно меньшим количеством ребер , содержащий данный круговой граф в качестве подграфа) может быть найдено за время O( n3 ). [3] Тискин (2010) показал, что максимальная клика кругового графа может быть найдена за время O( n log 2 n ), а Нэш и Грегг (2010) показали, что максимальное независимое множество невзвешенного кругового графа может быть найдено за время O(n log 2 n ). быть найден за время O( n min{ d , α }), где d — параметр графа, известный как его плотность, а α — число независимости кругового графа.
Однако существуют также проблемы, которые остаются NP-полными, если ограничиться круговыми графами. К ним относятся задачи о минимальном доминирующем множестве , минимальном связном доминирующем множестве и задаче о минимальном общем доминирующем множестве. [4]
Хроматическое число окружного графа — это минимальное количество цветов, которыми можно раскрасить его хорды так, чтобы никакие две пересекающиеся хорды не имели одинаковый цвет. Поскольку можно сформировать круговые графы, в которых сколь угодно большие наборы хорд пересекают друг друга, хроматическое число кругового графа может быть сколь угодно большим, и определение хроматического числа кругового графа является NP-полным. [5] Остается NP-полной проверка того, можно ли раскрасить круговой граф в четыре цвета. [6] Унгер (1992) утверждал, что найти раскраску в три цвета можно за полиномиальное время , но в его описании этого результата отсутствуют многие детали. [7]
Некоторые авторы исследовали проблемы раскраски ограниченных подклассов круговых графов небольшим количеством цветов. В частности, для круговых графов, в которых никакие наборы из k или более хорд не пересекаются друг с другом, можно раскрасить граф всего лишь несколькими цветами . Один из способов выразить это состоит в том, что круговые графы -ограничены . [8] В частном случае, когда k = 3 (то есть для круговых графов без треугольников ), хроматическое число не превышает пяти, и это очень трудно: все круговые графы без треугольников могут быть раскрашены в пять цветов, и при этом существуют круговые графы без треугольников, для которых требуется пять цветов. [9] Если круговой граф имеет обхват не менее пяти (то есть в нем нет треугольников и четырехвершинных циклов), его можно раскрасить не более чем в три цвета. [ 10] Проблема раскраски квадратных графов без треугольников эквивалентна проблеме представления квадратных графов как изометрических подграфов декартовых произведений деревьев ; в этом соответствии количество цветов в раскраске соответствует количеству деревьев в представлении продукта. [11]
Круговые графы возникают при физическом проектировании СБИС как абстрактное представление особого случая маршрутизации проводов , известного как «маршрутизация двухполюсной распределительной коробки». В этом случае область разводки представляет собой прямоугольник, все цепи двухполюсные, а клеммы расположены по периметру прямоугольника. Легко видеть, что граф пересечений этих сетей представляет собой круговой граф. [12] Одной из целей этапа прокладки проводов является обеспечение того, чтобы различные цепи оставались электрически разъединенными, а их потенциально пересекающиеся части должны быть расположены в разных проводящих слоях. Таким образом, круговые графики отражают различные аспекты этой проблемы маршрутизации.
Раскраски круговых графов также можно использовать для поиска книжных вложений произвольных графов: если вершины данного графа G расположены на окружности, причем ребра G образуют хорды окружности, то граф пересечений этих хорд представляет собой Круговой граф и раскраски этого кругового графа эквивалентны вложениям книг, которые соответствуют заданному круговому макету. В этой эквивалентности количество цветов в раскраске соответствует количеству страниц во вложении книги. [6]
Граф является круговым тогда и только тогда, когда он является графом перекрытия набора интервалов на прямой. Это граф, в котором вершины соответствуют интервалам, а две вершины соединены ребром, если два интервала перекрываются, причем ни одна из них не содержит другую.
Граф пересечений множества интервалов на прямой называется графом интервалов .
Струнные графы , графы пересечения кривых на плоскости, включают в себя круговые графы как особый случай.
Каждый дистанционно-наследственный граф является круговым графом, как и любой граф перестановок и каждый граф безразличия . Любой внешнепланарный граф также является круговым графом. [13]
Круговые графы обобщаются многоугольно -круговыми графами , графами пересечений многоугольников, вписанных в одну и ту же окружность. [14]
