Круговой график - Circle graph

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

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

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

Спинрад (1994) дает O (п²) -временной алгоритм, который проверяет, п-вершинный неориентированный граф является круговым графом и, если это так, строит набор хорд, которые его представляют.

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

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

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

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

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

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

Приложения

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

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

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

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

В граф пересечений набора интервалов на линии называется интервальный график.

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

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

Примечания

^ Клокс, Крач и Вонг (1998).
^ Кейл (1993)
^ Garey et al. (1980).
^ ^а ^б Унгер (1988).
^ Унгер (1992).
^ Черный (2007). Более ранние оценки см. Дьярфас (1985), Косточка (1988), и Косточка и Краточвил (1997).
^ Видеть Косточка (1988) для верхней границы и Агеев (1996) для соответствующей нижней границы. Карапетян (1984) и Дьярфас и Лехель (1985) дать более слабые оценки той же проблемы.
^ Агеев (1999).
^ Бандельт, Чепой и Эппштейн (2010).
^ Навид Шервани, "Алгоритмы для автоматизации физического проектирования СБИС"
^ Вессель и Пешель (1985); Унгер (1988).

внешняя ссылка

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

[1] Клокс, Крач и Вонг (1998).

[2] Кейл (1993)

[FOOTNOTEGareyJohnsonMillerPapadimitriou1980-3] Garey et al. (1980).

[FOOTNOTEUnger1988-4] а ^б Унгер (1988).

[FOOTNOTEUnger1992-5] Унгер (1992).

[6] Черный (2007). Более ранние оценки см. Дьярфас (1985), Косточка (1988), и Косточка и Краточвил (1997).

[7] Видеть Косточка (1988) для верхней границы и Агеев (1996) для соответствующей нижней границы. Карапетян (1984) и Дьярфас и Лехель (1985) дать более слабые оценки той же проблемы.

[8] Агеев (1999).

[FOOTNOTEBandeltChepoiEppstein2010-9] Бандельт, Чепой и Эппштейн (2010).

[10] Навид Шервани, "Алгоритмы для автоматизации физического проектирования СБИС"

[11] Вессель и Пешель (1985); Унгер (1988).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]