Задача об оптимальном соединении в пространствах компактов (1102650), страница 7
Текст из файла (страница 7)
По лемме 3.7 () достигает минимума при = 12 ,обозначим ( 21 ) за = { >>, >>, >>, >>} ∈ . Заметим,что ( ) = ssrp ( ), при этом ( ) ≤ () ≤ ssrp (2 ). Но, так как ∈ , выполняется неравенство ( ) ≥ ssrp ( ) и утверждение31леммы выполнено.Из этих лемм тривиальным образом следует утверждениеПараметрическое суботношение Штейнера ssrp ( ) =3 + 5). Суботношение Штейнера для четырех точек в R3 неменьше этого числа.Утверждение 3.13.√17 (2√Теорема 3.14.√1 √ssr4 (R3 ) = (2 3 + 5).7Доказательство. Мы знаем, что ssrp ( ) ≤ ssr4 (R3 ). Но инфинумминимального параметрического суботношения достигается на множестве , для которого — одновременно и топология минимальногозаполнения и топология кратчайшей сети.
Следовательно, ssrp ( ) =ssrp ( ) = ssr( ) ≥ ssr4 (R3 ).324Возможные количества кратчайшихКак было показано в 1.11, можно рассматривать несколько иную задачу,нежели возможные количества кратчайших, а именно, возможные количества реберных покрытий некоторого двудольного графа. Это позволитнам перевести задачу в плоскость машинного перебора.4.1Определения и предварительные результатыВ нижеприведенных леммах и утверждениях все графы будем считатьдвудольными, если не указано иначе.
Все графы будем считать связными, если явным образом не указано иного. Зная, что количество реберныхпокрытий графа, состоящего из нескольких связных компонент равнопроизведению количества реберных покрытий для каждой компоненты(доказательство можно посмотреть, например, в [1]), можно будет исключить некоторые составные числа, полученные машинным перебором,из рассмотрения (забегая вперед, заранее скажем, что это не повлиялона результат, и вопрос, существует ли натуральное число такое, что нетсвязного двудольного графа с таким количеством реберных покрытий,но есть несвязный, открыт).4.1.1Характеристики графа с выделенной вершиной с точкизрения реберных покрытийГрафом с выделенной вершиной будем называть произвольную пару (, ) из непустого графа = (, ) и его вершины ∈ .
Также такой граф будем обозначать (, , )Определение 4.1.Следующие определения могут показаться избыточными, но именноони позволят нам упорядочить перебор.Пусть = (, , ) — граф с выделенной вершиной.Тогда число реберных покрытий графа (, ) будем обозначать ()(заметим, что это значение не зависит от выбранной вершины). Числореберных покрытий графа ( ∖, ∖{| ∈ }) будем обозначать (),а их сумму — () = () + ().Определение 4.2.Реберное предпокрытие графа с выделенной вершиной — это такое подмножество ′ его ребер, что любая вершина ,кроме, возможно, , инцидентна хотя бы одному ребру из ′ .Определение 4.3.Заметим, что тогда () — количество реберных предпокрытий графа .Пусть = (, ) — граф с выделенной вершиной , а — некотороемножество вершин, тогда будем обозначать33{︂ (, ) =(),(),если ∈ ;если ∈/ .(О склейке двух графов с выделенной вершиной).Пусть 1 = (1 , 1 , ) и 2 = (2 , 2 , ) — два графа с общей выделенной вершиной, причем 1 ∩ 2 = {}.
Тогда можно рассмотретьграф с выделенной вершиной = (1 ∪ 2 , 1 ∪ 2 , ) и для него будутвыполняться следующие равенства:1)() = (1 ) × (2 )2)() = (1 ) × (2 )Утверждение 4.4Доказательство. 1) Граф без вершины и прилегающих к ней реберраспадается на два несвязных графа, получающихся из 1 и 2 соответственно с помощью удаления вершины и прилегающих к ней ребер,тогда количество их реберных покрытий равно (1 ) и (2 ) соответственно, следовательно, количество реберных покрытий искомого графабудет равно (1 ) × (2 ).2) Если рассмотреть произвольное подмножество ребер графа , покрывающего все его вершины, кроме, возможно, , то его ограничениена 1 и 2 будет снова покрывать все вершины, кроме, возможно, .Следовательно, () ≤ (1 ) × (2 ). Если рассмотреть произвольныеподмножества ребер графов 1 и 2 , каждое из которых покрывает всевершины соответствующего графа, кроме, возможно, , то их объединение будет покрывать все вершины графа , кроме, возможно, .
Следовательно, () ≥ (1 ) × (2 ).Подграф графа , порожденный подмножеством множества еговершин, обозначим как | .(О склейке графов с выделенной вершиной с отдельным графом с выделенной вершиной). Пусть 0 = (0 , ), причем 0— связный граф, 0 = {, 1 , . .
. , } — множество его вершин, а 0— множество его ребер. Пусть также для = 1, . . . , есть графы = ( , ), причем ∩ = ∅ при ̸= ̸= 0, а ∩ 0 = { }. ТогдаУтверждение 4.5для графа = (⋃︀ , ) выполнены равенства:=01) () =∑︀(0 | ′ ) ′ ⊂0 |∈ ′2) () =∑︀ ′ ⊂0 | ∈/ ′(0 | ′ )∏︀=1∏︀ ( , ′ ), ( , ′ ).=1Доказательство. 1) Фиксируем ′ ⊂ 0 . Пусть ′ —реберное покрытие⋃︀графа = и ′ = ′ ∩ таковы, что для любой вершины ∈ 0=034верно: ∈ ′ тогда и только тогда, когда в 0′ есть ребро, инцидентное.
Очевидно, ∈ ′ .Найдем количество покрытий графа для фиксированного ′ . Таккак и 0 пересекаются друг с другом по одной вершине, а и непересекаются, то все ′ , ̸= 0 — предпокрытия соответствующих графов . Тогда каждое реберное покрытие ′ однозначно задает и задаетсянабором предпокрытий ′ и множеством 0′ .Если ∈/ ′ , то ′ должно быть покрытием, при этом любое покрытие подходит. Всего их ( ).
Если же ∈ ′ , то ′ может быть любымпредпокрытием графа , всего таких покрытий ( ). Таким образом,существует ( , ′ ) возможных значений ′ .Множество 0′ может быть любым набором ребер таким, что длялюбой вершины из ′ есть ребро в 0′ , инцидентное ей, а для любойвершины не из ′ таких ребер нет. Таким образом, каждый подходящий набор ребер 0′ — покрытие графа 0 | ′ , таких покрытий (0 | ′ ).Значит, всего покрытий, для которых выполняется условие на ′ ровно(0 | ′ )∏︀ ( , ′ ). Просуммировав по ′ , получим искомое равенство.=12) Доказательство для второго равенства полностью аналогично доказательству для первого, за исключением того, что не будет принадлежать ′ .4.1.2Атомарные графыДва приведенных выше утверждения образуют основную часть процесса перебора. Для того, чтобыузнать и для графа с выделенной вершиной, полученного спомощью склейки двух графов повыделенной вершине, достаточнознать и его частей.
Эти величины мы и будем хранить при переборе.Рис. 10: Склейка нескольких графовК сожалению, для склейки грас выделенной вершиной с выбран- фов способом, описанным в 4.5,ным графомнужна дополнительная информация о графе 0 . Решение заключается в том, чтобы в качестве графа 0 брать графы из некоторого фиксированного небольшого набораграфов. В этом параграфе мы опишем такие графы, которые мы будемназывать атомарными, а в следующем покажем, что этих графов достаточно для полного перебора.35Рассмотрим граф = (, ) и множество графов1 , . . . , , =⋃︀( , ). Будемназывать это множество разбиением гра⋃︀фа , если⋃︀ = , = (далее будем обозначать такое отношениекак = ) и выполняются следующие условия:1) графы не имеют общих ребер и любая пара графов , имеетне более одной общей вершины.2) Если рассмотреть граф с вершинами, являющимися графами1 , .
. . , и ребром между двумя вершинами, если соответствующиеграфы имеют общую вершину, то граф будет деревом, то есть, связным и не иметь циклов и петель. Граф назовем графом разбиения.Определение 4.6.Граф будем называть атомарным, если не существует его разбиения на два или более графов.Определение 4.7.Заметим, что если у графа есть разбиение на > 2 графов, то с помощью объединения составляющих разбиение графов в два графа (например, граф, являющийся листом графа разбиения, и объединение всехостальных графов) можно получить разбиение исходного графа на два.Для того, чтобы найти графы,являющиеся атомарными, понадобится ряд лемм.Если атомарный графимеет более одного ребра, то он неимеет вершин степени 1.Лемма 4.8.Пусть — связныйграф и его вершины , не соединены ребром.
Тогда для графа ′ ,получающегося из графа добавлением ребра (), верно неравенство (′ ) ≥ 2 ().Лемма 4.9.Доказательство. В самом деле,на каждое реберное покрытие графа можно привести два уникальных покрытия графа ′ : и ∪ {()}.Пусть — связный Рис. 11: Пример разбиения графаграф, , — вершины из графа . (сверху) и графа этого разбиенияТогда для графа ′ , получающего- (снизу)ся из графа добавлением вершины и ребер () и () верно неравенство (′ ) ≥ 3 ().Лемма 4.10.36Доказательство. В самом деле, на каждое реберное покрытие графа можно привести три уникальных покрытия графа ′ : ∪ {()}, ∪{()} и ∪ {(), ()}.Пусть — связный граф, ≥ 2 – натуральное число,0 , +1 — вершины из графа .
Тогда для графа ′ , получающегося изграфа добавлением вершин 1 , . . . , и ребер ( +1 ) верно неравенство (′ ) ≥ 5 ().Лемма 4.11.Доказательство. Будем обозначать множество ребер {(1 , 2 ), . . . , (−1 , )}как . Заметим, что не пусто, так как ≥ 2.На каждое реберное покрытие графа можно привести пять уникальных покрытий графа ′ : ∪ , ∪ ∪{(0 1 )}, ∪ ∪{( +1 )}, ∪ ∪ {(0 1 ), ( +1 )} и ∪ ( ∖ {(1 2 )}) ∪ {(0 1 ), ( +1 )}.Эти леммы позволяют нам делать утверждения следующего рода:пусть нам известен подграф двудольного графа, и число реберныхпокрытий такого графа больше 2 , тогда если граф имеет не более реберных покрытий, то остальная часть графа состоит из висячихвершин и инцидентных им ребер.Для доказательства следующего утверждения нампонадобится теорема из [1]:Количество реберных покрытий угольника при четном равно = + 2−1 , где — -е число Фиббоначчи.
Такие числа называютсячислами Лукаса.Теорема4.12.В общем же случае количество реберных покрытий можно найти,например, перебрав все подмножества множества ребер и выбрав из нихте, которые будут являться покрытиями.Существует ровно семь различных двудольныхатомарных графов с числом реберных покрытий не больше 67.Утверждение 4.13.Доказательство. Граф с одним ребром, очевидно, атомарный. По предыдущим леммам любой другой атомарный граф не имеет вершин степени1. Так как граф двудольный, то все его циклы имеют четную длину.Пусть — цикл максимальной дины в графе, а ℓ — его длина.Пусть ℓ ≥ 10, тогда () ≥ 123 > 67, значит, ℓ < 10.Пусть ℓ = 8, тогда () = 47 > 672 , значит, по вышеприведеннымлеммам, в графе не может быть дополнительных ребер и вершин.Пусть ℓ = 6, тогда () = 18 > 675 , значит, по вышеприведеннымлеммам, в графе может быть не более одной дополнительной вершины степени два или одного дополнительного ребра.
В обоих случаях дополнительные элементы можно расположить единственным образом, таккак граф двудольный. Также граф может состоять из одного цикла.37Пусть ℓ = 4, тогда () = 7. При этом длина любого дополнительного к нему пути не больше двух, иначе существует цикл большей длины.Если такого пути нет, то это просто цикл. Если такой путь есть, то,если он один, то конфигурация графа единственна и число реберныхпокрытий такого графа равно 25, по предыдущим леммам еще одногодополнительного пути в графе быть не может.Перед доказательством этой леммы алгоритм, о котором речь пойдет ниже, был запущен на небольшом числе атомарных графов и быливыявлены несколько возможных чисел, для которых не существует двудольного графа с таким количеством реберных покрытий. Из них число67 было выбрано, как дающее максимальный набор атомарных графов,позволяющий провести машинный перебор за разумное время.
К сожалению, сложность поиска всех атомарных графов с числом реберныхпокрытий меньше некоторого числа такими методами очень быстрорастет с увеличением , как и сложность перебора, о котором пойдетречь в дальнейшем. Так, уже для следующего подозрительного числанужно принять к рассмотрению еще один атомарный граф (полный двудольный граф с долями из четырех и двух вершин), при этом нужнорассмотреть два случая различных выделенных вершин.4.2Основные результатыТеперь мы готовы к доказательству утверждения, на котором базируется алгоритм:Любой граф с выделенной вершиной можно получить из атомарных графов с выделенной вершиной с помощью двух операций:1) склейки двух графов по выделенной вершине;2) склейки атомарного графа с выделенной вершиной с несколькими графами с выделенной вершиной, при этом другие графы с выделенной вершиной склеиваются с различными вершинами атомарного графа (кроме выделенной).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
