Уважаемый товарищ
«В научно-исследовательской работе вуз обязан сделать главный упор на удовлетворительное решение теоретико-практических, научно-технических проблем строительства могучего социалистического государства, развитие фундаментальных отраслей науки и освоение сверхсовременных отраслей науки и техники».
Мы провели исследования о рисовании внешне плоских графов двумя длинами рёбер в дискретной геометрии, одной из областей современной науки и техники.
Вырождающееся расстояние-число графа является минимальным числом длин рёбер в линейном вложении графа на плоскости. Карми и другие(2008) выдвинули вопрос: равномерно ограничено ли это число для внешне плоских графов? Эта проблема решена положительно Алоном и Фелдхеимом(2015), которые показали, что почти каждые три длины рёбер могут использоваться для построения вырождающегося рисования внешне плоских графов. Алон и Фелдхеим сомневались, ограничено ли это вырождающееся расстояние-число двумя длинами на самом деле. Нами было доказано, что почти каждые две длины рёбер могут использоваться для построения вырождающегося рисования внешне плоских графов.
Планарное вложение является отображением графа на плоскость без пересечений рёбер. Внешне плоский граф является графом, который имеет планарное вложение, в котором все вершины находятся на границе бесконечой грани.
Линейное вложение является отображением графа на плоскость. При этом вершины графа отображаются в точки плоскости. Каждое ребро отображается в интервал, который соединяет изображение двух точек, инцидентных к тому ребру. Длина интервала называется длиной этого ребра в том же вложении. Вырождающееся вложение графа G является линейным вложением, в котором изображения всех точек непересекаются. Рисование графа является вырождающимся рисованием, в котором изображения всех точек не находятся в изображении каждого ребра G.
Расстояние-число графа G являеся минимальным числом длин рёбер в рисовании G.
Вырождающееся расстояние-число графа являеся минимальным числом длин рёбер в вырождающемся рисовании G.
Алон и Фелдхеим доказали впечатляющим методом, что верхняя грань для вырождающегося расстояния-числа внешне плоского графа является 3 и выдвинули вопрос: не больше ли вырождающееся расстояние-число, чем 2. На самом деле легко показать, что максимальное вырождающееся расстояние-число внешне плоского графа больше чем 1. Отсюда если мы покажем вырождающееся рисование двумя длинами рёбер, то максимальное вырождающееся расстояние-число внешне плоского графа будет именно два. Мы делали это подобно Алону и Фелдхеиму.
Наш основной результат:
Теорема. Для почти любых действительных чисел a,b таких, что 2a≥b, 2b≥a каждый внешне плоский граф имеет вырождающееся рисование длинами рёбер a,b.
Полученные результаты были опуликованны на тему «Degenerate drawing of outerplanar graphs with two edge lengths» в журнале «Discrete Applied Mathematics»степени SCI, издательства Elsevier в 2021 году (https://doi.org/10.1016/j.dam.2021.07.014)
В дальнейщем мы хотим использовать подобные методы для того, чтобы получить более тесную верхнюю грань для расстоянии-числа внешне плоских графов.
