Введение

График пересечения диаграммы аккордов
диаграмма
другие диаграммы

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

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

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

Приложения

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

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

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