Файл: Дискретная математика.pdf

Министерство образования и науки Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Е. Ф. Жигалова

ДИСКРЕТНАЯ МАТЕМАТИКА

Учебное пособие

Томск

«Эль Контент»

2014

УДК

519.1(075.8)

ББК

22.176я73
Ж 681

Рецензенты:

Фофанов О. Б., канд. техн. наук, доцент, зав. кафедрой оптимизации систем

управления Томского политехнического университета;

Абдалова О. И., зам. зав. кафедрой прикладной математики и информатики

ТУСУРа.

Жигалова Е. Ф.

Ж 681

Дискретная математика : учебное пособие / Е. Ф. Жигалова. — Томск :

Эль Контент, 2014. — 98 с.

ISBN 978-5-4332-0167-5

Учебное пособие содержит традиционные разделы дискретной мате-

матики: основы теории множеств, булевой алгебры, теории графов и ком-
бинаторики.

Наибольшее внимание в пособии уделено разделу о графах и их ха-

рактеристиках.

В пособии размещены примеры решения типовых задач по дискрет-

ной математике по всем разделам содержания. Все задачи снабжены по-
дробным описанием алгоритмов их решения. Пособие ориентировано на
студентов технических университетов, обучающихся с применением ди-
станционных образовательных технологий.

УДК

519.1(075.8)

ББК

22.176я73

ISBN 978-5-4332-0167-5

© Жигалова Е. Ф., 2014
© Оформление.

ООО «Эль Контент», 2014

ОГЛАВЛЕНИЕ

Введение

5

1

Основы теории множеств и отношений

8

1.1

Понятие множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.2

Операции над множествами . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3

Булевы выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2

Теория графов

14

2.1

Определение графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.2

Классы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.3

Способы задания графов . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.4

Числовые характеристики вершин графа . . . . . . . . . . . . . . . . . .

19

2.5

Маршруты, цепи и циклы . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.6

Определение числа маршрутов длины «L» на графе . . . . . . . . . . .

21

2.7

Части графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.7.1

Подграф . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.7.2

Частичный граф . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

2.8

Метрика графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

2.9

Структурный анализ графов . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.9.1

Раскраска графов. Правильная раскраска, хроматическое
число . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

2.9.2

Компоненты связности графа . . . . . . . . . . . . . . . . . . . .

41

3

Экстремальные задачи на графах

46

3.1

Максимальное паросочетание в двудольном графе . . . . . . . . . . .

46

3.2

Венгерский алгоритм нахождения максимального паросочетания
в двудольном графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

3.3

Оптимальные потоки в транспортных/информационных сетях . . . .

52

4

Переключательные функции

62

4.1

Переключательные функции. Способы задания . . . . . . . . . . . . .

62

4.2

Булевы функции (БФ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

4.3

Аналитическое представление булевых функций . . . . . . . . . . . . .

68

4.3.1

Булева алгебра функций и эквивалентные преобразования
в ней . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

4.3.2

Представление переключательных функций в виде
многочленов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

4

Оглавление

4.4

Функционально полные системы . . . . . . . . . . . . . . . . . . . . . .

75

4.5

Минимизация булевых функций . . . . . . . . . . . . . . . . . . . . . . .

76

4.5.1

Алгебраический метод упрощения булевых функций . . . . .

77

5

Комбинаторика

83

5.1

Основные формулы комбинаторики . . . . . . . . . . . . . . . . . . . . .

84

5.2

Комбинаторика и теоретико-вероятностные задачи . . . . . . . . . . .

86

Заключение

94

Литература

95

Глоссарий

96

ВВЕДЕНИЕ

Дискретная математика — часть математики, которая зародилась в глубокой древ-

ности. Главной её спецификой является дискретность (антипод непрерывности).
В широком смысле дискретная математика включает в себя такие сложившие-
ся разделы математики, как теория чисел, алгебра, математическая логика и ряд
разделов, которые наиболее интенсивно стали развиваться в середине ХХ-го века
в связи с внедрением ЭВМ, например «теория графов».

Дискретная математика сегодня является не только фундаментом математиче-

ской кибернетики, но и важным звеном математического образования.

Главная задача курса — это обучение методам и мышлению, характерным для

дискретной математики.

Научно-технический прогресс вызвал необходимость изучения и развития но-

вых разделов науки, таких как сложные управляющие системы.

Сложная система — это собирательное название систем, состоящих из большо-

го числа взаимосвязанных элементов. Типичными примерами сложной системы
являются: нервная система, мозг, ЭВМ, система управления в человеческом обществе
и т. д.

Другое определение сложной системы. Сложная система — это составной объ-

ект (система), части которого, в свою очередь, можно рассматривать как отдельные
системы, объединённые в единое целое в соответствии с определёнными принци-
пами или связанные между собой заданными отношениями.

Часто сложными называют системы, которые нельзя корректно описать мате-

матически потому, что в них имеется очень большое число различных элементов,
неизвестным образом связанных друг с другом (напр., мозг), либо потому, что
неизвестна природа процессов, протекающих в них. Сложными называются так-
же системы, изучение которых связано с обработкой непомерно больших объемов
информации (даже учитывая возможности современных ЭВМ).

Научно-технический прогресс вызвал необходимость изучения и развития но-

вых разделов науки. К новым разделам науки относят: теорию функциональных
систем; теорию графов и сетей; теорию кодирования; целочисленное программи-
рование; комбинаторный анализ.

Сегодня дискретная математика является фундаментом математической кибер-

нетики и важным звеном математического образования. Можно сказать, что дис-
кретная математика есть совокупность математических дисциплин, изучающих