Алгоритмы - построение и анализ (1021735), страница 253
Текст из файла (страница 253)
Б.7б показано бинарное дерево, отличающееся ст приведенного на рис. Б.7а позицией одного узла. Если рассматривать эти деревья как просто упорядоченные, то они являются идентичными. Пустующие места в бинарном дереве можно заполнить фиктивными листьями, как показано на рис. Б.7е, где они изображены квадратами. Так получается полностью бинарное дерево (й)11 Ьшагу ггее): каждый узел либо представляет собой лист, либо имеет степень 2. Узлы со степенью 1 в таком дереве отсутствуют.
Информация о позициях узлов, которая отличает упорядоченные деревья от бинарных, может быть расширена на случай деревьев с более чем 2 дочерними узлами в каждом узле. В позиционном дереве (роз!1!она! Сгее) все дочерние узлы данного узла пронумерованы различными натуральными числами. Если у данного узла среди дочерних нет узла с номером г', то г-й дочерний узел у данного узла отсутствует (аЬзепг). Позиционное дерево называется к-арным (lс-агу) деревом, если в нем не имеется дочерних узлов с номером, превышающим й. Таким образом, бинарное дерево представляет собой )с-арное дерево при )с = 2.
Полным 7с-арным деревом (сошр1е)е !с-агу ггее) называется /с-арное дерево, у которого все листья имеют одну и ту же глубину, а все внутренние узлы— одну и ту же степень !с. Так, на рис. Б.8 показано полное бинарное дерево высота Я ф (б1 б) Рис.
Б.7. Бинарные деревья Приложение Б. Множества н прочие художества 1223 плахха Гоьмн з х .;',,~'...; г !; ', 1, ',, ~~, .', г,,.чО,лм Рис. Б.8. Полное бинарное дерево, которое имеет высоту 3, 8 листьев н 7 внутренних узлов юторого равна 3. Сколько листьев содержится в полном 1с-арлем дереве, высота которого равна Ь? Корень имеет й дочерних узлов на глубине 1, каждый из которых содержит по 1с дочерних узлов с глубиной 2 и т.д.
Таким образом, количество листьев на глубине Ь равно 1с". Соответственно, высота полного й-арного дерева с и листьями равна 1обь и. Количество внутренних узлов полного 1с-арного дерева высоты и равно ь-~ 12 + + 16-1 '~ ~~1т й — 1 =о в соответствии с (А.5).
Таким образом, полное бинарное дерево содержит 2" — 1 внутренних узлов. Упражнения Б.5-1. Нарисуйте все свободные деревья, состоящие из 3 вершин А, В и С. Изобразите все корневые деревья с этими же узлами и узлом А в качестве корня. Нарисуйте все упорядоченные деревья с узлами А, В и С и узлом А в качестве корня. Изобразите все бинарные деревья с этими же узлами и узлом А в качестве корня. Б.5-2. Пусть С = (г', Е) — ориентированный ациклический граф, в ютором имеется вершина ио Е г', такая что имеется единственный путь от оо к любой другой вершине оба. Докажите, что неориентированная версия графа С является деревом. Б.5-3. Покажите по индукции, что количество узлов степени 2 в любом непустом бинарном дереве на 1 меньше количества листьев.
Б.5-4. Покажите с использованием метода математической индукции, что непустое бинарное дерево с и узлами имеет высоту как минимум 11кп1. Часть Ч!!!. Приложения: математические основы 1224 * Б.5-5. Определим длину внутреннего нуми (!пгегла! раг(з 1епя!Ь) полностью бинарного дерева как сумму глубин всех внутренних узлов дерева. Аналогично, под длиной внеигнего нута (ех!егпа! ра!(з 1епйгй) будем подразумевать сумму глубин всех листьев дерева. Рассмотрим полностью бинарное дерево с и внутренними узлами, длиной внутреннего пути ! и длиной внешнего пути е. Докажите, что е = ! + 2п. *Б.5-6.
Назначим каждому листу х с глубиной с( бинарного дерева Т "вес" ю (х) = 2 ". Докажите, что ,'~, 'и (х) < 1, где суммирование выполняется по всем листьям дерева Т (неравенсиюво Крафюеа (Кгай !пепла!!!у)). * Б.5-7. Покажите, что если 1, > 2, то каждое бинарное дерево с Ь листьями содержит поддерево с количеством листьев от Ь/3 до 2Ь/3 включительно. Задачи Б-1.
Раскраска графа Назовем «-раскраской (й-со!ойле) неориентированного графа С = (Ъ; Е) функцию с: У вЂ” (0,1,..., й — 1), такую что для всех ребер (п,п) Е Е Е выполняется с(и) ф с(п). Другими словами, числа 0,1,..., Й вЂ” 1 представляют й цветов, и смежные вершины графа должны иметь разные цвета. а) Покажите, что любое дерево можно раскрасить двумя цветами.
б) Покажите, что следующие утверждения эквивалентны: 1) граф С вЂ” двудольный; 2) граф С можно раскрасить двумя цветами; 3) граф С не имеет циклов нечетной длины. в) Пусть И вЂ” максимальная степень вершины в графе С. Докажите, что О может быть раскрашен при помощи Н+ 1 цветов. г) Покажите, что если граф имеет О (Щ) ребер, то его можно раскра- сить при помощи О (;Щ) цветов. Б-2. Граф дружбы Преобразуйте следующие утверждения в теоремы о неориентированных графах и докажите их. Отношение дружбы считаем симметричным, но не рефлексивным. а) В любой группе из и > 2 человек имеется два человека с одним и тем же количеством друзей из этой группы.
Приложение Б. Множества н прочие художества 1225 б) Каждая группа из шести человек содержит либо три человека, которые являются друзьями друг друга, либо три человека, никакие два из которых не являются друзьями. в) Любую группу людей можно разделить на две подгруппы так, что как минимум половина друзей каждого человека из одной подгруппы будет находиться в другой подгруппе. г) Если каждый человек в группе является другом по меньшей мере для половины группы, то можно рассадить эту группу людей за столом так, что каждый будет сидеть между двумя друзьями. Б-3. Разбиение деревьев Многие алгоритмы типа "разделяй и властвуй", работающие с графами, требуют разбиения графа на два близких по размеру подграфа.
Вопрос заключается в том, как сделать это с наименьшим количеством удаляемых ребер. а) Покажите, что удалением единственного ребра можно разбить вершины любого бинарного дерева с и вершинами на два множества, в каждом из которых оказывается не больше Зп/4 вершин. б) Покажите, что константу 3/4 из пункта а) нельзя улучшить. Для этого приведите пример простого бинарного дерева, для которого при удалении любого ребра в одной из частей оказывается ровно Зп/4 вершин. в) Покажите, что, удаляя не более О (18 и) вершин, мы можем разбить бинарное дерево с п вершинами на такие два множества А и В, что (А~ = '1п/23 и )В! = ~п/21.
Заключительные замечания Основатель символьной логики Дж. Буль (О. Воо!е) ввел многие обозначения, связанные с множествами, в своей книге, изданной в 1854 году. Современная теория множеств (в первую очередь теория мощности бесконечных множеств) была создана Кантором (О. Салгог) в 1874-1895 гг. Термин "функция" введен Лейбницем (0.%. Ьейоп1х) для некоторых типов математических формул. Его весьма ограниченное определение функции позже неоднократно обобщалось и расширялось. Создание теории графов относится к 1736 году, когда Л.
Эйлер (1.. Еи1ег) доказал невозможность такого обхода семи мостов в Кенигсберге, при котором выполняется по одному проходу по каждому из мостов, и обход завершается в исходной точке. Полезным справочником, содержащим множество определений и свойств графов, является книга Харари (Нагагу) 1138!. ПРИЛОЖЕНИЕ В Комбинаторика и теория вероятности В этом приложении вы познакомитесь с азами комбинаторики и теории вероятности.
Если вы уже знакомы с этими разделами математики, то можете просто бегло ознакомиться с началом приложения и обратить большее внимание на его окончание. Большинство глав в этой книге не используют теорию вероятностей, но некоторые целиком построены на ее применении. В разделе В.1 приведен обзор основ комбинаторики, включая формулы для количества перестановок и сочетаний. В разделе В.2 вас ожидает встреча с аксиомами теории вероятности и основами распределения вероятностей. Случайные величины, а также математическое ожидание и дисперсия рассматриваются в разделе В.З. Раздел В.4 посвящен геометрическому и биномиальному распределениям, изучение которых продолжается в разделе В.5, где обсуждается проблема "хвостов" распределений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
