Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 120
Текст из файла (страница 120)
Если это сделать, то вопрос сведется к тому, сколькими способами можно заполнить и — 2 пробела, если имеется и способов заполнения каждого пробела, а таких способов, как известно, существует и" з. Вместо формального доказательства приведем алгоритм построения указанной последовательности по остовному дереву и алгоритм построения остовного дерева по соответствующей последовательности. Далее покажем на примере, что если начать с остовного дерева и использовать алгоритм построения последовательности, а затем применить к ней алгоритм построения остовного дерева, то получим исходное остовное дерево. Начнем с алгоритма преобразования остовного дерева в последовательность. Алгоритм перевода дерева в последовательность — ДвП(Т) для и ) 3 (1) Для выбора а~ взять лист е с наименьшим значением ~.
Всегда существует единственное )с такое, что (оу, ьь) является ребром дерева. Удалить это ребро и положить а~ = к. (2) Если выбрано а, и то для выбора а; из оставшегося дерева взять лист е, с наименьшим значением в'. Всегда существует единственное й такое, что (ев, оь) является ребром дерева. Удалить это ребро и положить а, = !ь (3) Продолжать, пока не будет выбрано а„з. ПРИМЕР 15.29. Пусть Т вЂ” дерево, изображенное на рис. 15.84.
Вершина аз— лист с наименьшим индексом, поэтому удаляем ребро (сз, ев) и полагаем а~ = 1, как показано на рис. 15.85. Поскольку в оставшемся дереве вершина из — лист с наименьшим индексом, удаляем ребро (сз, св) и полагаем аз = 4 (рис, 15.86). "в в вв вв "в Рис. 15.85 Рис. !5.85 Рис.
/5.84 Далее, сз — лист с наименьшим индексом, удаляем ребро (о;, ев) и полагаем аз = 1, как показано на рис. 15.87. Поскольку в оставшемся дереве вершина св— лист с наименьшим индексом, удаляем ребро (ем ос) и полагаем а4 = 6, как показано на рис. 15.88. В оставшемся дереве вершина ет — лист с наименьшим индексом, поэтому удаляем ребро (ит, ое) и полагаем аз = 6 (рис. 15.89). РАЗДЕЛ 15.5.
Остовные деревья 671 ° б У У 7 б Уб Рис. 15.87 Рис. 15.88 Рис. 15.89 Наконец, поскольку в оставшемся дереве ее — лист с наименьшим индексом, удаляем ребро (ев, ю4) и полагаем ав = 4. Осталось только ребро, изображенное на рис. 15.90. Поэтому искомая последовательность имеет вид 1, 4, 1, 6, 6, 4, Отметим, что происходит число вхождений в последовательность индекса каждой вершины на единицу меньше ее степени.
Это потому, что прн удалении ребра вершина-лист не учитывется, а вторая его вершина учитывается как вершина в ребре, которое остается как лист, или как вершина в ребре, которое остается. П "в Рис. 15.90 3 "з Уг 7 Рис. 15.91 Рис. 15.92 Рис. 15.93 Поскольку вершина еб стала листом с наименьшим индексом, удаляем ребро 1ю„,о~о) и полагаем аз = 10 (рис. 15.94). Теперь вершина ез стала листом с наименьшим индексом, удаляем ребро (оз,ого) и полагаем а4 = 10, как показано на рис.
15.95. Далее, поскольку вершина юе стала листом с наименьшим индексом, удаляем ребро (ов,е~) и полагаем аз = 1 (рис. 15.96). ПРИМЕР 16.30. Пусть Т вЂ” дерево, изображенное на рис. 15.91. Поскольку язв лист с наименьшим индексом, УдалЯем РебРо (еа, оэ) и полагаем аг = 9, как показано на рис. 15.92. В оставшемся дереве оз — лист с наименьшим индексом, удаляем ребро (ез,оз) и полагаем аз = 8, как показано на рис. !5.93. 672 ГЛАВА 15. Деревья "и Уд Рис. 15,95 Рис. 15.94 Рис.
15.95 Поскольку в оставшемся дереве вершина от стала листом с наименьшим индексом, удаляем ребро (от, оа) и полагаем ае = 8, как показано на рис. 15.97. Теперь вершина оа стала листом с наименьшим индексом, поэтому удаляем ребро (оа,од) и полагаем ат = 9, как показано на рис. 15.98. Наконец, оставшаяся вершина ид стала листом с наименьшим индексом, и мы удаляем ребро (од,ог) и полагаем аа = 1.
В результате осталось только ребро, изображенное на рис. 15.99. "и Рис. 15.97 Рис, !5,99 Рис. 15,95 Таким образом, искомая последовательность имеет вид 9, 8, 10, 10, 1, 8, 9, 1. Теперь нам нужен обратный алгоритм, Алгоритм перевода последовательности в дерево— ПвД(аз,аа,...,а а) для ть > 3 (1) Для каждого о„если 1 появляется в последовательности п, раз, положить г(е8(о;) = тн + 1. (2) Прочитать аг и сформировать ребро (и „о ), где 9' — наименьшая метка, такая что Йеб(о = 1). (3) Уменьшить г(ея(о,) и г(ея(оу) на 1. (4) Предположим, что а, г прочитано, читать а, и формировать ребро (и,, иу), где 1 — наименьшая такая метка, что бек(о ) = 1.
(5) Уменьшить бея(о,) и с(ек(оу) на 1. (б) После того, как аи а прочитано, создать ребро между двумя оставшимися вершинами степени 1. ПРИМЕР 16.31. Рассмотрим последовательность 1,4,1,6,6,4 и воспользуемся ею для восстановления исходного дерева из примера !5.29. РКЗДЕЛ 15.5. Остоеныв деревья 673 Поскольку 1, 4 и 6 появляются в последовательности дважды, то с)ей(ос) = с!ей(ие) = с!ей(ие) = 3.
А так как 2, 3 и 5 не встречаются вообще, то с)ея(и2) = с!е6(юз) = с)е6(гв) = с!ея(ит) = с!е$(из) = 1. Запишем их с помощью восьмерки из чисел (3,1,1,3,1,3,1,1), которую назовем восьмеркой степеней. Теперь считываем аг = 1 и, поскольку из среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (вы из) (рис. 15.100). Положим с)ея(иг) = 2 и с!ея(из) = О, поэтому восьмерка степеней теперь имеет вид (2,0,1,3,1,3,1,1). Далее считываем аз = 4 и, потому что из среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (оз,ие), после чего получаем граф, изображенный на рис. 15.101. Полагаем с)ея(и4) = 2 и с!ек(из) = О, поэтому восьмерка степеней теперь имеет вид (2,0,0,2,1,3,1,1).
Второе ребро наклонено в другую сторону, потому что я смошенничал и посмотрел на дерево, которое пытаюсь воссоздать. Теперь считываем аз = 1 и, поскольку св среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (с низ), после чего получаем граф, изображенный на рис. 15.!02, Рис. 15.100 Рис. 15.102 Рис. 15. 101 Полагаем с)ек(ог) = 1 и с!ед(из) = О, поэтому восьмерка степеней теперь имеет вид (1,0,0,2,0,3,1,1).
Считываем ае = 6 и, поскольку иг среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (сыне), после чего получаем граф, изображенный на рис. 15.!03. Полагаем с!ек(ис) = 0 и с!ек(ие) = 2, поэтому восьмерка степеней теперь имеет вид (0,0,0,2,0,2,1,1). Считываем аз — — 6 и, потому что ит среди всех вершин степени 1 наименьшую степень, создаем ребро (ит, ие), после чего получаем граф, изображенный на рис.
15.!04. Полагаем с!ек(ит) = 0 и с!ея(ие) = 1, поэтому восьмерка степеней теперь имеет вид (О, 0,0,2, 0,1,0,1). Считываем ае = 4 и, поскольку ие среди всех вершин степени 1 наименьший индекс, создаем ребро (ие,ив), после чего получаем граф изображенный на рис. 15.105. 674 ГЛАВА 15. Деревья Уб У' б У7 7 Рис. 15.105 Рис.
15.104 Рис. 15.103 Полагаем с(ей(774) = 1 и с(ей(об) = О, поэтому восьмерка степеней теперь имеет вид (0,0,0,1,0,0,0,1). Наконец, поскольку все последовательности прочитаны и 4(ей(о4) = 4(еК(77в) = 1, формируем ребро (474,77б) и получаем искомое дерево из примера 15.29. П ПРИМЕР 15.32. Теперь рассмотрим последовательность 9, 8, 10, 10, 1, 8, 9, 1 и воспользуемся ею для воссоздания исходного дерева из примера 15.30.
Поскольку 10, 9, 8 и 1 появляются в последовательности по два раза, то г)еК(777о) = 41еК(ье) = с(еК(47в) = 4(еК(472) = 3. А так как 2, 3 и 5 не встречаются в последовательности вообще, то с(ей(772) б(еК(473) 4(ей(о4) б1ей(об) 4(еК(77б) 4(еК(777) Запишем их с помощью десятки чисел (3,1,1,1,1,1,1,3,3,3), которую будем называть десяткой степеней. Считываем а2 = 9 и, поскольку 772 среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (иэ,772), как показано на рис. !5.106. Полагаем г(еК(77э) = 2 и б1ей(оз) = О, поэтому десятка степеней имеет вид (3,0,1,1,1,1,1,3,2,3).
Считываем а2 = 8 и, потому что пз среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (ив, оз), как показано на рис. 15.107. Полагаем дей(77в) = 2 и 4(ей(772) = 0; десятка степеней теперь имеет вид (3, О, О, 1, 1, 1, 1,2,2,3). Считываем аз = 10 и, поскольку о4 среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (772о,о4), как показано на рис. 15.108. Рис. 15.105 Рис. 15.107 Рис. 15.106 Полагаем с(ей(472о) = 2 и с(еК(о4) = 0; десятка степеней теперь имеет вид (3,0,0,0,1,1,1,2,2,2). Считываем а4 = 10 и, так как об среди всех вершин РАЗб(ЕП 15.5.
Остовные деревья 675 степени 1 имеет наименьший индекс, создаем ребро (его,ье), как показано на рис. 15.109. Полагаем г!ея(ю д) = 1 и с!ея(оз) = О, поэтому десятка степеней теперь имеет вид (3,0,0,0,0,1,1,2,2,1). Считываем аз = 1 и поскольку пе среди всех вершин степени 1 имеет наименьший индекс, создаем ребро (о~, вв) рис. 15.110. Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
