Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf

173
????
1
= {{????
1
, ????
2
, ????
3
, ????
4
, ????
5
, ????
6
}, {(????
1
, ????
2
), (????
1
, ????
3
), (????
1
, ????
4
), (????
1
, ????
5
), (????
2
, ????
3
), (????
3
, ????
4
)}}
????
2
= {{????
1
, ????
2
, ????
3
, ????
4
, ????
5
}, {(????
4
, ????
5
), (????
5
, ????
2
), (????
3
, ????
5
), (????
2
, ????
3
), (????
3
, ????
1
)}}
б) матрицы смежности:
1 2
0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
G
G
A
A
















=
=




















в) матрицы инцидентности:
1 2
1 1
0 0
0 0
0 0
0 1
1 0 1 1
0 0
0 0
1 0
0 1
0 0 1 1
0 0
0 0
1 0
1 1
0 1 0
0 0
0 1
1 0
0 1
0 0 1 0
0 1
0 1
0 0
1 0
0 0 1 0
G
G
B
B


+
−








−
+






=
=
+
−






+
−








−
+






г) списки ребер (дуг):
(
)
(
)
(
)
(
)
1 1
2 3
1 1
1 2
4 5
2 3
3 1
2 1
3 3
4 3
4 6
2 5
2 3
1 5
,
, , , ,
;
,
,
, ,
;
:
:
, ,
, ,
,
,
, , ,
r
v v v v v v
r
v v v v v
G
G
t
v v v v v v
t
v v v v v
=
=






=
=




д) структуры смежности:


(
)
(
)
(
)
(
)
( )
( )


( )
( )
(
)
( )
( )
1 1
2 3
4 5
6 2
1 2
3 4
5 1
1 2
2 3
3 4
4 5
5 6
2 3
4 5
1 3
3 1
2 4
1 5
1 3
5 1
2
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
G
v
v
v
v
v
v
G
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
S
L
L
L
L
L
L
S
L
L
L
L
L
L
v v v v
L
L
v v
L
v
L
v v v
L
v v
L
v v
L
v
L
v
L
v
L


=
=



=

=


=
=




=


=


=
=




=
=




=


Следует отметить, что во многих задачах на графах выбор представления явля-
ется решающим для эффективности алгоритмов.

174 3. Взвешенный граф:
4.
Метрические характеристики графа: а) степени вершин: для неориентированного графа:
( )
1 4
d v =
;
( )
2 2
d v
=
;
( )
3 3
d v
=
;
( )
4 2
d v
=
;
( )
5 1
d v =
;
( )
6 0
d v
=
для ориентированного графа:
( )
1 0
d
v
−
=
;
( )
2 1
d
v
−
=
;
( )
3 2
d
v
−
=
;
( )
4 1
d
v
−
=
;
( )
5 1
d
v
−
=
;
( )
1 1
d
v
+
=
;
( )
2 1
d
v
+
=
;
( )
3 1
d
v
+
=
;
( )
4 0
d
v
+
=
;
( )
5 2
d
v
+
=
б) матрица весов по ребрам:
0 1
2 10 1
0 10 0
2 10 0
3 10 0
3 0
W






=






в) массив весов по вершинам:
2)
(
)
25, 30, 29, 46 .
V
W =
г) расстояния в графе:
Пути из вершины в вершину :
;
;
;
;
2
v
4
v
(
)
1 2
1 4
, ,
P
v v v
=
( )
1 11
l P =
(
)
2 2
3 4
,
,
P
v v v
=
( )
2 13
l P =

175
;
;
;
– наикратчайший путь, так он имеет минимальную длину, т.е. расстояние
Аналогичным образом, определяя расстояния от вершины до остальных двух вер- шин, получим следующий набор расстояний:
;
;
Максимальное расстояние из этого набора дает эксцентриситет вершины
:
Таким же образом найдем все эксцентриситеты графа:
;
;
;
Минимальный из эксцентриситетов дает радиус графа и, соответственно, центр графа – вершину .
Максимальный из эксцентриситетов дает диаметр графа и, соответ- ственно, периферийные вершины – и .
Найдем передаточное число вершины :
Таким же образом получим все передаточные числа графа:
;
;
;
Минимальное передаточное число получилось у вершины , значит, эта вершина яв- ляется медианой графа;
(
)
3 2
1 3
4
, ,
,
P
v v v v
=
( )
3 6
l P =
(
)
4 2
3 1
4
,
, ,
P
v v v v
=
( )
4 22
l P =
3
P
(
)
2 4
,
6
r v v
=
2
v
(
)
2 1
,
1
r v v
=
(
)
2 3
,
3
r v v
=
(
)
2 4
,
6
r v v
=
2
v
( )
2 6.
e v
=
( )
1 5
e v
=
( )
2 6
e v
=
( )
3 3
e v
=
( )
4 6
e v
=
( )
3
Rad G =
3
v
( )
6
Diam G =
2
v
4
v
2
v
( )
(
)
(
)
(
)
2 1
2 1
3 2
3 4
2 4
,
,
,
25 1 29 3 46 6 382.
s v
w r v v
w r v v
w r v v
=

+

+

=
 +
 +
 =
( )
1 318
s v
=
( )
2 382
s v
=
( )
3 278
s v
=
( )
2 392
s v
=
3
v

176 д) для графов ????
′
и ????
′′
найдем число вершинной связности ????(????); число реберной связ- ности ????(????); минимальную степень вершины ????(????):
????
′
????
′′
( )
1
G

 =
,
( )
2
G

 =
,
( )
2
G

 =
:
;
( )
1
G

 =
,
( )
1
G

 =
,
( )
2
G

 =
: е) графы и содержат трехэлементный полный подграф К
3
, поэтому для пра- вильной раскраски необходимо, по крайней мере, три краски. На рисунке метки вершин графа означают номера красок:
Для графа этого достаточно.
Граф имеет цикл длины 5, для правильной раскраски которого необходимы три краски. Но центральная вершина смежна со всеми вершинами цикла, поэтому для правиль- ной раскраски понадобится четвертая краска.
Таким образом, хроматические числа графов:
????(????
1
) = 3 и ????(????
2
) = 4. ж) плотности графов:
????(????
1
) = 3 и ????(????
2
) = 3. з) числа независимости графов:
1 2 2
 
1 1 2
 
1
G
2
G
1
G
2
G

177
????(????
1
) = 3 и ????(????
2
) = 2. и) числа паросочетания графов:
????(????
1
) = 3 и ????(????
2
) = 3. к) числа реберного покрытия графов:
????(????
1
) = 4 и ????(????
2
) = 3.
Варианты индивидуальных заданий:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

178 13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.

179 28.
29.
30.

180
ЗАКЛЮЧЕНИЕ
Учебное пособие посвящено изучению основных разделов и понятий, приобретению практических навыков решения типовых задач дискретной математики.
При изучении раздела «Множества, отношения и функции» студенты получают зна- ния о таких понятиях, как множество и подмножество, операции над множествами, декар- тово произведение множеств, отношения и функции. Студенты знакомятся с различными способами представления множеств, отношений и функций, приобретают навыки исследо- вания свойств бинарных отношений и функций.
На материале раздела «Алгебра логики» студенты получают первоначальное пред- ставление о таких понятиях, как логическая функция, операция суперпозиции, функцио- нально полная система. Студенты знакомятся с различными способами заданий логических функций; изучают применение исследования полноты и замкнутости систем логических функций; изучают одно из приложений теории булевых функций – синтез логических схем.
В рамках раздела «Теория графов» студенты изучают задачи связности графа, свой- ства деревьев, теория матроидов, независимые множества вершин, хроматические числа, эйлеровы и гамильтоновы циклы Рассматриваемые понятия являются основой информа- тики и программирования. Данный курс позволит студентам освоить основные разделы тео- рии графов, применять различные алгоритмы для решения практических задач.
Таким образом, знания, полученные в результате изучения материала учебного посо- бия, приобретенные навыки решения задач дискретной математики позволят студентам успешно осваивать дисциплины профессионального цикла, выполнять курсовые и диплом- ные работы.
Авторы надеются, что книга будет полезной не только студентам, но и аспирантам и специалистам в области IT-технологий.

181
ЛИТЕРАТУРА
1. Иванов Б. Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002. – 288 с.
2. Новиков Ф.А. Дискретная математика для программистов: учебник для вузов. 3-е изд. – СПб.: Питер, 2009. – 384 с.
3. Хаггарти Р. Дискретная математика для программистов. 2-е изд. – М.: Техносфера,
2005. – 400 с.
4. Липский В. Комбинаторика для программистов; пер. с польск. – М.: Мир, 1988. –
200 с.
5. Чередникова А.В., Садовская О.Б., Каминская Л.А. Дискретная математика. Теория и практика. – Кострома: Изд-во Костром. гос. технол. ун-та, 2011. – 74 с.
6. Кузнецов А.П., Адельсон-Вельский А.М. Дискретная математика для инженера. –
М.: Энергоатомиздат, 1988. – 480 с.
7. Математический форум Math Help Planet [Электронный ресурс]. 2010–2016. – URL: http://mathhelpplanet.com/static.php?p=algebraicheskiye-struktury-i-operatsii (дата обращения:
11.02.2022).
8. Куликов Л.Я. Алгебра и теория чисел. – М.: Высш. школа, 1979. – 559 с.
9. Стенли Р. Перечислительная комбинаторика; пер. с англ. – М.: Мир, 1990. – 440 с.
10. Самофалов К.Г. [и др.]. Прикладная теория цифровых автоматов. – Киев: Вища школа, 1987. – 375 с.
11. Минимизация булевых функций методом Квайна // Пятифан [Электронный ре- сурс]. – URL: http://5fan.ru/wievjob.php?id=42423 (дата обращения: 10.02.2022).
12. Зубчук В.И. и др. Справочник по цифровой схемотехнике / В.И. Зубчук, В.П. Си- горский, А.Н. Шкуро. – Киев: Тэхника, 1990. – 448 с.
13. Библиотека учебных материалов [Электронный ресурс]. 2010–2016. – URL: http://xn-- e1axa0c.xn--p1ai/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%
D0%B0%D1%82%D0%B8%D0%BA%D0%B0/%D0%9B%D0%BE%D0%B3%D0%B
8%D0%BA%D0%B0/p5d77tln165875/
(дата обращения: 12.02.2022).
14. Карта Карно // Википедия. Свободная энциклопедия [Электронный ресурс]. –
URL: http://ru.wikipedia.org/w/index.php?oldid=36798414 (дата обращения: 02.03.2022).
15. Спирина М. С., Спирин П.А. Дискретная математика – М.: Издательский центр
«Академия», 2003. – 368 с.
16. Образовательный математический сайт [Электронный ресурс]. 1993–2016. – URL: http://vuz.exponenta.ru/PDF/L11.html (дата обращения: 12.07.2021).
17. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Наука, 1997.
18. Гуров С.И. Лекции по упорядоченным множествам и универсальной алгебре: учеб.-метод. пособие. – М.: Издательский отдел факультета ВМиК им. М.В. Ломоносова:
МАКС Пресс, 2009. – 192 с.
19. Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике. –
М.: Айрис-пресс, 2007. – 176 с.
20. Киселева Л.Г., Смирнова Т.Г. Функции алгебры логики в примерах и задачах: учеб.-метод. пособие. – Нижний Новгород: Изд-во Нижегород. гос.ун-та, 2008. – 57 с.
21. Гладких О. Б., Белых О. Н. Основные понятия теории графов: учеб. пособие. –
Елец: Изд-во ЕГУ им. И.А. Бунина, 2008. – 175 с.

182 22. Петрякова Е.А., Синеговская Т.С. Дискретная математика. Часть 2. Элементы тео- рии графов. – Иркутск: Изд-во ИрГУПС, 2009. – 108 с.
23. Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ-Петер- бург, 2008. – 352 с.
24. Базарон С.А., Данилова С.Д., Извеков Я.О. Комбинаторика и теория графов: курс лекций по дисциплине «Дискретная математика». – Улан-Удэ, 2014.
25. Данилова С.Д. Дискретная математика: курс лекций. – Улан-Удэ: Изд-во
ВСГУТУ, 2016. – 142 с.

183
СОДЕРЖАНИЕ
Введение ......................................................................................................................................... 3
Раздел 1. Множества, отношения, функции ................................................................................ 4
Тема 1.1 Введение в дискретную математику. Теория множеств ........................................ 4 1.1.1 Семантика дисциплины «Дискретная математика» .................................................. 4 1.1.2 Понятие множества и способы представления множеств ........................................ 4 1.1.3 Мощность множества, пустое множество, универсальное множество ................... 6 1.1.4 Подмножество, отношения включения и равенства множеств, булеан .................. 6 1.1.5 Операции над множествами и их основные свойства. Диаграммы Венна. ............ 7 1.1.6 Контрольные вопросы ................................................................................................ 13
Тема 1.2 Отношения. Композиция отношений ..................................................................... 14 1.2.1 Декартово произведение множеств........................................................................... 14 1.2.2 n-арные и бинарные отношения ................................................................................ 15 1.2.3 Области определения и значений бинарного отношения. Обратное отношение . 17 1.2.4 Свойства бинарных отношений ................................................................................ 18 1.2.5 Композиция отношений ............................................................................................. 20 1.2.6 Контрольные вопросы ................................................................................................ 21
Тема 1.3 Отношения эквивалентности и порядка ................................................................ 22 1.3.1 Отношение эквивалентности и разбиение множества ............................................ 22 1.3.2 Отношения порядка .................................................................................................... 24 1.3.3 Контрольные вопросы ................................................................................................ 28
Тема 1.4 Функции .................................................................................................................... 30 1.4.1 Определение функции ................................................................................................ 30 1.4.2 Отображение ............................................................................................................... 32 1.4.3 Сюрьективная функция .............................................................................................. 33 1.4.4 Инъективная функция ................................................................................................ 34 1.4.5 Биективная функция и биекция ................................................................................. 34 1.4.6 Контрольные вопросы ................................................................................................ 35
Раздел 2. Алгебра логики ............................................................................................................ 36
Тема 2.1 Функции алгебры логики ........................................................................................ 36 2.1.1 Логические функции и способы их представления ................................................. 36 2.1.2 Фиктивные и существенные переменные логической функции ............................ 37 2.1.3 Логические функции одной и двух переменных ..................................................... 39 2.1.4 Суперпозиции и формулы .......................................................................................... 40

184 2.1.5 Булева алгебра. Конъюнктивные и дизъюнктивные нормальные формы ............ 41 2.1.6 Контрольные вопросы ................................................................................................ 50
Тема 2.2 Классы функций алгебры логики. Функциональная полнота ............................. 52 2.2.1 Двойственные функции. Класс самодвойственных функций ................................ 52 2.2.2 Алгебра Жегалкина. Класс линейных функций ...................................................... 54 2.2.3 Монотонные функции. Класс монотонных функций .............................................. 57 2.2.4 Классы функций, сохраняющих 0 и сохраняющих 1 .............................................. 58 2.2.5 Классы Поста............................................................................................................... 58 2.2.6 Полнота и замкнутость системы логических функций ........................................... 59 2.2.7 Две теоремы о функциональной полноте ................................................................. 61 2.2.8 Контрольные вопросы ................................................................................................ 62
Тема 2.3 Минимизация функций алгебры логики ................................................................ 64 2.3.1 Сокращенная и минимальная ДНФ........................................................................... 64 2.3.2 Метод Квайна .............................................................................................................. 66 2.3.3 Метод минимизации по картам Карно ..................................................................... 69 2.3.4 Метод неопределенных коэффициентов .................................................................. 73 2.3.5 Контрольные вопросы ................................................................................................ 75
Тема 2.4 Синтез логических схем .......................................................................................... 77 2.4.1 Логическая схема и логические элементы ............................................................... 77 2.4.2 Построение логической схемы .................................................................................. 80 2.4.3 Минимизация логической схемы .............................................................................. 81 2.4.4 Контрольные вопросы ................................................................................................ 82
Раздел 3. Теория графов .............................................................................................................. 84
Тема 3.1 Основные понятия теории графов .......................................................................... 84 3.1.1 Начальные определения ............................................................................................. 84 3.1.2 Машинные представления графов ............................................................................ 88 3.1.3 Маршруты, пути, цепи, циклы .................................................................................. 90 3.1.4 Часть графа, суграф, подграф .................................................................................... 91 3.1.5 Связность графа .......................................................................................................... 92 3.1.6 Обходы графа .............................................................................................................. 94 3.1.7 Контрольные вопросы ................................................................................................ 97
Тема 3.2 Метрические характеристики графов .................................................................... 98 3.2.1 Степени вершин графа ............................................................................................... 98 3.2.2 Взвешенный граф...................................................................................................... 100 3.2.3 Расстояния в графе ................................................................................................... 102