|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[30] Задачи к главе 5 99 Упражнения 5.5-1 Нарисуйте все деревья (без выделенного корня), содержащие три вершины А, В и С. Нарисуйте все корневые деревья с вершинами А, В и С и корнем А. Нарисуйте все (корневые) деревья с порядком на детях с вершинами А, В и С и корнем А. Нарисуйте все двоичные деревья с вершинами А, В и С и корнем А. 5.5-2 Покажите, что для любого га 7 существует дерево с га вершинами, из которого можно получить га различных корневых деревьев, объявив корнем одну из га вершин. 5.5-3 Пусть G = (V, Е) - ориентированный ациклический граф, в котором существует вершина г>о, из которой в каждую другую v G V ведёт единственный путь. Покажите, что неориентированный вариант графа G является деревом. 5.5-4 Докажите по индукции, что в любом двоичном дереве число вершин степени 2 на единицу меньше числа листьев. 5.5-5 Покажите, что двоичное дерево с га вершинами имеет высоту не меньше [lg raj. 5.5-6* Определим внутреннюю сумму длин (internal path length) для двоичного дерева, в котором каждая вершина имеет степень О или 2, как сумму глубин всех внутренних вершин. Определим внешнюю сумму длин для этого же дерева как сумму глубин всех его листьев. Пусть га - число внутренних вершин такого дерева, г и е - внутренняя и внешняя суммы длин. Докажите, что е = г + 2га. 5.5-7* Определим «вес» листа в двоичном дереве как 2 d, где d - его глубина. Докажите, что сумма весов всех листьев в двоичном дереве не превосходит 1 (неравенство Крафта, Kraft inequality) 5.5-8* Покажите, что в любом двоичном дереве с L листьями можно найти поддерево, число листьев в котором находится на отрезке [L/3,2L/3J. Задачи 5-1 Раскраска графа Назовём /г-раскраской неориентированного графа (V, Е) функцию с: V -т- {0,1,..., к - 1}, для которого с(и) ф с[у) для любых двух смежных вершин и и v. (Концы любого ребра должны иметь разные цвета.) а. Покажите, что любое дерево имеет 2-раскраску. б.Покажите, что следующие свойства неориентированного графа G равносильны: 1.Граф G двудольный. 2.Граф G имеет 2-раскраску. 3.Граф G не имеет циклов нечётной длины. в.Пусть d - максимальная степень вершин неориентированного графа G. Покажите, что G имеет (d + 1)-раскраску. г.Покажите, что если граф G имеет 0(V) рёбер, то G имеет 0(-\/ Г")-раскраску. 5-2 Графы и люди Переведите на язык неориентированных графов следующие утверждения и докажите их. (Предполагается, что отношение «быть другом» симметрично, и человек не включается в число своих друзей.) а.В любой компании из га 2 человек найдутся два человека с одинаковым числом друзей (среди присутствующих). б.В любой группе из 6 человек можно найти либо трёх человек, являющихся друзьями друг друга, либо трёх человек, никакие двое из которых не являются друзьями. в.Любую компанию людей можно развести по двум комнатам так, что для каждого человека как минимум половина его друзей окажутся в другой комнате. г.Если в компании из га человек у каждого не менее га/2 друзей, то эту компанию можно рассадить за круглым столом так, чтобы каждый сидел между двумя своими друзьями. 5-3 Разбиение деревьев на части Многие алгоритмы на графах, действующие по принципу «разделяй и властвуй», делят граф на две части, при этом желательно удалять как можно меньше рёбер и получить две части по возможности близкого размера. а.Покажите, что в любом двоичном дереве с га вершинами можно найти ребро, после удаления которого получатся две части размера не больше Зга/4 каждая. б.Покажите, что константу 3/4 в пункте (а) нельзя улучшить, приведя пример двоичного дерева, для которого после удаления любого ребра в одной из частей остаётся не менее Зга/4 вершин. в.Покажите, что множество вершин любого двоичного дерева с га вершинами можно разбить на две части А и В таким образом, что А\ = [п/2\, \В\ = [га/2], а число рёбер, соединяющих вершины из разных частей, есть О (lgra). Замечания Основатель символической логики Буль (G. Boole) ввёл многие из нынешних теоретико-множественных обозначений в книге, опубликованной в 1854 году. Современная теория множеств (прежде всего теория мощностей бесконечных множеств) была создана Кантором (С. Cantor) в 1874-1895 годах. Термин «функция» использовал Лейбниц (G.W. Leibnitz) в применении к некоторым математическим формулам. Определение функции впоследствии многократно обобщалось. Теория графов восходит к 1736 году, когда Эйлер (L. Euler) показал, что невозможно пройти по всем семи мостам города Кенигсберга по одному разу и вернуться в исходную точку. Полезным справочником по определениям и результатам теории графов является книга Харари [94]. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||