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