Введение к работе
актуальность темы. Теория графов является разделом теоретической кибернетики. Настоящая работа посвящена исследованию двух проблем этой теории - задаче китайского почтальона и задаче Энтринжера.
Задача китайского почтальона состоит в нахождении длины кратчайшего замкнутого маршрута, проходящего через все рббра графа. В терминах задачи китайского почтальона можно сформулировать такие оптимизационные проблемы как нахождение наибольшего паросочетания, кратчайшего пути, оптимальных консервативных (и-взвешиваний ребер. С ней тесно связаны задача о минимальном покрытии ребер циклами и задача о многопродуктовнх потоках на плоскости. Распэ [в] и Джексон [7], получили оценки наихудших решений невзвешенной задачи китайского почтальона для графов без мостов и минимальных 2-рбберно-связных обыкновенных графов. Поскольку эти оценки ненамного отличались от тривиальных, то возникают естественные вопросы:
-
Можно ли улучшить оценки Распэ и Джексона?
-
Найти обширные классы графов, в которых оценки наихудших решений невзвешенной задачи китайского почтальона существенно лучше.
Задача Энтринжера, поставленная в 1973 году, состоит в
ОПИСаНИИ ОбЫКНОВеННЫХ ГрафОВ 6, В КОТОРЫХ ДЛЯ КаЖДОГО a.3B существует ровно один цикл длины в. Она связана с рядом других проблем о циклической структуре графов и некоторыми теоретико-числовыми вопросами. цель исследования. Во-первых, улучшить оценки, подученные Распэ в невзвешенной задаче китайского почтальона, и найти точные оценки ее наихудших решений в классе однородных графов. Во-вторых, описать графы, обладающие свойством Энтринжера, в некоторых классах. методы исследования. в основу исследования положены теория минимальных джойнов в графах, теория эйлеровых графов и теоремы о нигде ненулевых потоках в графах. научная новизна. Результаты диссертации состоят в следупцем: описаны все графы g, на которых достигается оценка Распа; описаны минимальные 2-рбберно-связныв обыкновенные графы g с максимальной длиной пути китайского почтальона; описаны 2-связные мультиграфы g с максимальной длиной пути китайского почтальона; найдены точные верхние оценки длины пути китайского почтальона в однородных графах и ряде подклассов однородных графов (графы с заданной связностью, с заданным числом малых разрезов, т-атомные графы и др.); получено описание внешнепланарных графов Энтринжера; описаны все графы Энтринжера с цикломатическим числом, меньшим шести; описаны все эйлеровы графы Энтринжера с цикломатическим числом, меньшим восьми. практическая и. теоретическая иЕННость. Результаты и методы главы 2 будут использованы для дальнейшего изучения строения решений задачи китайского почтальона. Идеи главы 3 могут помочь при решениии задач о циклической структуре графов. апробация работы. Результаты диссертации докладывались на семинарах "Эстремальные задачи на графах", "Дискретный анализ" и семинаре отдела теоретической кибернетики Института математики СО РАН, семинаре под руководством профессора В.К.Попкова на ВЦ СО РАН. публикация. По теме диссертации опубликованы две работы [і] и [2]. структура и объем работы. Диссертация состоит из введения, трбх глав основного текста и списка литературы. Объем работы - 120 страниц.