Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 274
Текст из файла (страница 274)
Б.7,(б) показано бинарное дерево, отличающееся от приведенного на рис. Б.7, (а), позицией одного узла. Если рассматривать эти деревья как просто упорядоченные, то они являются идентичными. Можно представить позиционную информацию в бинарном дереве с помощью внутренних узлов упорядоченного дерева, как показано на рис. Б.7,(в). Идея заключается в том, чтобы заменить каждый отсутствующий дочерний узел узлом, не имеющим потомков. Эти листья на рисунке изображены квадратами.
Так получается полностью бинарное дерево (йзй Ьтпагу ггее): каждый его узел либо Заметам, что степень узла зависит от того, рассмягрнааем лн мы дерево с корнем нлн свободное дерево. Степень вершнны в своболном дереве, как н в любом неорнентнрованном графе, равна колнчесгву сменных вершин В дереве с корнем степень равна количеству дочерннх узлов — родательскнй узеа прн вычнсленнн степени не учитывается. Прилвжелие д Мналсестяо ы щечке лудожестеа (23! (б) (в) (в) Рис.
Б.7. Бииерные деревья. (я) Бинерное дерево, изображенное е стандартном виде, Левый ребенок узла изобряжаетсл нике и левее этого угля) прелый ребенок изображается ниже и правее. (6) Бинарное дерево, отличное от дерева из части (я). В части (а) левым дочерним узлом узла 7 является узел 5, я правый дочерний узел отсутствует. В части (б) у узла 7 отсутствует левый дочерний узел, я узел 5 яяивется его правым дочерним узлом. Клк упорядоченные деревья деревья я честял (я) и (б) идентичны, но кяк бинарные дереяья они различны. (и) Бинарное дерево из (я), представленное янугренними узлами полностью бинарного дерева (упорядоченного дереке, я ипором каждый янугренний узел имеет степень 2).
Листья этого дерева покязяны кяалрятикями. представляет собой лист, либо имеет степень 2. Узлы со степенью 1 в таком дереве отсутствуют. Следовательно, порядок дочерних узлов сохраняет информацию о местоположении. Информация о позициях узлов, которая отличает упорядоченные деревья ст бинарных, может быть расширена на случай деревьев более чем с 2 дочерними узлами в каждом узле. В позиционном дерике (рогйбопа1 (гее) все дочерние узлы данного узла пронумерованы различными натуральными числами. Если у данного узла среди дочерних нет узла с номером з', то з-й дочерний узел у данного узла оп(сутяги(пуп)и (аЬзепг).
Позиционное дерево называется 1очгрным (Ь-агу) деревом, если в нем нет дочерних узлов с номером, превышанмцнм /с. Таким образом, бинарное дерево представляет собой Ь-арное дерево прн Ь = 2. Полным Ь-(гримм деревом (сагир!е(е Ь-агу ггее) называется lс-арное дерево, все листья которого имеют одну н ту же глубину, а все внутренние узлы — одну н ту же степень /с. Так, на рнс. 8.8 показано полное бинарное дерево, высота которого равна 3.
См)лько листьев содержится в полном Ь-арном дереве, высота которого равна Ь? Корень имеет Й дочерних узлов на глубине 1, каждый нз которых содержит по /с дочерних узлов с глубиной 2 н тд. Таким образом, количество листьев на глубине Ь равно /Р. Соответственно, высота полного /с-арного дерева с и лнстьямн равна 1ойа и. Количество внутренних узлов полного Й-арного дерева высоты Ь равно Ь вЂ” 1 1+Ь+)г+ +Ьь — 1 ~~,'Ь (=и Ьь /с — 1 ггуг Часть ПП.
Прилолселил математические основы Ъ.з. ! ! ~ ) глубава 2 (' ) (' ~ ~~) (:~ (,'Л .. 1 ';..' глзалтз Рис. Б.В. Полное бинарное дерево высотой 3 с восемью листьями и семью внутренними узлами. согласно (А.5). Таким обраюм, полное бинарное дерево содмзжит 2" — 1 внутрен- них узлов.
Упражнения Б.5.1 Нарисуйте все свободные деревья, состоящие из трех вершин — х, у и л. Изобразите все корневые деревья с этими же узлами и узлом х в качестве корня. Нарисуйте все упорядоченные деревья с узлами х, у и л и узлом х в качестве корня. Изобразите все бинарные деревья с этими же узлами и узлом х в качестве корня. Б'.5.2 Пусть С = (й, Е) — ориентированный ациклический граф, в котором имеется вершина еп Е Ъ', такая, что имеется единственный путь из со в каждую другую вершину н б й'. Докажите, что неориентированная версия графа С является деревом.
Б.5.3 Покажите по индукции, что количество узлов степени 2 в любом непустом бинарном дереве на единицу меньше количества листьев. Сделайте отсюда вывод о том, что количество внутренних узлов полного бинарного дерева на единицу меньше количества листьев. Б.5.4 Покажите с использованием метода математической индукции, что непустое бинарное дерево с и узлами имеет высоту как минимум (1й и!.
Б.5.5 * Определим длину внутреннего пути (!пзегпа! ра!)2 !епйбз) полностью бинарного дерева как сумму глубин всех внутренних узлов дерева Аналогично под ззлиной внеьинего пути (ехзегпа! раг)2 !епй2п) будем подразумевать сумму глубин всех листьев дерева. Рассмотрим полностью бинарное дерево с и внутренними узлами, длиной внутреннего пути з и длиной внешнего пути е. Докажите, что е = з + 2п.
Приложение и Мнкисества и прочие худажестаа 3233 Б.5.6 * Назначим каждому листу х с глубиной б бинарного дерева Т "вес" ш(х) = 2 ~. Докажите, что 2',, тс(х) < 1 (керавенство Крафта (Кгатт !пеона!!ту)). Б.5. 7 * Покажите, что если Е > 2, то каждое бинарное дерево с Е листьями содержит поддерево с количеством листьев от Ь/3 до 2Ь/3 включительно. Задачи Б.1. Раскраска графа Определим для заданного неориентированного графа С = ()г, Е) и-раскраску (/с-со!оппй) графа С как функцию с: )г -+ (0,1,...,й — 1), такую, что с(и) ~ с(с) для каждого ребра (и,о) Е Е.
Другими словами, числа О, 1,..., !г — 1 представляют /с цветов, и смежные вершины должны иметь разные цвета. а. Покажите, что любое дерево можно раскрасить двумя цветами. б. Покажите, что следующие утверждения эквивалентны: !. граф С двудольный; 2. граф С раскрашивается двумя цветами; 3. граф С не имеет циклов нечетной длины. в.
Пусть д — максимальная степень вершины в графе С. Докажите, что граф С может быть раскрашен д + 1 цветами. г. Покажите, что если граф имеет О(!)г!) ребер, то его можно раскрасить О( „Щ) цветами. Б.2. Граф дрзогсбы Преобразуйте следующие утверждения в теоремы о неориентированных графах и докажите их. Отношение дружбы считаем симметричным, но не рефлексивным. а.
В любой группе из и > 2 человек имеется два человека с одним и тем же количеством друзей из этой группы. б. Каждая группа из шести человек содержит либо три человека, которые являются друзьями друг друга, либо три человека, никакие два из которых не являются друзьями. в. Любую группу людей можно разделить на две подгруппы так, что как минимум половина друзей каждого человека из одной подгруппы будет находиться в другой подгруппе. Части Р7И. Прилоокекии: математические основы * Если каждый человек в группе является другом по меньшей мере для половины группы, то можно рассадить эту ~руину людей за столом так, что каждый будет сидеть между двумя друзьями.
Б.З. Разбиение деревьев Многие алгоритмы типа "разделяй и властвуй", работающие с графами, требуют разбиения графа на два близких по размеру подграфа, порождаемых разбиением множества вершин. Вопрос заключается в том, как сделать это с наименьшим количеством удаляемых ребер. Должно выполняться условие, что если две вершины находятся в конечном итоге в одном и том же поддереве после удаления ребер, то они должны находиться и в одном н том же разбиении вершин. в. Покажите, что удалением единственного ребра можно разбить вершины любого бинарного дерева с п вершинами на два множества, А и В, такие, что )А! < Зп/4 и )В! < Зп/4. б. Покажите, что константу 3/4 из п. (а) нельзя улучшить.
Для этого приведите пример простого бинарного дерева, для которого при удалении любого ребра в одной из частей оказывается ровно Зп/4 вершин. в. Покажите, что, удаляя не более О(18 и) ребер, можно разбить бинарное дерево с п вершинами на такие два множества, А и В, что ~А( = 1п/2)' и ~В) = ~п/21. Заключительные замечания Основатель символьной логики Дж.
Буль (О. Воо!е) ввел многие обозначения, связанные с множествами, в своей книге, изданной в 1854 году. Современная теория множеств (в первую очередь, теория мощности бесконечных множеств) была создана Г. Кантором (О. Сапгог) в 1874 — 1895 годах. Термин "функция" введен Г.В. Лейбницем (0.%. Ье)Ьп)х) для неюторых типов математических формул. Его весьма ограниченное определение функции позже неоднократно обобщалось и расширялось. Создание теории графов относится к 1736 году, югда Л. Эйлер (Ь. Еп1ег) доказал невозможность такого обхода семи мостов в Кенигсберге, при котором выполняется по одному проходу по каждому из мостов и обход завершается в исходной точке.
Полезным справочником, содержащим множество определений и свойств графов, является книга Харари (Натягу) [1591. Приложение В. Комбинаторика и теория вероятности В этом приложении вы познакомитесь с азами комбинаторики и теории вероятности. Если вы уже знакомы с этими разделами математики, то можете просто бегло ознакомиться с началом приложения и обратить больше внимания иа его окончание.
В большинстве глав этой книги теория вероятности не используется, но некоторые целиком построены на ее применении. В разделе В.! приведен обзор основ комбинаторики, включая формулы для количества перестановок и сочетаний. В разделе В.2 вас ожидает встреча с аксиомами теории вероятности и основами распределения вероятностей. Случайные величины, а также математическое ожидание и дисперсия рассматриваются в разделе В.З. Раздел ВА посвящен геометрическому и биномиальному распределениям, изучение которых продолжается в разделе В.5, где обсуждается проблема "хвостов" распределений. В.1. Основы комбинаторики Комбинаторика пытается ответить на вопрос "Сколько?", не выполняя перечисления.
Например, вы можете спросить "Сколько всего имеется различных и- битовых чисел?" или "Сколькими способами можно упорядочить п различных чисел?" Здесь вы познакомитесь с азами комбинаторики, которые предполагают знание основ теории множеств, так что, надеемся, вы основательно проработали раздел Б.1. Правила суммы и произведения Иногда множество, количество элементов которого необходимо подсчитать, можно выразить как объединение непересекающихся множеств или как декартово произведение множеств.
Правило суммы гласит, что количество способов, которыми можно выбрать элемент из одного из двух непересекающихся множеств, равно сумме мощностей этих множеств. То есть, если А и  — два конечных множества без общих членов, то ~А 0 В! = )А! + 1В~, что следует из уравнения (Б.З). Например, если каждый символ в номере машины должен быть либо латинской буквой, либо цифрой, то всего имеется 26 + 10 = 36 различных вариантов выбора этого символа, так как всего имеется 26 вариантов выбора буквы и 10 — цифры. /По Части И//. Прияоокенинс математические основы Правило нронзведення гласит, что количество способов, которыми можно выбрать упорядоченную пару, равно количеству вариантов выбора первого элемента, умноженному на количество вариантов выбора второго элемента. То есть, если А и  — конечные множества, то )А х В( = (А).(В) (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
