Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 117
Текст из файла (страница 117)
,,/ ~,„ а Ь Рис. 15.49 4. Для дерева, изображенного на рис. !5.50, а) приведите инфиксную запись вершин дерева; ГЛЯВА 15. Деревья б) приведите префиксную запись вершин дерева; в) приведите постфиксную запись вершин дерева. а с Рис. ЫЯ Рис. Ы.50 5. Для дерева, изображенного на рис. !5.51, а) приведите инфиксную запись вершин дерева; б) приведите префиксную запись вершин дерева; в) приведите постфиксную запись вершин дерева.
6. Для дерева, изображенного на рис. 15.52, а) приведите инфиксную запись вершин дерева; б) приведите префиксную запись вершин дерева; в) приведите постфиксную запись вершин дерева. г' а Ь 1 п1 и Рис. 15.52 7. Дана инфиксная запись (а+ Ь) х ш а) найдите бинарное дерево, задающее это выражение; б) укажите префиксную запись этого выражения; в) укажите постфиксную запись этого выражения.
8. Дана инфиксная запись (а+ Ь) х (с+И): а) найдите бинарное дерево, задающее это выражение; б) укажите префиксную запись этого выражения; в) укажите постфиксную запись этого выражения. 9. Дана инфиксная запись Иа+ Ь) х с) —: (с+ д): а) найдите бинарное дерево, задающее это выражение; б) укажите префиксную запись этого выражения. в) укажите постфиксную запись этого выражения. 10. Дана инфиксная запись (а ис Ь) + (с х (с)+ е)): а) найдите бинарное дерево, задающее это выражение; б) укажите префиксную запись этого выражения; в) укажите постфиксную запись этого выражения.
РАЗДЕЛ тб.4. Обход бонарных деревьев 657 Дана инфиксная запись (а х (Ь+ (Ы вЂ” (е+ 7)))) + ((д + Ь) х (1 + д)): а) найдите бинарное дерево, задающее это выражение; б) укажите префиксную запись этого выражения; в) укажите постфиксную запись этого выражения. Дана инфиксная запись (а+ Ь) х ((Ие — У) + д) —: Ь) — 1): а) найдите бинарное дерево, задающее это выражение; б) укажите префиксную запись этого выражения; в) укажите постфиксную запись этого выражения. 12. 13. Дана инфиксная запись (((а + Ь) — с) х и) ьь (е — (7 х (д + и))): а) найдите бинарное дерево, задающее это выражение; б) укажите префиксную запись этого выражения; в) укажите постфиксную запись этого выражения. 14.
Найдите такое бинарное дерево, обход которого в центрированном порядке дает асЬде, а обход в обратном порядке дает аЬсео. 15. Найдите такое бинарное дерево, обход которого в центрированном порядке дает осбеке, а обход в обратном порядке дает асе6Ь. 16. Найдите такое бинарное дерево, обход которого в центрированном порядке дает асЫеуд, а обход в обратном порядке дает г)сЬ|ед.
17. Найдите такое бинарное дерево, обход которого в центрированном порядке дает асЫе~д, а обход в обратном порядке дает ебсаЬгд. 18. Найдите дерево, содержащее не менее трех вершин, инфиксная запись которого совпадает с префиксной. 19. Найдите дерево, содержащее не менее трех вершин, инфиксная запись которого совпадает с постфиксной. постфиксное выражение аЬсд. 21. Постройте три неизоморфных бинарных дерева, которые при обходе дают префиксое выражение абеб. 22. Докажите, что задание для дерева инфиксного и постфиксного выражений однозначно определяет его структуру.
23. Если все арифметические операции бинарные, то какое из приведенных ниже выражений истинно для дерева, задающего данное арифметическое выраже- ние) а) Бинарное дерево сбалансировано. б) Бинарное дерево полное. в) Лист может быть арифметическим выражением. г) Внутренняя вершина должна быть арифметическим выражением. 24. Напишите алгоритм, который правильным образом расставляет скобки в ин- фиксном арифметическом выражении, полученном при обходе дерева в цен- трированном порядке.
25. Сформулируйте необходимые и достаточные условия, при выполнении которых выражение было бы постфиксным арифметическим выражением, 26. Арифметическая операция возведения в степень является бинарной или унарной) Почему? Приведите пример унарной арифметической операции. 20. Постройте три неизоморфных бинарных дерева, которые при обходе дают 658 ГЛАВА 15. Деревья 27. Опишите, где и каким образом алгоритм ИБД покажет, что деревья, изображенные на рис. 15.53, не изоморфны.
15.5. ОСТОВНЫЕ ДЕРЕВЬЯ В разделе б.З остовное дерево было определено как дерево Т, которое является подграфом графа С и таким, что каждая вершина в С является вершиной в Т; показано также, что каждый связный граф имеет остовное дерево. В данном разделе рассматриваются два метода построения остовного дерева. Первый — метод поиска в ширину, а второй — метод поиска в глубину.
Начнем с метода поиска остовного дерева в ширину. Согласно методу произвольную вершину ео графа С выбираем в качестве корня дерева Т. Для каждой вершины е графа С, смежной с вершиной оо, в дерево Т добавляется вершина е и ребро 1с, ео1. Это вершины уровня 1. Затем берем каждую вершину о, уровня 1 и для каждой вершины еу графа С, смежной с вершиной и; из тех, что еще не выбраны, добавляем в дерево Т вершину ьу и ребро (и„оД. Вершины, добавленные на этом этапе, — это вершины уровня 2. Продолжаем процесс, пока в графе С не останется вершин, которые можно было бы добавить в дерево. По построению Т является деревом.
Если расстояние от оо до вершины о графа С равно и, то эта вершина будет добавлена в дерево на уровне и. Следовательно, Т несомненно является остовным деревом. При построении алгоритма требуется наверняка знать, что некоторые вершина и ребро уже были добавлены в дерево, с тем чтобы, с одной стороны, описывать дерево, а с другой стороны, — исключать возможность повторного использования вершин, так как в противном случае мы не получим дерево. Требуется также знать уровень, на котором добавляется вершина, поскольку для определения листьев на следующем уровне эффективнее использовать только вершины, добавленные на последнем уровне. При определении новых вершин для добавления в дерево необходимо также иметь возможность выбора вершин по одной. Существует несколько способов решения такого рода задач, в том числе решения с использованием массивов и очередей, поэтому мы не будем подробно останавливаться на том, как определить "следующую" вершину.
Можно считать, что вершины графа С предварительно упорядочены. Пусть И и Е обозначают множество вершин и множество ребер графа С, и пусть Ъ'т и Ет обозначают множество вершин и множество ребер дерева Т. При добавлении в дерево вершины е мы будем обозначать через Т,(е) уровень, на котором она добавляется. РАЗДЕЛ 15.5. Остоеные деревья 669 Алгоритм поиска остовного дерева в ширину — ПОДШ(С:) (1) ВыбРать пРоизвольный элемент оо гРафа С. ПУсть оо Е г'с и Цоо) = О.
(2) Для всех о Е Ъ' — Ъ'т таких, что ю смежна с ио, положить ю Е У~, (оо, о) Е Е и Ь(ю) = 1. (3) Пусть 4 = 1. (4) Выбрать ю Е $'~ такое, что Цо,) = 1. (5) Выбрать о е Ъ' — 'г'~ . Если о смежна с с1, положить ю е Ъ'~, (ео, с) е Ет и Цо) = 1+1. (б) Продолжать шаг 5, пока все элементы множества Ъ' — Ъ'т не будут рас- смотрены. (Обратите внимание, что Ъ' — Ъ'т постоянно меняется.) (7) Повторять шаги 4, 5, и б, пока все о такие, что Цо ) = 1, не будут выбраны. (8) Положиты = г + 1. (9) Повторять шаги 4-8 до У = Ут'', ПРИМЕР 16.21.
Рассмотрим граф, изображенный на рис. 15.54. Предположим, что вершина оо выбрана в качестве первой вершины. Тогда Ь(со) = О и со Е $'~. Поскольку ог является смежной с оо, положим ог Е Ъ'~, (оо, о~~ Е Е~ и Ь(иг) = 1. Вершина оз также смежна с юо, поэтому положим га Е Ъ', (ео,гз) е Е и Доз) = 1. Наконец, веРшина из тоже смежна с оо, поэтомУ полагаем оз Е Ът, (оо,оз) Е Е~ и Ь(из) = 1. На данный момент имеем дерево, изображенное на рис. 15.55.
"! "г "з Рис, 15.55 Рис. 15.54 Теперь рассматриваем вершины о такие, что Цо) = 1. Начинаем с ог и находим неиспользованные вершины, смежные с юы Поскольку вершина те смежна с гы полагаем сз Е Ъ'~, (си ге) Е Е и Цоз) = 2. Больше нет неиспользованных и смежных с ю, вершин, поэтому переходим к сз. Поскольку о4 смежна с сз, полагаем юс Е Ъ'т, (оз, юз) Е Е~ и Цо4) = 2. ТепеРь все веРшины использованы, процесс завершен.
В результате имеем дерево, изображенное на рис. 15.55. те е Рис. 15.55 660 ГПАВА »5. Деревья ПРИМЕР 16.22. Рассмотрим граф, изображенный на рис. 15.5?. "о то !7 !б Рис. 15.57 Как и раньше, выберем ио как начальную вершину. Тогда Цео) = 0 и ио Е Ъ'~. ПосколькУ ипиъ из, иб, ив ЯвлЯютсЯ смежными с ио, положим и» 6 Ъ'~, (ио,и») 6 Е~ и Е(и») = 1, где 1 <» < 5. После этого получаем дерево, изображенное на рнс. 15.58. о Рис.
15.58 Теперь начинаем на уровне 1 с вершины и». На этом уровне находятся: вершина иа, смежная с и», вершина и»о, смежная с из, вершины ип и и»б, смежные с иб, и и»в, и»в, смежные с ив Поэтому ив,и»о,ип,и»4,еш,и»в 6»', б(иа) = т Циш) = б (и»») = » (и»4) = б (и»в) = б (и»в) — 2»» (и»~ »»а)~ (»з»»10)~ (иб и»1)~ (иб, и»4), (ив, и»з), (ив, и»в) 6 Е~ В результате получаем дерево, изображенное на рис.
15.59. Рис Г559 Теперь начинаем на уровне 2. На этом уровне: вершины ит,ив,иа, смежные с иа, и»г, смежная с ип, и»з смежная с и»4, и»а, смежная с и»в, и ипч смежная с и»в Поэтому ет ив,ив,и»г,и»з,и»а,и»т е 17б, (ив,ит),(ив,ив),(иа,иа) (и»»,и»г), (и»4, и»з), (и»а, и»з), (и»т, и»в) Е Е, и Цит) = Цив) = » (иа) = Цигг) = » (и»з) = Ци»в) = Ци»т) = 3. В результате получаем дерево, изображенное на рис. 15.60. РАЗДЕЛ Г5.5.
Остоеные деревья 661 "в Рис. !5. 60 При поиске в ширину первым делом отыскиваются все вершины, смежные с заданной вершиной, а потом осуществляется переход на следующий уровень. При поиске в ширину усилия направлены на построение для дерева как можно более длинного пути. Когда путь заходит в тупик и формирует лист, необходимо возвращаться к родителю листа и пытаться сформировать другой путь. Возврат к родителю происходит только после попытки построить все возможные пути от сына этого родителя.
В образах создаваемого дерева это означает, что мы пытаемся достичь самый глубокий, или самый большой уровень, какой только возможен. Алгоритм начинается у заданной вершины графа, которую будем считать корнем. Выбираем вершину, смежную с корнем, и формируем ребро дерева. Затем выбираем вершину, смежную с ранее выбранной вершиной, и формируем новое ребро. По ходу процесса необходимо помечать использованные вершины, с тем чтобы каждая вершина использовалась один раз.
Если, находясь в вершине с, мы выбираем другую вершину ю и обнаруживаем, что вершина ю уже была добавлена в дерево, то ребро (р,ю) между этими вершинами не может быть добавлено в дерево. Такое ребро назовем обратным ребром, и будем хранить его след для дальнейшего использования. Прежде, чем объявить ребро обратным, нужно тщательно проверить, не является ли вершина ю родителем вершины с, поскольку в этом случае ребро (с,ю) уже присутствует в дереве. По сушеству, при выборе ю как возможной новой вершины следует избегать ситуации, когда вершина ю является родителем и.
Если (е,ю) — обратное ребро, то мы остаемся в и и выбираем новую смежную вершину, если это возможно. По определению, любое ребро графа, в конечном счете, — либо ребро дерева, либо обратное ребро. В рассматриваемом алгоритме множество ребер дерева назовем РЕБРА ДЕРЕВА, а множество обратных ребер — ОБРАТНЫЕ РЕБРА. В самом начале предположим, что для "новых" вершин использованы метки "нов", а после добавления вершины в дерево эти метки меняются на "исп" — "использованные". Алгоритм поиска остовиого дерева в глубину — ПОДГ(С) (!) Пометить каждую вершину графа С символом п. (2) Выбрать произвольный элемент ио графа С и назвать его корнем дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
