Задача об оптимальном соединении в пространствах компактов, страница 8

Некоторые вершины атомарного графа могутоставаться свободными.Утверждение 4.14.Доказательство. Будем доказывать утверждение по индукции по числуребер графа. База индукции очевидна, граф, состоящий из двух вершини ребра между ними атомарный.38Пусть мы можем получить вышеописанным способом любой граф свыделенной вершиной и меньше, чем с ребрами.

Рассмотрим произвольный граф с выделенной вершиной и ребрами. Если граф атомарный, то возьмем его. Пусть граф не является атомарным, рассмотримего произвольное разбиение. Возможны два случая:1) выделенная вершина принадлежит двум графам (она не можетпринадлежать трем, так как тогда граф разбиения имел бы цикл). Тогда эта вершина разбивает граф разбиения на две или более связныхкомпоненты.

Можно объединить их в две группы, пересекающиеся только по выделенной вершине. Таким образом, мы получили два графа сменее, чем ребрами, из которых склейкой по выделенной вершине получается исходный граф. Значит, мы можем склеить выбранный графиз атомарных описанными выше операциями.2) выделенная вершина принадлежит одному атомарному графу. Тогда этот граф разбивает граф разбиения на две или более связных компоненты, каждая из которых прикрепляется к атомарному графу и имеетменьше, чем ребер.

Значит, мы можем склеить выбранный граф изатомарных описанными выше операциями.Следующее утверждение позволит нам существенно ограничить перебор:Пусть графы 1 и 2 не имеют общих ребер, но,возможно, имеют общие вершины. Тогда (1 ∪ 2 ) ≥ (1 ) × (2 ).Утверждение 4.15.Доказательство. В объединении двух любых реберных покрытий графов 1 и 2 соответственно, для любой вершины найдется ребро, инцидентное ей, следовательно, такое объединение является реберным покрытием для объединения графов.Таким образом, получаем следующий алгоритм. Пусть мы хотим найти графы, у которых число реберных покрытий не выше некоторого заранее заданного значения .

Будем хранить множество, состоящее изпар ((), ()) (можно хранить также (), но это не является необходимым). Вначале в множестве будет лишь одна пара (0, 1), соответствующая графу, состоящему из одной вершины. Также будем хранитьвсе атомарные графы с выделенной вершиной.Проведем несколько итераций следующих операций (критерий остановки зависит от поставленной задачи, определим его позднее):1) рассмотрим все пары пар (1 , 1 ), (2 , 2 ) таких, что 1 2 ≤ ,для них рассмотрим склейку соответствующих графов по выделеннойвершине и добавим новую пару чисел, формула для вычисления которойбыла найдена в утверждении 4.4 в множество (если такой пары еще нети ≤ ).392) рассмотрим все атомарные графы с выделенной вершиной. Длякаждого такого графа рассмотрим все наборы пар чисел из множестватакие, что произведение количества их реберных покрытий, умноженноена количество покрытий атомарного графа не больше .

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

Для доказательства того, что из данных атомарных графов нельзя построить граф сзаданным значением нужно повторять операции 1 и 2, описанные в алгоритме, до тех пор, пока они добавляют новые элементы ко множествупар. После некоторой итерации операции 1 и 2 перестанут добавлять новые пары, так как количество возможных пар конечно. Тогда если средиэлементов множества пар нет пары с заданным , то связный граф стаким количеством реберных покрытий нельзя построить из выбранныхатомарных графов.Если в качестве выбранных атомарных графов рассматривались вседвудольные атомарные графы с числом реберных покрытий, не больших заданного числа, то связного двудольного графа с заданным числомреберных покрытий не существует. Если же не существует разложениявыбранного числа на множители, для каждого из которых такой связный граф существует, то граф с таким количеством реберных покрытийнельзя составить из нескольких связных компонент.Алгоритм был реализован на языках C#, C++, Java и Q независимои дал одинаковые результаты для реализаций.

В приложении A приведенполный текст программы на языке Java. При помощи данной программыбыл получен следующий результат:Для любого натурального числа от 1 до 1000 включительно кроме, возможно, 19, 37, 41, 59, 67, 82, 97, 149, 197, 223, 257, 291, 379существует двудольный граф с таким количеством реберных покрытий. Двудольный граф не может иметь 19, 37, 41, 59 или 67 реберныхпокрытий.Теорема 4.16.Используя этот же алгоритм, но другой набор атомарных графов,а именно, граф, состоящий из одного ребра, можно получить все возможные количества реберных покрытий деревьев.

Последовательностьчисел, для которых нет дерева с таким количеством реберных покрытийможно описать в следующем утверждении.40У дерева не может быть19 37 41 57 59 67 79 82 97 111 131 149 177 179 197 201 205 223 237 251 257269 271 277 283 291 311 331 379 397 443 449 457 461 469 553 577 587 591 603617 649 677 679 711 733 737 758 771 797 811 829 839 849 877 881 911 985 991или993 реберных покрытия. Для любого натурального числа ≤ 1000не из этого списка существует дерево с таким количеством реберныхпокрытий.Теорема 4.17.Существует ли натуральное число такое, что не существует дерева с таким количеством реберных покрытий, но существует лес?Задача 4.18.415ЗаключениеВ этом разделе мы еще раз перечислим основные результаты работы ивозможные дальнейшие пути исследования.В главе 2 были найдены отношения Штейнера и отношение ШтейнераГромова для пространства компактов в евклидовом пространстве.

Также были найдены суботношения Штейнера степеней 3 и 4. Возможнымипутями для продолжения исследований в том же направлений видятсяследующие задачи:∙ Поиск отношений Штейнера и Штейнера-Громова для пространствкомпактов в банаховых пространствах∙ Поиск суботношения Штейнера и суботношений Штейнера болеевысоких степеней с помощью описанной операции увеличения размерности, проверка гипотезы о минимальности этих суботношенийВ главе 3 были найдены ограничения на суботношение Штейнера длявыпуклых пятиточечных множеств на плоскости, а так же для четырехточечных множеств в пространстве, была показана неверностьгипотезы√3о том, что суботношение Штейнера для плоскости равно 2 .

Идеи, использованные в этой главе можно попытаться перенести на случай большего количества точек√и для проверки гипотезы о том, что суботношениеШтейнера не меньше 23 для всех конечных выпуклых множеств.В главе 4 была разработана теория, позволяющая машинным перебором доказать невозможность существования двудольного графа, имеющего 19, 37, 41, 59 или 67 реберных покрытий. Дальнейшие исследованиямогут включать в себя следующие задачи∙ Поиск продолжения данной последовательности∙ Существует ли натуральное число такое, что не существует дерева с таким количеством реберных покрытий, но существует лес?∙ Существует ли натуральное число такое, что не существует двудольного планарного графа, имеющего такое количество реберныхпокрытий, но существует двудольный непланарный граф с такимколичеством покрытий?∙ Существует ли составное натуральное число такое, что не существует двудольного планарного графа, имеющего такое количествореберных покрытий?42Список публикаций по теме диссертации[Ssr5] З.

Н. Овсянников Суботношение Штейнера для пяти точек наплоскости и четырeх точек в пространстве, Фундамент. и прикл.матем., 18 (2013), стр. 167–179[GHSub] З. Н. Овсянников Отношения Штейнера, Штейнера–Громоваи суботношения Штейнера для пространства компактов в евклидовой плоскости с расстоянием Хаусдорфа, Фундаментальная иприкладная математика, 18(2013), выпуск 2, стр. 157–165[ShPaths] З.Н.Овсянников, Количество реберных покрытий двудольныхграфов или кратчайших с фиксированными концами в пространстве компактов в R , Доклады Академии Наук, 466(2016), выпуск4, стр. 402–405Список литературы[1] C. C.

Blackburn, K. Lund, S.Schliker, P. Sigmon, A. Zupan A MissingPrime Configuration in the Hausdorff Metric Geometry, J. Geom, 92(2009), pp 28-59[2] K. Lund, P. Sigmon, and S. Schlicker, Fibonacci sequences in the spaceof compact sets, Involve 1 (2008), pp 197–215.[3] F. Memoli, G. Sapiro Comparing Point Clouds, EurographicsSymposium on Geometry Processing (2004)[4] K. Honigs, Missing edge coverings of bipartite graphs and the geometryof the Hausdorff metric, Journal of Geometry, 2013.[5] E. N. Gilbert, H.