В теории графов , A строка граф является графом пересечений из кривых на плоскости; каждая кривая называется «струной». Учитывая график G , G представляет собой строку график , если и только если существует множество кривых, или строк, нарисованный в плоскости таким образом, что никакие три строки пересекаются в одной точке и таким образом, что граф , имеющий вершину для каждой кривой и ребро для каждой пересекающей пары кривых изоморфна G .
Задний план
Сеймур Бензер ( 1959 ) описал концепцию, аналогичную строковым графам, применительно к генетическим структурам. В этом контексте он также представил частный случай пересечения интервалов на прямой, а именно теперь классическое семейство интервальных графов . Позже Синден (1966) применил ту же идею к электрическим сетям и печатным схемам. Математическое изучение строковых графов началось с работы Эрлиха, Эвена и Тарьяна (1976) и в результате сотрудничества между Синденом и Рональдом Грэхемом , где характеристика строковых графов в конечном итоге стала открытым вопросом на 5-м Венгерском коллоквиуме по комбинаторике. в 1976 г. [1] Тем не менее, в конечном итоге было доказано, что распознавание строковых графов является NP-полным , что подразумевает, что не существует простой характеристики, вероятно, не существует. [2]
Связанные классы графов
Каждый планарный граф является строковым графом: [3] можно сформировать представление строкового графа для произвольного графа, встроенного в плоскость, нарисовав строку для каждой вершины, которая проходит вокруг вершины и вокруг средней точки каждого смежного ребра, как показано на фигура. Для любого ребра uv графа строки для u и v дважды пересекают друг друга около середины uv , и нет никаких других пересечений, поэтому пары пересекающихся строк представляют в точности смежные пары вершин исходного плоского графа . В качестве альтернативы, согласно теореме об упаковке кругов , любой плоский граф может быть представлен как набор окружностей, любые две из которых пересекаются тогда и только тогда, когда соответствующие вершины смежны; эти круги (с выбранной начальной и конечной точкой, чтобы превратить их в открытые кривые) обеспечивают представление строкового графа данного плоского графа. Chalopin, Gonçalves & Ochem (2007) доказали, что каждый планарный граф имеет строковое представление, в котором каждая пара строк имеет не более одной точки пересечения, в отличие от представлений, описанных выше. Гипотеза Шейнермана , теперь доказанная, является еще более сильным утверждением, что любой планарный граф может быть представлен графом пересечений отрезков прямых, очень частным случаем строк.
Если каждое ребро данного графа G является подразделены , полученный график представляет собой строку график , если и только если G является плоской. В частности, подразделение полного графа K 5, показанное на иллюстрации, не является строковым графом, потому что K 5 не является плоским. [3]
Каждый круговой граф , как граф пересечений линейных сегментов (хорды круга), также является строковым графом. Каждый хордовый граф может быть представлен как строковый граф: хордовые графы - это графы пересечений поддеревьев деревьев, и можно сформировать строковое представление хордового графа, сформировав планарное вложение соответствующего дерева и заменив каждое поддерево строкой, которая отслеживает по краям поддерева.
Комплемента график каждой сопоставимость графы также строка граф. [4]
Другие результаты
Эрлих, Эвен и Тарьян (1976) показали, что вычисление хроматического числа строковых графов является NP-трудным. Краточвил (1991a) обнаружил, что строковые графы образуют индуцированный второстепенный замкнутый класс, но не второстепенный замкнутый класс графов.
Каждый строковый граф с m- краем можно разбить на два подмножества, каждое из которых представляет собой постоянную долю размера всего графа, путем удаления O ( m 3/4 log 1/2 m ) вершин. Отсюда следует, что строковые графы без бикликов , строковые графы, не содержащие подграфа K t , t для некоторой константы t , имеют O ( n ) ребер и, что более важно, имеют полиномиальное расширение . [5]
Заметки
- ^ Грэм (1976) .
- ^ Kratochvil (1991b) показал, что распознавание строковых графов является NP-трудным, но не смог показать, что это может быть решено в NP. После промежуточных результатов Schaefer & Štefankovič (2001) и Pach & Tóth (2002) , Schaefer, Sedgwick & Štefankovič (2003) завершили доказательство того, что проблема NP-полна.
- ^ a b Шефер и Штефанкович (2001) приписывают это наблюдение Синдену (1966) .
- ^ Golumbic, Rotem и Уррутиа (1983) и Lovász (1983) . См. Также Fox & Pach (2010) .
- ^ Фокс и Пач (2010) ; Дворжак и Норин (2015) .
Рекомендации
- Бензер, С. (1959), "О топологии тонкой генетической структуры", Труды Национальной академии наук Соединенных Штатов Америки , 45 (11): 1607–1620, Bibcode : 1959PNAS ... 45.1607B , DOI : 10.1073 / pnas.45.11.1607 , КУП 222769 , PMID 16590553 CS1 maint: обескураженный параметр ( ссылка ).
- Chalopin, J .; Gonçalves, D .; Очем П. (2007), «Планарные графы в 1-STRING», Материалы восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , ACM и SIAM, стр. 609–617.
- Дворжак, Зденек ; Норин, Сергей (2015), Сильно сублинейные разделители и полиномиальное разложение , arXiv : 1504.04821 , Bibcode : 2015arXiv150404821D.
- Эрлих, G .; Даже, S .; Tarjan, RE (1976), "Графы пересечений кривых на плоскости", Журнал комбинаторной теории , 21 (1): 8–20, DOI : 10.1016 / 0095-8956 (76) 90022-8.
- Фокс, Джейкоб ; Пах, Янош (2010), "Теорема о разделителе для строковых графов и ее приложения", Комбинаторика, вероятность и вычисления , 19 (3): 371, DOI : 10.1017 / s0963548309990459.
- Golumbic, M .; Rotem, D .; Уррутия, Дж. (1983), «Графы сопоставимости и графы пересечений», Дискретная математика , 43 (1): 37–46, DOI : 10.1016 / 0012-365X (83) 90019-5.
- Грэм, Р.Л. (1976), «Проблема 1», Открытые задачи на 5-м венгерском коллоквиуме по комбинаторике CS1 maint: обескураженный параметр ( ссылка ).
- Краточвил, Ян (1991a), «Струнные графы. I. Число критических нестроковых графов бесконечно», Журнал комбинаторной теории, серия B , 52 (1): 53–66, DOI : 10.1016 / 0095-8956 (91) 90090-7 CS1 maint: обескураженный параметр ( ссылка ).
- Краточвил, Ян (1991b), «Строковые графы. II. Распознавание строковых графов - это NP-трудная задача», Журнал комбинаторной теории, серия B , 52 (1): 67–78, DOI : 10.1016 / 0095-8956 (91) 90091 -W CS1 maint: обескураженный параметр ( ссылка ).
- Ловас, Л. (1983), «Совершенные графы», Избранные темы теории графов , 2 , Лондон: Academic Press, стр. 55–87. CS1 maint: обескураженный параметр ( ссылка ).
- Пах, Янош ; Тота, Геза (2002), "Распознавание строк графы разрешима", Дискретная и вычислительная геометрия , 28 (4): 593-606, DOI : 10.1007 / s00454-002-2891-4.
- Шефер, Маркус; Штефанкович, Даниэль (2001), «Разрешимость строковых графов», Труды 33-го ежегодного симпозиума ACM по теории вычислений (STOC 2001) : 241–246.
- Шефер, Маркус; Седжвик, Эрик; Štefankovič, Daniel (2003), "признавая струнные графики в НП", журнал компьютерных и системных наук , 67 (2): 365-380, DOI : 10.1016 / S0022-0000 (03) 00045-X.
- Sinden, FW (1966), "Топология тонкопленочных RC-цепей", Bell System Technical Journal , 45 (9): 1639–1662, DOI : 10.1002 / j.1538-7305.1966.tb01713.x.