Jump to content

Строковый граф

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

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

[ редактировать ]
Представление планарного графа в виде строкового графа.

Каждый планарный граф представляет собой строковый граф: [3] можно сформировать представление строкового графа для произвольного графа, вложенного в плоскость, нарисовав для каждой вершины строку, которая огибает вершину и середину каждого смежного ребра, как показано на рисунке. Для любого ребра uv графа строки u и v пересекают друг друга дважды около середины uv , и других пересечений нет, поэтому пары пересекающихся строк представляют собой в точности соседние пары вершин исходного плоского графа. . В качестве альтернативы, согласно теореме об упаковке кругов , любой плоский граф может быть представлен как набор кругов, любые два из которых пересекаются тогда и только тогда, когда соответствующие вершины смежны; эти круги (с начальной и конечной точкой, выбранной для превращения их в разомкнутые кривые) обеспечивают представление данного плоского графа в виде строкового графа. Chalopin, Gonçalves & Ochem (2007) доказали, что каждый планарный граф имеет строковое представление, в котором каждая пара строк имеет не более одной точки пересечения, в отличие от представлений, описанных выше. Гипотеза Шайнермана , теперь доказанная, представляет собой еще более сильное утверждение о том, что каждый плоский граф может быть представлен графом пересечения отрезков прямых, что является особым случаем струн.

Подразделение K 5 , не являющееся строковым графом.

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

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

Граф дополнений каждого графа сравнимости также является строковым графом. [4]

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

[ редактировать ]

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

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

Примечания

[ редактировать ]
  1. ^ Грэм (1976) .
  2. ^ Краточвил (1991b) показал, что распознавание строковых графов является NP-трудным, но не смог показать, что его можно решить в NP. После промежуточных результатов Шефера и Штефанковича (2001) и Паха и Тота (2002) , Шефер, Седжвик и Штефанкович (2003) завершили доказательство того, что задача NP-полна.
  3. ^ Jump up to: а б Шефер и Штефанкович (2001) приписывают это наблюдение Синдену (1966) .
  4. ^ Голумбик, Ротем и Уррутия (1983) и Ловас (1983) . См. также Fox & Pach (2010) .
  5. ^ Фокс и Пах (2010) ; Дворжак и Норин (2016) .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a71b5453899a4985c9a5bd2d70cc0e22__1721108520
URL1:https://arc.ask3.ru/arc/aa/a7/22/a71b5453899a4985c9a5bd2d70cc0e22.html
Заголовок, (Title) документа по адресу, URL1:
String graph - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)