Jump to content

Гипотеза Шейнермана

В математике , гипотеза Шайнермана ставшая теперь теоремой, утверждает, что каждый плоский граф является графом пересечения набора отрезков прямой на плоскости. Эту гипотезу сформулировал Э.Р. Шейнерман в своей докторской диссертации. диссертация (1984 г.) , следуя более ранним результатам о том, что каждый плоский граф может быть представлен как граф пересечений набора простых кривых на плоскости ( Эрлих, Эвен и Тарьян, 1976 г. ). Это доказали Жереми Чалопен и Даниэль Гонсалвес ( 2009 ).

Например, граф G, показанный ниже слева, может быть представлен как граф пересечений набора сегментов, показанных ниже справа. Здесь вершины G ребра представлены отрезками прямых, а G представлены . точками пересечения

 

Шайнерман также предположил, что сегментов только с тремя направлениями будет достаточно для представления графов, раскрашиваемых в 3 цвета , а Уэст (1991) предположил, что аналогичным образом каждый планарный граф можно представить с использованием четырех направлений. Если граф представлен сегментами, имеющими только k направлений и никакие два отрезка не принадлежат одной прямой, то граф можно раскрасить в k цветов, по одному цвету для каждого направления. Следовательно, если каждый планарный граф можно представить таким образом только с четырьмя направлениями, затем следует теорема о четырех цветах . Гонсалвес (2020) доказал, что некоторые плоские графы невозможно представить таким образом.

Хартман, Ньюман и Зив (1991) и де Фрессейкс, Оссона де Мендес и Пах (1991) доказали, что каждый двудольный плоский граф может быть представлен как граф пересечения горизонтальных и вертикальных отрезков; об этом результате см. также Czyzowicz, Kranakis & Urrutia (1998) . Де Кастро и др. (2002) доказали, что каждый планарный граф без треугольников можно представить как граф пересечений отрезков прямой, имеющих только три направления; из этого результата следует теорема Греча ( Grötzsch 1959 ) о том, что плоские графы без треугольников можно раскрасить в три цвета. де Фрайссейкс и Оссона де Мендес (2005) доказали, что если планарный граф G может быть 4-цветным таким образом, что ни один разделяющий цикл не использует все четыре цвета, то G имеет представление в виде графа пересечений сегментов.

Chalopin, Gonçalves & Ochem (2007) доказали, что плоские графы относятся к 1-STRING, классу графов пересечений простых кривых на плоскости, которые пересекаются друг с другом не более чем в одной точке пересечения на пару. Этот класс занимает промежуточное положение между графами пересечений отрезков, возникающими в гипотезе Шейнермана, и графами пересечений неограниченных простых кривых из результата Эрлиха и др. Ее также можно рассматривать как обобщение теоремы об упаковке кругов , которая показывает тот же результат, когда кривым разрешено пересекаться по касательной. Доказательство гипотезы Чалопина и Гонсалвеса (2009) было основано на улучшении этого результата.

  • Де Кастро, Н.; Кобос, Ф.Дж.; Дана, Джей Си; Маркес, А. (2002), «Плоские графы без треугольников как графы пересечения сегментов» (PDF) , Журнал графовых алгоритмов и приложений , 6 (1): 7–26, doi : 10.7155/jgaa.00043 , MR   1898201 .
  • Чалопин Дж.; Гонсалвес, Д. (2009), «Каждый плоский граф представляет собой граф пересечения сегментов на плоскости» (PDF) , Симпозиум ACM по теории вычислений .
  • Чалопин Дж.; Гонсалвес, Д.; Очем, П. (2007), «Плоские графы имеют 1-СТРУНУ», Труды восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , ACM и SIAM, стр. 609–617 .
  • Чизович, Дж.; Кранакис, Э.; Уррутия, Дж. (1998), «Простое доказательство представления двудольных плоских графов в виде контактных графов ортогональных отрезков прямых», Information Processing Letters , 66 (3): 125–126, doi : 10.1016/S0020-0190 (98)00046-5 .
  • де Фрейссе, Х.; Оссона де Мендес, П. (2005), «Представления контактов и пересечений», в Пах, Дж. (ред.), Рисование графиков, 12-й Международный симпозиум, GD 2004 , Конспекты лекций по информатике, том. 3383, Springer-Verlag, стр. 217–227 .
  • де Фрейссе, Х.; Оссона де Мендес, П. ; Пах, Дж. (1991), «Представление плоских графов сегментами», Интуитивная геометрия , 63 : 109–117, MR   1383616 .
  • Эрлих, Г.; Эвен, С.; Тарьян, Р.Э. (1976), «Графики пересечения кривых на плоскости», Журнал комбинаторной теории , серия B, 21 (1): 8–20, doi : 10.1016/0095-8956(76)90022-8 , MR   0505857 .
  • Гретч, Герберт (1959), «К теории дискретных сущностей, VII: теорема о трех цветах для сетей без трехкругов на сфере», Wiss. З. Мартин-Лютер-У., Галле-Виттенберг, Math.-Nat. Серия , 8 : 109–120, МР   0116320 .
  • Хартман, IB-A.; Ньюман, И.; Зив, Р. (1991), «О графах пересечения сеток», Discrete Mathematics , 87 (1): 41–52, doi : 10.1016/0012-365X(91)90069-E , MR   1090188 .
  • Шайнерман, Э.Р. (1984), Классы пересечений и множественные параметры пересечений графов , доктор философии. диссертация, Принстонский университет .
  • Уэст, Д. (1991), «Открытые проблемы № 2», Информационный бюллетень группы деятельности SIAM по дискретной математике , 2 (1): 10–12 .
  • Гонсалвес, Дэниел (2020), «Не все плоские графы находятся в PURE-4-DIR», Журнал графовых алгоритмов и приложений , 24 (3): 293–301, doi : 10.7155/jgaa.00533 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 31ef7c75928b3b6cb15222142a77f6b4__1720402860
URL1:https://arc.ask3.ru/arc/aa/31/b4/31ef7c75928b3b6cb15222142a77f6b4.html
Заголовок, (Title) документа по адресу, URL1:
Scheinerman's conjecture - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)