- •Учебно-методический комплекс дисциплины сд.12 дискретная математика
- •061800 «Математические методы в экономике»
- •Раздел 1. Программа учебной дисциплины. Структура программы учебной дисциплины
- •1.3 Пояснительная записка:
- •1.5. Объем дисциплины и виды учебной работы.
- •1.6 Содержание дисциплины.
- •1.7 Методические рекомендации по организации изучения дисциплины.
- •1.8 Учебно-методическое обеспечение дисциплины.
- •1.9 Материально-техническое обеспечение дисциплины.
- •1.10 Примерные зачетные тестовые задания.
- •1.11 Примерный перечень вопросов к зачету (экзамену).
- •1.12 Комплект экзаменационных билетов
- •1.13 Примерная тематика рефератов.
- •1.14 Примерная тематика курсовых работ.
- •Элементы теории множеств
- •§ 2. Бинарные операции и их свойства
- •§ 3. Операции над множествами. Законы де Моргана
- •§ 4. Вектор. Прямое произведение
- •§ 5. Мощность конечного множества
- •§ 6. Отношения и их свойства
- •§ 7. Отношение эквивалентности
- •§ 8. Отношение порядка
- •§ 9. Отображения и их свойства
- •Глава II. Элементы теории графов
- •§ 1. Графы, их вершины, рёбра и дуги
- •§ 2. Операции над графами
- •§ 3. Способы задания псевдографов. Степени вершин
- •§ 4. Отношение связности для вершин неориентированного графа
- •§ 5. Отношение достижимости для вершин орграфа
- •§ 6. Эйлеров граф и условия его существования
- •§ 7. Гамильтонов граф и условия его существования
- •§ 8. Деревья и их свойства. Цикломатическое число
- •§ 9. Формула Кэли
- •§ 10. Двудольный граф
- •§ 11. Планарность
- •§ 12. Раскраска графов
- •Глава III. Булевы функции
- •§ 1. Основные определения
- •§ 2. Свойства булевых функций
- •§ 3. Переключательные функции
- •§ 4. Совершенные нормальные формы
- •§ 5. Полнота. Примеры полных систем
- •§ 6. Замыкание и его свойства
- •§ 7. Важнейшие замкнутые классы
- •§ 8. Теорема о функциональной полноте
- •Раздел 4. Словарь терминов (глоссарий) Элементы теории множеств
- •Конечные графы
- •Функциональные системы с операциями: алгебра логики
- •Раздел 5. Практикум по решению задач (практических ситуаций) по темам лекций (одна из составляющих частей итоговой государственной аттестации) Элементы теории множеств
- •Задачи для самостоятельного решения
- •Конечные графы
- •Задачи для самостоятельного решения
- •Функциональные системы с операциями: алгебра логики
- •Задачи для самостоятельного решения
- •Раздел 6. Изменения в рабочей программе, которые произошли после утверждения программы.
- •Раздел 7. Учебные занятия по дисциплине ведут:
§ 9. Формула Кэли
Рассмотренная ниже теорема была доказана Кэли, который исследовал деревья в связи с химическими структурными формулами.
Теорема 3.6 (Кэли). Число различных деревьев, которые можно построить на n данных вершинах, равно: tn = nn2.
Чтобы вывести эту формулу, воспользуемся методом Прюфера. Обозначим элементы данного множества вершин V, расположенные в некотором фиксированном порядке, числами
1, 2, 3, ... , n. (*)
Установим теперь взаимно однозначное соответствие между множеством всех деревьев с n вершинами и множеством всех векторов (со значениями компонент от 1 до n) длиной (n2).
Согласно третьему свойству, в дереве Т найдутся хотя бы две концевые вершины. Обозначим через b1 первую концевую вершину в последовательности (*), а через e1=(a1,b1) - соответствующее концевое ребро. Удалив из дерева Т ребро e1 и вершину b1, мы получим новое дерево T1. Для T1 найдётся первая в последовательности (*) концевая вершина b2 с ребром e2=(a2,b2), удалив которое, получим дерево T2 и т.д. Наконец, после удаления ребра en2=(an2,bn2) останется единственное ребро en1=(an1,bn1), соединяющее две оставшиеся вершины. Тогда вектор (a1,a2,..., an2) однозначно определяется деревом Т и двум различным деревьям соответствуют разные векторы.
Пример. Составить вектор для данного дерева (см. рис. 3.19, а).
Решение.. Концевая вершина с самым маленьким номером - 3, а соответствующее ей концевое ребро - (2,3); поэтому принимаем a1=2 и отсекаем это ребро.
Концевая вершина с самым маленьким номером из оставшихся 4, а соответствующее ей концевое ребро - (2,4). Принимаем a2=2 и отсекаем ребро. Дальше действуем аналогично.
Требуемый вектор имеет вид: (2,2,2,1,6,6).
Покажем теперь, что, наоборот, каждое дерево Т однозначно определяется вектором
(a1,a2,..., an-2) (**)
Выполним обратное построение. Если дан вектор (**), то в последовательности (*) находится первая вершина b1, которая не содержится в (**). Это определяет ребро e1=(a1,b1).
Рис.
3.19.
Пример. Восстановить дерево Т, если соответствующий ему вектор имеет вид: (1, 2, 2, 1, 4, 4, 4). (’’)
Решение. Данный вектор содержит 7 компонент, значит, дерево Т должно иметь 7+2=9 вершин. Выпишем последовательность номеров этих вершин:
1, 2, 3, 4, 5, 6, 7, 8, 9. (’)
1. В (’) находим первое число, которое не содержится в (’’), - 3. Получаем ребро (1,3).
Зачёркиваем 1 в (’’), 3 в (’); остаётся:
(2, 2, 1, 4, 4, 4), (’’) 1, 2, 4, 5, 6, 7, 8, 9. (’)
2. Первое число в (’), которое не содержится в (’’), - это 5. Получаем следующее ребро - (2,5). Зачёркиваем 2 в (’’), 5 в (’); остаётся:
(2, 1, 4, 4, 4), (’’) 1, 2, 4, 6, 7, 8, 9. (’)
Повторяя эту процедуру ещё 3 раза, получим рёбра (2,6), (1,2), (4,1), (4,7), (4,8). После этого в последовательности (’) останутся два числа - 4 и 9. Они определяют последнее ребро (4,9). Так как все рёбра известны, восстанавливаем дерево Т, схема которого приведена на рис. 3.19, б.
Итак, нам удалось установить взаимно однозначное соответствие между множеством всех деревьев с n вершинами и множеством всех векторов (со значениями компонент от 1 до n) длиной (n2). Из взаимно однозначного соответствия этих множеств следует их равномощность.
В векторе (a1, a2,..., an2) каждая компонента может принимать любое из n значений (от 1 до n), а всего таких компонент n. По следствию из теоремы о мощности прямого произведения можно составить nn2 различных векторов вида (a1,a2,..., an2), а значит, и различных деревьев с n вершинами будет столько же.