Меню

Главная
Случайная статья
Настройки
Струнный граф
Материал из https://ru.wikipedia.org

Струнный граф — это граф пересечений кривых на плоскости, каждая кривая при этом называется «струной». Если дан граф G, он является струнным тогда и только тогда, когда существует набор кривых (струн), нарисованных на плоскости, таких, что никакие три струны не пересекаются в одной точке и граф G изоморфен графу, вершины которого соответствуют кривым, а дуга в этом графе соответствует пересечению двух кривых.

Содержание

Предпосылки

Бензер (Benzer 1959) описывал концепцию, близкую струнным графам, но для более общих структур. В этом контексте он также сформулировал специальный случай пересечения интервалов на прямой, ставший классическим классом интервальных графов. Позднее Синден (Sinden 1966) выразил ту же идеею для электрических сетей и печатных схем. Математическое изучение струнных графов началось со статьи Эрлиха, Ивена и Тарьяна (Ehrlich, Even, Tarjan 1976) и при содействии Синдена и Рональда Грэма описание струнных графов, в конечном счёте, было поставлено как открытая проблема на 5-м Венгерском коллоквиуме по комбинаторике в 1976[1]. В конце концов, было доказано, что распознавание струнных графов является NP-полной задачей, откуда следует, что вряд ли существует простое описание этого класса[2]

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

Любой планарный граф является струнным[3] — можно образовать представление в виде струнного графа для любого вложенного в плоскость графа путём рисования для каждой вершины кривой, которая обходит по кругу вершину и середину каждого смежного ребра, как показано на рисунке. Для любого ребра uv графа, струны для u и v пересекаются дважды близ середины ребра uv, и не существует других пересечений, так что пересечение пары струн представляют смежные пары вершин исходного планарного графа. Альтернативно, по теореме об упаковке кругов, любой планарный граф может быть представлен в виде коллекции окружностей, любые две из которых пересекаются тогда и только тогда, когда соответствующие вершины смежны. Эти окружности (с начальной и конечной точкой, выбранными для превращения окружности в открытую кривую) дают представление заданного планарного графа в виде струнного графа. Чалопин, Гонсалвис и Ошан (Chalopin, Gonalves, Ochem 2007) доказали, что любой планарный граф имеет представление в виде струнного графа, в котором каждая пара струн имеет максимум одно пересечение, а не так, как описано выше. Гипотеза Шейнермана, ныне доказанная, является даже более строгим утверждением, что любой планарный граф может быть представлен как граф пересечений отрезков.

Если все рёбра заданного графа G подразделяются, полученный граф является струнным графом тогда и только тогда, когда граф G планарен. В частности, подразделение полного графа K5, показанное на рисунке, струнным графом не является, поскольку K5 не планарен[3].

Любой круговой граф, как граф пересечений отрезков (хорд окружности) является также струнным графом. Любой хордальный граф может быть представлен как струнный граф — хордальные графы являются графами пересечений поддеревьев деревьев и можно образовать струнное представление хордального графа путём планарного вложения соответствующего дерева и заменой каждого поддерева струной, проходящей вокруг рёбер поддерева.

Дополнение графа любого графа сравнимости является также струнным графом[4].

Другие результаты

Эрлих, Эвен и Тарьян (Ehrlich, Even, Tarjan 1976) показали, что вычисление хроматического числа струнного графа является NP-трудной задачей. Кратохвил (Kratochvil 1991a) обнаружил, что струнные графы образуют замкнутый класс порождённых миноров, но не минорно замкнутый класс графов.

Любой струнный граф с m рёбрами можно разбить на два подмножества, при этом каждое подмножество составляет фиксированную долю полного графа, путём удаления O(m3/4log1/2m) рёбер. Отсюда следует, что струнные графы без клик, струнные графы, не содержащие подграфов Kt,t ни для какой постоянной t, имеют O(n) рёбер и имеют полиномиальное расширение[5][6].

Примечания
  1. Graham, 1976.
  2. Кратохвил (Kratochvil 1991b) показал, что распознавание струнного графа является NP-трудной задачей, но не смог показать, что она может быть решена в классе NP. После промежуточных результатов Шефера и Стефанковича (Schaefer, tefankovi 2001), Паха и Тота (Pach, Tth 2002), Шефера, Седжвика и Стефанковича (Schaefer, Sedgwick, tefankovi 2003) было завершено доказательство, что задача NP-полна.
  3. 1 2 Шефер и Стефанкович (Schaefer, tefankovi 2001) приписывают это наблюдение Синдену(Sinden 1966).
  4. Golumbic, Rotem, Urrutia, 1983; Lovsz, 1983. См. также статью Фокса и Паха (Fox, Pach 2009).
  5. Fox, Pach, 2009.
  6. Dvok, Norin, 2015.


Литература
Downgrade Counter