Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 254
Текст из файла (страница 254)
Б.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, где обсуждается проблема "хвостов" распределений. В.1 Основы комбинаторики Комбинаторика пытается ответить на вопрос "Сколько?", не выполняя перечисления. Например, вы можете спросить "Сколько всего имеется различных и- битовых чисел?" или "Сколькими способами можно упорядочить и различных чисел?" Здесь мы познакомимся с азами комбинаторики, которые предполагают знание основ теории множеств, так что, надеемся, вы основательно проработали предыдущее приложение. Приложение В.
Комбинаторика и теория вероятности 1227 Правила суммы и произведения Множество, количество элементов которого мы хотим подсчитать, иногда можно выразить как объединение непересекающихся множеств или как декартово произведение множеств.
Правило суммы гласит, что количество способов, которыми можно выбрать элемент из одного из двух непересекающихся множеств, равно сумме мощностей этих множеств. То есть, если А и  — два конечных множества без общих членов, то )А 1.1 В1 = )А) + (В(, что следует из уравнения (Б.З). Например, если каждый символ в номере машины должен быть либо латинской буквой, либо цифрой, то всего имеется 2б+ 10 = 36 различных вариантов выбора этого символа, т.к. всего имеется 26 вариантов выбора буквы и 10 — цифры.
Правило произведения гласит, что количество способов, которыми можно выбрать упорядоченную пару, равно количеству вариантов выбора первого элемента, умноженному на количество вариантов выбора второго элемента. То есть, если А и  — конечные множества, то )А х В) = )А!.1В~ (см. уравнение (Б.4)). Например, имея 28 сортов мороженого и 4 разных сиропа, можно приготовить 28 4 = 112 различных вариантов мороженого с сиропом.
Строки Сюирокой (мпп8) на конечном множестве Я называют последовательность элементов Я. Например, вот восемь двоичных (составленных из 0 и 1) строк длины 3: 000, 001, 010, 011, 100, 101, 110, 111. Иногда строки длиной к называются й-сюро«ами. Подстрокой (зпЬз1г1п8) в' строки в называется упорядоченная последовательность элементов в. Подстрока длиной /с называется к-подстрокой. Например, 010 — 3-подстрока строки 01101001 (начинающаяся с 4 позиции строки); 111 же подстрокой указанной строки не является. й-сюирока на множестве Я может рассматриваться как элемент декартова произведения Я", так что всего имеется 15~ строк длины 1с, в частности, число двоичных к-строк равно 2 .
Интуитивно это очевидно — при построении к-строки ь из множества с и элементами у нас имеется и вариантов выбора первого элемента строки; для каждого из первых элементов у нас имеется и вариантов выбора второго элемента строки, и так /с раз. Это дает нам общее количество /с-строк, равное п и.... п=п". Перестановки Пересюиановкой (реппп1абоп) конечного множества 5 называется упорядоченная последовательность всех элементов Я, в которой каждый элемент встречается ровно один раз.
Например, если Я = (а, Ь, с), то имеется шесть перестановок Я: аЬс, асЬ, Ьас, Ьса, саЬ, сЬа. Часть Ч1П. Приложения: математические основы 1228 Всего имеется и! перестановок множества из п элементов, поскольку первый элемент может быть выбран п способами, второй — п — 1 способом, третий— и — 2 и т.д. и-нерестановкой' Я называется упорядоченная последовательность lс элементов из Я, в которой ни один элемент не встречается дважды (таким образом, обычная перестановка представляет собой и-перестановку множества из и элементов.
Для множества Я = (а, Ь, с, с!) имеется двенадцать 2-перестановок: аЬ, ас, ас1, Ьа, Ьс, Ы, са, сЬ, сс1, с!а, с1Ь, с!с. Количество Й-перестановок множества из и элементов равно и! п(п — 1) (и — 2) (и — 1с+ 1) = (и — !с)! (В.1) поскольку имеется п способов выбора первого элемента, п — 1 — второго и т.д., до последнего, !с-го элемента, который можно выбрать из оставшихся и — и + 1 элементов множества. Сочетания Сочетаниями (к-сошЬ(папоп) из п элементов по !с называются к-элементные подмножества п-элементного множества. Например, имеется шесть сочетаний по 2 элемента из множества Я = (а, Ь, с, с1): аЬ, ас, ас(, Ьс, Ы, сд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
