- •Введение
- •1. Теория множеств
- •1.1. Основные понятия
- •1.2. Операции над множествами
- •1.3. Алгебраические свойства операций над множествами
- •1.4. Нечёткие множества
- •2. Элементы комбинаторики
- •2.1. Основные правила комбинаторики
- •2.2. Выборки элементов без повторений
- •2.3. Выборки элементов с повторениями
- •2.4. Объединение комбинаторных конфигураций
- •2.5. Бином Ньютона
- •3. Отношения на множествах
- •3.1. Декартово произведение множеств
- •3.2. Булев куб и его свойства
- •3.3. Понятие отношения
- •3.4. Операции над отношениями
- •3.5. Свойства отношений на множестве
- •3.6. Отношения эквивалентности, толерантности и порядка
- •3.7. Нечеткие отношения
- •3.8. Понятие отображения
- •3.9. Алгебраическая операция
- •3.10. Общие сведения об алгебраических системах
- •4 Булевы функции
- •4.1. Основные определения и операции над высказываниями
- •4.2. Типы пф.
- •4.3. Равносильность формул
- •4.4. Дизъюнктивные и конъюнктивные нормальные формы
- •4.5 Алгоритм приведения пф к нормальным формам
- •4.6 Аналитический способ приведения к сднф
- •4.7. Табличный способ приведения к сднф
- •4.8. Табличный способ приведения к скнф
- •4.9. Логическое следствие
- •4.10. Алгоритм проверки правильности рассуждений
- •4.11. Алгоритм определения всех логических следствий из данных посылок
- •4.12. Алгоритм определения всех посылок, логическим следствием которых является данная формула
- •4.13. Полнота систем булевых функций
- •4.14. Полином Жегалкина
- •4.15. Замкнутость
- •4.16. Теорема Поста
- •4.17. Нечеткая логика
- •5. Многозначные функции
- •5.1. Функции и формулы k-значной логики
- •5.2. Полнота и замкнутость функций k-значной логики
- •5.3. Особенности k – значной логики
- •6.. Основные понятия теории графов.
- •6.1. Задачи теории графов.
- •6.2. Основные определения.
- •6.3. Степени вершин графа.
- •6.4. Изоморфизм графов.
- •6.5. Матричные способы задания графов.
- •6.6. Основные операции над графами.
- •6.7. Маршруты в графах
- •6.8. Связность в графах.
- •Связность и матрица смежности графа.
- •6.9. Матрица взаимодостижимости.
- •6.10. Деревья Свободные деревья.
- •Ориентированные, упорядоченные и бинарные деревья.
- •6.11. Эйлеровы графы.
- •6.12 Гамильтоновы графы.
- •6.13. Планарные графы.
- •6.14. Потоки в сетях. Основные определения.
- •Теорема Форда и Фалкерсона.
- •Алгоритм построения максимального потока в сети.
- •7. Конечные автоматы
- •7.1. Понятие конечного автомата Общие сведения о конечных автоматах
- •7.2. Абстрактное определение конечного автомата
- •7.3. Автоматная функция и её моделирование Понятие ограниченно детерминированной функции
- •Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •7.4. Эксперименты с автоматами
- •8. Рекуррентные уравнения
- •8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения
- •8.2. Решение линейного неоднородного рекуррентного уравнения
- •8.3. Решение рекуррентного уравнения для чисел Фибоначчи
- •Заключение
- •Библиографический список
- •Оглавление
- •1.Теория множеств 5
- •2 Элементы комбинаторики 14
- •3 Отношения на множествах 22
- •4. Булевы функции 42
- •5. Многозначные функции 64
- •6. Основные понятия теории графов 70
- •7. Конечные автоматы 106
- •8. Рекуррентные уравнения 120
- •394026 Воронеж, Московский просп., 14
Ориентированные, упорядоченные и бинарные деревья.
Ориентированным деревом (ордеревом, корневым деревом) называется орграф со следующими свойствами.
Существует единственная вершина, полустепень захода которой равна 0. Она называется корнем ориентированного дерева.
Полустепень захода всех остальных вершин равна 1.
Каждая вершина достижима из корня.
Например:
а ) все возможные ориентированные деревья с 3-я вершинами:
Рис. 29
б ) с 4-я вершинами :
Рис. 30
Концевая (висячая) вершина ордерева называется листом. Путь из корня в лист называется ветвью.
Уровень вершины ордерева – это расстояние от корня до вершины. Корень имеет уровень 0. Вершины одного уровня образуют ярус дерева.
Эквивалентное определение ориентированного дерева.
Ордерево D – это конечное множество вершин, таких что:
1) имеется одна вершина r, называемая корнем данного дерева;
2) остальные вершины содержаться в k попарно непересекающихся множествах D1,…Dk , каждое из которых является ордеревом. (k0) D= .
Множества D1,…,Dk называются поддеревьями.
Упорядоченным деревом называется ориентированное дерево, в котором:
задан порядок поддеревьев
каждое поддерево Di является упорядоченным поддеревом.
дерево с одной вершиной считается упорядоченным поддеревом.
Замечание. При изображении ориентированных деревьев принято соглашение о том, что корень размещается вверху. В связи с этим все дуги оказываются ориентированными сверху вниз, поэтому стрелки на них можно не изображать. В результате, диаграммы свободных, ориентированных и упорядоченных деревьев оказываются графически неотличимыми. В этом случае требуется дополнительное указание, какого класса дерево изображено на диаграмме. Обычно это ясно из контекста.
Н апример: Имеются 3 диаграммы деревьев:
Рис. 31
Как упорядоченные деревья, они все различны. Как ориентированные деревья D1=D2D3. Как свободные деревья, они все изоморфны D1=D2=D3.
Терема 3. Число упорядоченных деревьев с m дугами не превосходит 4m.
Доказательство: Рассмотрим алгоритм обхода упорядоченного дерева, называемого «поиском в глубину». Этот обход рекурсивно описывается следующим образом:
Начать с корня. Пока есть деревья выполнять.
Перейти в корень очередного поддерева, обойти это поддерево в глубину.
Вернуться в корень исходного поддерева.
В результате «обхода в глубину» по каждой дуге проходят ровно 2 раза: один раз при переходе в очередное поддерево, второй раз – при возвращении из него. В соответствии с «обходом в глубину» строиться последовательность из нулей и единиц. На каждом шаге записывается нуль, если происходит переход в очередное поддерево, а единица – при возвращении из поддерева. В результате получается последовательность из нулей и единиц длины 2m, которая называется кодом дерева. По этому коду однозначно восстанавливается дерево, т.к. каждый очередной разряд однозначно указывает, начинать ли строить новое очередное поддерево или возвращаться на ярус ближе к корню. Таким образом, упорядоченных деревьев с m дугами не больше, чем последовательностей из нулей и единиц длины 2m. А их число равно 22m=4m. Теорема доказана.
Изоморфизм ориентированных деревьев определяется так же, как и изоморфизм графов, но с дополнительным условием - корень должен отображаться в корень. Для упорядоченных деревьев требуется также сохранение порядка поддеревьев.
Следствие. Число неизоморфных ориентированных или свободных деревьев с m ребрами не превосходит 4m.
Доказательство: Выделив в неизоморфных свободных деревьях по одной вершине, мы получаем неизоморфные ориентированные деревья. Упорядочивая поддеревья в неизоморфных ориентированных поддеревьях, мы получаем упорядоченные деревья. Поэтому число неизоморфных свободных деревьев с m ребрами не превосходит числа неизоморфных ориентированных деревьев с m дугами, которое в свою очередь не превосходит числа неизоморфных (различных) упорядоченных деревьев с m дугами. Отсюда из теоремы 3 следует утверждение следствия.
Бинарное дерево – это конечное множество вершин, которое либо пусто, либо состоит из корня и не более двух непересекающихся бинарных поддеревьев – левого и правого. Заметим, что бинарное дерево не является упорядоченным.
П ример: На рисунке представлены два различных бинарных дерева:
Рис. 32
То есть, эти деревья изоморфны как упорядоченные, ориентированные и свободные, но не изоморфны как бинарные деревья.