МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное
образовательное учреждение высшего образования
«Северо-Кавказская государственная академия»
Институт Прикладной математики и информационных технологий
Кафедра «Математика»
_к.ф.-м.н., доцент_
(ученая степень, ученое звание)
_Шапошникова О.И.
(фамилия, имя, отчество)
Варианты заданий и методические указания
к выполнению контрольной работы по дисциплине
«Дискретная математика» для обучающихся __1___ курса
направления подготовки (специальности)
_09.03.03 Прикладная информатика
(заочная форма обучения)
Черкесск, 2024
1
ВАРИАНТЫ КОНТРОЛЬНЫХ РАБОТ
Выбор варианта по последней цифре номера зачетной книжке
Выбор варианта задания по последней цифре номера зачетной книжки обучающегося.
Задание 1.
Решить задачу.
В-1. На школьный вечер танцев собрались ребята 9-х, 10-х и 11-х классов. Вести хоровод
приглашаются 10 школьников. Сколькими способами можно составить хоровод при условии участия в нем хотя бы одного одиннадцатиклассника? (55)
В-2. На студенческий вечер собрались юноши и девушки 8 факультетов университета (в
том числе математического и филологического). Для исполнения народных танцев приглашаются 10 студентов. Сколькими способами можно выбрать эту десятку при условии
участия в ней хотя бы одного студента математического и хотя бы одного студента филологического факультета? (6435)
В-3. На Всемирный фестиваль молодежи прибыла молодежь пяти континентов мира. Возникла необходимость организовать делегацию из восьми представителей разных стран для
оглашения клятвы борцов за мир. Сколькими способами можно было образовать делегацию при условии участия в ней представителей всех континентов? (35)
В-4. В гастрономе имеются конфеты трех наименований. Конфеты упакованы в коробки
трех видов – для каждого наименования своя коробка. Сколькими способами можно заказать набор из пяти коробок? (21)
В-5. Сколько автомашин модно обеспечить 6-значными номерами? (106)
В-6. Сколько 5-значных чисел можно образовать из цифр 0 и 1? (16)
В-7. В одном государстве (сказочном) не найдется двух человек, у которых оказался бы
одинаковый состав зубов: либо у них разное число зубов, либо зубов нет в разных местах.
Оцените наибольшую численность населения в этом государстве, если максимальное число зубов у одного человека 32. (Не больше 232)
В-8. Сколькими способами можно отослать 6 писем разным адресатам, если их будут разносить 3 курьера и заранее известно, какому курьеру какое достанется письмо? (729)
В-9. Четыре студента сдают экзамен. Сколько может быть вариантов распределения оценок, если известно, что так или иначе все они экзамены сдали? (81)
В-0. Три парня и три девушки решили после окончания школы поступить на работу в своем родном городе. В городе имеются 3 завода, на которые берут только мужчин, 2 – где
нужны женщины и 2 – которые принимают на работу и мужчин и женщин. Сколькими
способами пять выпускников могут распределиться по заводам города? (2000)
Задание 2.
В произвольном связном графе G (V , E ), V 10, E 20 у которого ребра e (u, v)
deg u deg v
, найти:
НОД (deg u , deg v)
а) минимальное остовное дерево с помощью алгоритма Краскала;
б) минимальное остовное дерево с помощью алгоритма Прима;
в) составить матрицу смежности и матрицу инцидентности;
г) вычислить радиус и диаметр графа, указать центральные и периферийные вершины;
д) построить дополнение для данного графа;
е) найти все инварианты графа (вектор степеней графа, число внешней устойчивости, число внутренней устойчивости, хроматическое число, число компонент связности, число
Хадвигера);
взвешены числами w(e)
2
Задание 3.
Составить таблицы истинности формул.
В1. x y y x ,
В2. x y y x ,
В3. x y y x ,
В4. x y y x ,
x y z xy .
x y z xy .
x y z xy .
x y z xy .
x y z xy .
x y z xy .
В6. x y y x ,
x y z xy .
В7. x y y x ,
В5. x y y x ,
В8. x y y x ,
x y z xy .
x y z xy .
x y z xy .
В9. x y y x ,
В0. x y y x ,
Задание 4.
Проверить, будут ли эквивалентны следующие формулы с помощью эквивалентных преобразований.
В1. x y z и x y x z .
В2. x y z и x y x z .
В3. x y z и x y x z .
В4. x y z и x y x z .
В5. x y z и x y x z .
В6. x y z и x y x z .
В7. x y z и x y x z .
В8. x y z и x y x z
В9. x y z и x y x z .
В10. x y z и x y x z .
3
Задание 5.
С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ,
СКНФ. Проверьте правильность полученного результата, используя табличный способ
построения этих форм.
В2. x y z x .
В3. x y z x .
В4. x y z x .
В5. x y z x .
В6. x y z x .
В1. x y z x .
В7. z x y x .
В8. x y z x .
В9. z x x y .
В0. z x x y .
Задание 6. Построить детерминированный конечный автомат, распознающий язык L
В-1. L1 – множество слов, имеющих подслово ddcba в алфавите A a, b, c, d
В-2. L2 – множество слов, начинающихся буквой a и заканчивающихся буквой с в алфавите A a, b, c, d
В-3. L3 – множество слов, в которых буква d встречается ровно 3 раза в алфавите
A a, b, c, d
В-4. L4 – множество слов, содержащих четное количество букв b в алфавите A a, b, c, d
В-5. L5 – множество слов, в которых буква a встречается 2 раза, а буква c – 1 раз в алфавите A a, b, c, d
В-6. L6 – множество слов, в которых каждая цифра кратна 3 в алфавите B 0,1,2,...,9
В-7. L7 – множество слов, в которых расстояние между буквой c и ближайшей буквой d
не больше 3 в алфавите A a, b, c, d
В-8. L8 – множество слов, у которых вторая и предпоследняя буква – d в алфавите
A a, b, c, d
В-9. L9 – множество слов, у которых вторая и предпоследняя буква – d в алфавите
A a, b, c, d
В-10. L10 – множество симметричных слов длины 6 в алфавите A a, b, c, d
4
Задание 7. Построить конечные автоматы, распознающие объединение, пересечение, разность языков, заданных автоматами K 1 и K 2
Номер
варианта
K1
a
q10
В-1.
a
a
q11
b
K2
a
q12
b
q02
q12
a
b
b
В-2.
b
a
a, b
b
q10
q11
q02
q12
b
a, b
a
q10
a, b
q12
a
a
В-3.
b
a
q11
q02
a
q12
b
q22
a, b
b
b
a
q10
В-4.
q12
a
a
q11
q12
a
b
b
b
b
a, b
b
q02
q22
a
q11
b
a
В-5.
b
q02
a, b
b
q10
a, b
q12
a
q12
a
a
q10
В-6.
b
q11
b
a
a
a
q12
q02
b
a
q12
a, b
q22
b
b
5
a, b
q10
q12
q11
a
a
В-7.
b
b
a, b
b
q02
q22
a
1
0
q10
В-8.
0
q11
1
q12
q12
0
0
1
1
0
1
1
q02
q22
0
0
В-9.
0, 1
0
q11
q10
0
q12
q12
q02
0, 1
1
1
q11
a
В-0.
1
a
b
q02
q10
q31
b
b
a, b
q12
b
a
a
b
q12
a
6
Методические указания по выполнению контрольной работы
по дисциплине «Дискретная математика»
Глава 1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
В комбинаторном анализе рассматриваются задачи о расположениях
элементов в соответствии с точно определенными требованиями, и выясняется, сколькими различными вариантами такие расположения могут быть осуществлены. При этом необходимо однозначно определить, какие решения
считаются различными.
Одними из основных средств, для подсчета числа решений комбинаторных задач являются выборки, к которым относятся размещения, сочетания и перестановки.
Рассмотрим множество A ai , i 1,...,n .
Определение 1. Набор элементов ai , ai ,..., ai из A называется выборкой
объема k из n элементов или (n, k) – выборкой.
Выборки могут отличаться друг от друга, как составом, так и порядком
расположения элементов. Если допустить, что среди элементов выборки есть
одинаковые, то объем выборки в отдельных случаях может превышать объем
исходного множества.
Выборка называется упорядоченной, если порядок элементов в ней задан. То есть, упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.
Если порядок следования элементов не является существенным, то выборка называется неупорядоченной.
В выборке могут допускаться или не допускаться повторения элементов. Таким образом, можно говорить о (n, k) – выборках без повторений и о
(n, k) – выборках с повторениями.
Положим n=3, k=2 и рассмотрим множество A 1,2,3, представим для
него все случаи (3,2)-выборок.
(1) неупорядоченные без повторения (1,2) ; (1,3); (2,3);
(2) неупорядоченные с повторениями (1,1); (1,2); (2,2); (1,3); (3,3); (2,3);
(3) упорядоченные без повторений (1,2); (2,1); (1,3); (3,1); (2,3); (3,2);
(4) упорядоченные с повторениями (1,2); (2,1); (1,3); (3,1); (2,3); (3,2); (1,1);
(2,2); (3,3);
Определение 2. Упорядоченная (n, k) – выборка без повторений называется размещением из n элементов по k или кратко (n, k) – размещением.
Определение 3. Упорядоченная (n, k) – выборка с повторениями называется размещением с повторениями из n элементов по k или кратко (n, k) –
размещением с повторениями.
Определение 4. Неупорядоченная (n, k) – выборка без повторений называется сочетанием из n элементов по k или кратко (n, k) – сочетанием.
1
2
k
7
Определение 5. Неупорядоченная (n, k) – выборка с повторениями
называется сочетанием с повторениями из n элементов по k или кратко (n, k)
– сочетанием с повторениями.
Определение 6. Если n=k, то (n, n) – размещение называется перестановкой n элементов.
Число всех (n, k) – размещений обозначается символом Pnk или P(n, k ) и
вычисляется по формуле
Pnk
n!
n(n 1)...( n k 1) .
(n k )!
Действительно, размещение k элементов можно представить как заполнение некоторых k позиций элементами множества A . При этом первую позицию можно заполнить n различными способами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать (n-1)
способами. Если продолжить этот процесс, то после заполнения позиций с 1й по (k -1)-ю будем иметь (n-k+1) способов заполнения последней, k-й позиции.
Перемножая
эти
числа,
получим
формулу
Pnk
n!
n(n 1)...( n k 1) .
(n k )!
Число всех (n, k) – размещений с повторениями обозначается символом
P̂nk или Pˆ (n, k ) и вычисляется по формуле Pˆnk n k .
Действительно, размещение k элементов можно представить как заполнение некоторых k позиций элементами множества A . При этом первую позицию можно заполнить n различными способами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать тоже n
способами. Если продолжить этот процесс, то для заполнения последней, k-й
позиции будем иметь тоже n способов. Перемножая эти числа, получим формулу Pˆnk n k .
Число всех перестановок n элементов обозначается символом Pn или
P(n, n) и вычисляется по формуле Pn n! .
Действительно, Pn Pnn
n!
n(n 1)( n 2)... 3 2 1 n! .
(n n)!
Число всех (n, k) – сочетаний обозначается символом Cnk или C (n, k ) и
вычисляется по формуле
Cnk
n!
.
(n k )! k!
В каждом из Cnk сочетаний имеется k различных элементов, поэтому на
базе каждого сочетания можно получить Pk перестановок. Совокупность всех
выборок, полученных путем построения всех перестановок на базе каждого
из Cnk сочетаний, представляет собой число размещений Pnk , т.е. Cnk Pk Pnk
откуда Cnk
n!
.
(n k )! k!
Число всех (n, k) – сочетаний с повторениями обозначается символом
Ĉnk или Cˆ (n, k ) и вычисляется по формуле
(n k 1)!
Cˆ nk Cnnk11
.
k!(n 1)!
8
Задачи на применение формул подсчета числа различных выборок.
1. Сколько различных четырехзначных чисел можно образовать из
цифр 1, 2, …, 9, если все цифры в каждом четырехзначном числе различны?
Pnk
n!
9!
9!
6 7 8 9 3024 .
, n=9, k=4. P94
( n k )!
(9 4)! 5!
2. На тренировках занимаются 12 баскетболистов. Сколько может быть
образовано тренером разных стартовых пятерок?
12!
12!
n!
5
792 .
C nk
, n=12, k=5. C12
(12 5)!5! 7!5!
(n k )! k!
3. Сколько различных наборов по 8 пирожных в каждом можно составить используя 4 сорта пирожных?
(n k 1)!
(4 8 1)! 11!
Cˆ nk Cnnk11
165 .
, n=4, k=8. Cˆ 48 C44811
k!(n 1)!
8!(4 1)! 3!8!
4. Буквы азбуки Морзе образуются как последовательность точек и тире. Сколько различных букв можно образовать если использовать 5 символов?
Pˆnk n k , n=2, k=5. Pˆ25 25 32 /
5. Семь девушек водят хоровод. Сколькими различными способами
они могут встать в круг?
Pn n! n=7. P7 7! 5040
При подсчете числа различных комбинаций используются следующие
два правила:
1.
Правило произведения. Если объект A1 может быть выбран n1 способами и после каждого из таких выборов объект A2 в свою очередь может
быть выбран n2 способами, то выбор « A1 и A2 » в указанном порядке может
быть осуществлен n1 ∙ n2 способами.
2.
Правило суммы. Если объект A1 может быть выбран n1 способами,
а объект A2 может быть выбран другими n2 способами, то выбор « A1 или A2 »
может быть осуществлен n1 + n2 способами.
Задачи на правило произведения и правило суммы.
1) Правило произведения.
Для полета на Марс необходимо укомплектовать следующий экипаж
космического корабля: командир, первый его помощник, второй помощник,
два бортинженера и один врач. Командующая тройка может быть отобрана
из числа 25 готовящихся к полету летчиков, два бортинженера – из числа 20
специалистов, врач – из числа 8 медиков. Сколькими способами можно
укомплектовать экипаж?
9
Решение: командующая тройка - P253 т.к. важен порядок, у бортинженеров обязанности одинаковые - С202 , врач - С81 . Весь экипаж - P253 и С202 и С81 , что
соответствует P253 С202 С81 20976000 способами.
2) Правило суммы.
Сколько существует различных телефонных номеров, если считать, что
каждый номер содержит не более семи цифр (телефонный номер может
начинаться с 0)?
Решение: P101 P102 P103 ... P107 10 10 2 10 3 ... 10 7
10(1 10 7 ) 10(10 7 1)
.
1 10
9
Воспользовались формулой суммы геометрической прогрессии при q>1:
b1 (1 q n )
Sn
.
1 q
Перестановки с повторениями.
Пусть имеются предметы k различных видов. Сколько существует перестановок из n1 элементов первого типа, n2 элементов второго типа,…, из
nk элементов k-того типа.
Пусть дано множество M: M={a,a,a,b,b,c,d,d,d,d}, n=10, a повторяется 3 раза, b повторяется 2 раза, c повторяется 1 раз и d повторяется 4 раза.
Рассмотрим перестановки элементов этого множества, если все элементы различны: a1 , a2 , a3 , a4 , b1 , b2 , c1 , d1 , d 2 , d3 , d 4 . Тогда мы получим 10! перестановок. Но из этих 10! перестановок такие перестановки как
a2 , a1 , a3 , a4 , b1 , b2 , c1 , d1 , d 2 , d3 , d 4 ;
a2 , a1 , a3 , a4 , b2 , b1 , c1 , d1 , d 2 , d3 , d 4 ;
a2 , a1 , a3 , a4 , b2 , b1 , c1 , d 2 , d1 , d3 , d 4 ;
…
при отбрасывании индексов будут одинаковыми. Одинаковыми будут 3! перестановок из a, 2! перестановок из b, 1! перестановок из c, 4! перестановок
из d. Общее количество одинаковых перестановок: 3!2!1!4!
Исключим их из общего количества перестановок:
10!
P(10;3,2,1,4) .
3!2!1!4!
В общем случае число перестановок любого мультимножества (множества с повторениями элементов) или перестановок с повторениями равно полиномиальному коэффициенту:
P (n; n1 , n2 ,...nk )
n!
n1!n2!... nk !
Перестановки с повторениями имеют тесную связь с сочетаниями.
Определим их количество: из всех n элементов перестановки n1 место зани10
мают элементы первого типа. Выбор мест для них можно сделать из Cnn способами. Из оставшихся n n1 мест элементы второго типа занимают n2 место, которое можно выбрать Cnn n способами…
Согласно правилу прямого произведения число перестановок с повторениями равно:
1
2
1
P(n; n1 , n2 ,...nk ) Cnn1 Cnn2 n1 Cnn3 n1 n2 ... Cnnk n1 ... nk 1
n!
n1!n2!... nk !
Задача №1:
Решить пример с использованием формулы через сочетания.
10!
7!
5!
4!
P(10;3,2,1,4) C103 C72 C51 C44
3!(10 3)! 2!(7 2)! 1!(5 1)! 4!(4 4)!
120 21 5 1 12600
Задача №2:
Сколько существует различных перестановок из букв слова «уссури»?
6!
P(6;2 у ,2с ,1р ,1и )
180
2!2!1!1!
Глава 2. ТЕОРИЯ ГРАФОВ
Рассмотрим конечное множество V , V n и множество V 2 V V всех
его 2-х элементных множеств. Для произвольных подмножеств E V 2 называем термином граф всякую пару G (V , E) .
Элементы множества V , V n называются вершинами, элементы множества E ребрами.
Вершины и ребра графа называются его элементами. Число V n
вершин графа G называется его порядком и обозначается через G . Если G n, E m , то G называют (n, m)-графом.
Говорят, что две вершины u и v графа смежны, если множество {и, v}
является ребром, и не смежны в противном случае. Если e = {и, v} —
ребро, то вершины u и v называют его концами. В этой ситуации говорят также, что ребро e соединяет вершины u и v. Такое ребро обозначается
символом uv.
Два ребра называются смежными, если они имеют общий конец.
Вершина u и ребро e называются инцидентными, если v является
концом ребра e (т. е. e = иv), и не инцидентными в противном случае.
Заметим, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.
11
Рис. 1.2
Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а соединяющие пары точек линии — ребрам. В качестве
иллюстрации рассмотрим граф G, изображенный на рис. 1.1. Это (5, 6)граф, VG = {1, 2, 3, 4, 5}, EG = {{1, 2}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {4,
5}}.
Вершины 1 и 2 смежны, а 1 и 3 не смежны. Вершина 1 и ребро {1, 2}
инцидентны.
Приведем примеры некоторых графов специального вида.
Граф G называется полным, если любые две его вершины смежны, т.
е. EG=(VG)(2). Полный граф порядка n обозначается символом Kn, число
n
2
ребер в нем равно
n(n 1)
. На рис. 1.2 изображены графы Kn, n <= 5.
2
Граф называется пустым, если в нем нет ребер. Пустой граф порядка
n обозначается через On.
Матрицы, ассоциированные с графом
Далее элемент матрицы M, занимающий позицию (i, j), обозначается символом Mij. Матрица, каждый элемент которой равен 0 или 1, называется бинарной.
Пусть G — помеченный граф порядка n, VG ={1, 2, ..., n}. Определим бинарную n*n-матрицу A=A(G), положив
1, если вершины i и j смежны,
A ij
0 в противном случае.
A(G) называется матрицей смежности графа G. Это симметрическая
матрица с нулями на диагонали. Число единиц в строке равно степени соответствующей вершины.
Аналогично определяются матрицы смежности А мульти- и псевдографов: Aij равно числу ребер, соединяющих вершины i и j (при этом петля
означает два ребра).
Так же определяется матрица смежности A(G) ориентированного
графа G:
1, если вершины (i, j) AG,
( A(G)) ij
0 в противном случае.
Здесь AG — множество дуг орграфа G.
12
Очевидно, что любая квадратная бинарная матрица является матрицей
смежности некоторого ориентированного графа. На рис. 6.1 изображен
ориентированный граф с матрицей смежности.
Абстрактный граф приводит к различным матрицам смежности в зависимости от нумерации вершин.
Определим матрицу инцидентности графа. Пусть G-(n, m)-граф,
VG = {1, 2, ..., n}, EG = {e 1 , e2, ..., em}. Определим бинарную nmматрицу I = I(G) условиями:
1, если вершина k и ребро el инцидентны ,
I kl
0 в противном случае.
Матрица I называется матрицей инцидентности графа G. В каждом
ее столбце ровно две единицы, равных столбцов нет. Как и выше, соответствие GI(G) является биекцией множества помеченных (n, m)-графов
с занумерованными ребрами на множество nm-матриц, удовлетворяющих
описанным условиям.
Для ориентированных графов определение матрицы инцидентности I
видоизменяется:
1, если вершина k начало дуги al ,
Bij - 1, если вершина k конец дуги al ,
0, если вершина k и дуга a не инцидентны ,.
l
Метрические характеристики графа
Пусть G — связный граф, а u и v — две его несовпадающие вершины.
Длина кратчайшего (u, v) -маршрута (он, естественно, является простой цепью) называется расстоянием между вершинами u и v и обозначается через d(u,
v). Положим еще d(u, u)=0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:
1) d(u, v)>= 0,
2) d(u, v) = 0 тогда и только тогда, когда u = v,
3) d(u, v)= d(v, и),
4) d(u, v)+d(v, w) >= d(u, w) (неравенство треугольника).
Для фиксированной вершины u величина
13
называется эксцентриситетом вершины u. Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d(G).
Тем самым
Вершина v называется периферийной, если e(v)=d(G). Простая цепь
длины d(G), расстояние между концами которой равно d(G), называется диаметральной цепью.
Для иллюстрации обратимся к графу на рис. 8.1. Здесь d(1, 2)=1, d(1,
3)=2; e(1)=2; d(G)=2. Все вершины, кроме вершины 2, являются периферийными, (1, 2, 3) — диаметральная цепь.
Минимальный из эксцентриситетов вершин связного графа называется его
радиусом и обозначается через r(G):
Очевидно, что радиус графа не больше его диаметра.
Вершина v называется центральной, если e(v)= r(G). Множество всех
центральных вершин графа называется его центром. Граф может иметь
единственную центральную вершину или несколько центральных вершин. Наконец, центр графа может совпадать с множеством всех вершин.
Задача нахождения центральных вершин графа постоянно возникает
в практической деятельности людей. Пусть, например, граф представляет
сеть дорог, т. е. вершины его соответствуют отдельным населенным
пунктам, а ребра — дорогам между ними. Требуется оптимально разместить больницы, магазины, пункты обслуживания. В подобных ситуациях
критерий оптимальности часто заключается в оптимизации «наихудшего»
случая, т. е. в минимизации расстояния от места обслуживания до наиболее
удаленного пункта. Следовательно, местами размещения должны быть
центральные вершины графа.
Инварианты графа
Условимся использовать обозначения
- изоморфизм графов G и G’;
М – множество, элементами которого могут быть числа, векторы, многочлены, матрицы, системы чисел;
14
F – функция, которая каждому графу G ставит в соответствие некоторый элемент f(G) из множества М.
Функцию f называют инвариантом, если на изоморфных графах ее значения совпадают, т.е. для любых графов G и G’ выполняется соотношение
↔
f(G) = f(G’).
Кликой называют всякий наибольший полный подграф данного графа,
размер клики – число вершин в ней.
Определим наиболее важные инварианты графа.
10. Вектор степеней графа G (V , E) - это упорядоченный (по возрастанию или убыванию) перечень S (G) (S1, S2 ,..., Sn ) степеней Si deg vi вершин
v1 , v2 ,..., vn V , n V .
20. Число внешней устойчивости или плотности G - это число вершин
максимальной клики в графе G. Другими словами, G - это наибольшее количество попарно смежных вершин в G.
Иногда плотность G называют кликовым числом.
Наименьшее число клик графа G, покрывающих множество V, называется числом кликового покрытия и обозначается через с(G).
30. Число внутренней устойчивости или неплотность (G) графа
G (V , E) - это наибольшее количество его попарно несмежных вершин. Приведем другое определение. Подмножество V ' V называется независимым
(или внутренне устойчивым), если в нем любая пара вершин v ' , v '' V ' не
смежна. Т.е. если V ' независимо в G , то порожденный подграф G(V ' ) состоит
только из изолированных вершин.
Независимое множество называется максимальным, если оно не является собственным подмножеством другого независимого множества.
Наибольшее по мощности независимое множество в графе G называется
наибольшим, а его мощность равна (G) .
Примечание. Для всякого полного графа G (V , E) значение (G) =1, а
число внешней устойчивости G = V .
Задачи определения точного значения (G) очень трудны.
40. Хроматическое число.
Рассмотрим правильные k-раскраски графа G. Минимальное число k,
при котором граф G является k-раскрашиваемым, называется хроматическим
числом этого графа и обозначается (G) . Правильная k-раскраска графа G
при k (G) называется минимальной.
Если для графа G (G) 2 , то G называется бихроматическим.
50. Число компонент связности K(G).
60. Числом Хадвигера (G) связного графа G называется количество
вершин наибольшей клики, на которую можно стянуть данный граф.
Деревья
15
Деревом называется связный граф, не содержащий циклов. Любой граф
без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. На рис. 13.1 изображены все деревья шестого порядка.
Существует несколько вариантов определения дерева; некоторые из них
отражены в следующей теореме.
Теорема. Для (n, m)-графа G следующие утверждения эквивалентны .
1) G — дерево;
2) G — связный граф и m = n — 1;
3) G — ациклический граф и m = n — 1;
4) любые две несовпадающие вершины графа G соединяет единственная
простая цепь;
5) G — ациклический граф, обладающий тем свойством, что если какуюлибо пару его несмежных вершин соединить ребром, то полученный граф будет
содержать ровно один цикл.
З а д а ч а о б о с т о в е м и н и м а л ь н о г о в е с а (о кратчайшем
остове): связном взвешенном графе (G, w) порядка n найти остов минимального веса.
Алгоритм Краскала, решающий эту задачу, заключается в следующем.
1. Строим граф T1 = Оn + е1, присоединяя к пустому графу на множестве вершин VG ребро е1 принадлежит EG минимального веса.
2. Если граф Ti уже построен и i<n— 1, то строим граф Ti+1 — Ti +
ei+1 , где ei+`1 — ребро графа G, имеющее минимальный вес среди ребер, не
входящих в Ti и не составляющих циклов с ребрами из Тi.
Алгоритм Прима отличается от алгоритма Краскала только тем, что на
каждом этапе строится не просто ациклический граф, но дерево. Именно:
1.
Выбираем ребро е1 = аb минимального веса и строим дерево T1
полагая VT1 = {а, 6}, ЕТ1 = {е1}.
2. Если дерево Ti порядка i +1 уже построено и i<n— 1, то среди
ребер, соединяющих вершины этого дерева с вершинами графа G, не входящими в Ti, выбираем ребро ei+1 минимального веса. Строим дерево Ti+1, присоединяя к Ti ребро ei+1 вместе с его не входящим в Тi концом.
Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым гра-
16
фом. Такой граф можно нарисовать, не отрывая карандаша от бумаги и не
повторяя линий.
Помимо задачи о кёнигсбергских мостах известен ряд других старинных
занимательных задач (головоломок), решение которых сводится к выяснению вопроса «является ли граф эйлеровым?». В одной из них требуется обрисовать фигуру, именуемую саблями (знаком) Магомета, не отрывая карандаша от бумаги и не повторяя линий.
Теорема. (Л. Эйлер, 1736 г.). Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.
Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.
Гамильтонов путь (или гамильтонова цепь) — путь (цепь), содержащий
каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.
Гамильтонов цикл является простым остовным циклом. Задача определения
содержит ли данный граф гамильтонов цикл является NP-полной.
Глава 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА.
Логические операции над двумя высказываниями
Очевидно различных логических операций над двумя высказываниями
имеется столько, сколько существует различных третьих столбцов в соответствующих таблицах истинности, а именно 24=16. Условимся обозначать
эти операции символом fk и представим их следующей “сводной” таблицей
истинности:
x
0
0
1
1
y
0
1
0
1
f0
0
0
0
0
f1
0
0
0
1
f2
0
0
1
0
f3
0
0
1
1
f4
0
1
0
0
f5
0
1
0
1
f6
0
1
1
0
f7
0
1
1
1
f8
1
0
0
0
f9
1
0
0
1
f10
1
0
1
0
f11
1
0
1
1
f12
1
1
0
0
f13
1
1
0
1
f14
1
1
1
0
f15
1
1
1
1
Совокупность из 16 операций fk можно разбить на 3 группы:
I. f0 0, f15 1.
II. f3 = x , f5 = y ,
f10 = y ,
f12 = x .
III. f1 = x y ,
f7 = x y ,
f14 = x y x y ,
f8 = x y x y ,
f13 = x y ,
f2 = x y ,
f11 = y x ,
f4 = y x ,
f9 = x y ,
f6= x y x y .
Формулы в АВ строятся по следующим правилам:
10. Переменная есть формула.
17
20.Если F и Ф - формулы, то и F , (FФ), (FФ), (FФ), (FФ) - тоже
формулы.
30. Любая формула имеет вид, 10 или 20.
Например, выражение (( À B) (C D)) является формулой.
Эквивалентные формулы.
1. Для конъюнкции и дизъюнкции:
(1)
xx x ,
xx x
xx 0 (закон противоречия), x x 1 (закон исключенного третьего) (2)
(3)
x0 0 ,
x0 x
x1 x ,
x 1 1
(4)
2. Для отрицания, конъюнкции и дизъюнкции:
(5)
xx
(6)
x1x 2 x1 x 2
(7)
x1 x 2 x1x 2
Здесь (6) и (7) иногда называют законами де Моргана.
3. Законы дистрибутивности
( x1 x2) x3 ( x1x3) ( x2 x3)
(8)
( x1 x 2) x 3 ( x1 x 3)( x 2 x 3)
(9)
Обозначив через x1 x2 любую из функций x1 x2 , x1 x2 . Тогда функция
x1 x2 обладает свойством ассоциативности
(x1 x2 ) x3 = x1 ( x2 x3 ).
4. Эквивалентные формулы
(10)
x y x y
(11)
(12)
(13)
x y x y x y
x y ( x y )(x y)
Совершенные формы.
f x ,..., x x ...x
1
n
,,...,
1
1
1
n
n
(1)
n
Разложение вида (1) называется совершенной дизъюнктивной нормальной формой (с.д.н.ф.) и позволяет использовать следующий алгоритм построения с.д.н.ф. для всякой булевой функции f= f(x1, ..., xn), если f0.
Этап 1. В таблице, задающей f(x1, ..., xn), отмечаем все строки (1, ..., n), в которых f ,..., =1.
Этап 2. Для каждой отмеченной строки образуем конъюнкцию
(2)
x1 1 x2 2...xn n
1
n
Этап 3. Все полученные конъюнкции (1) соединим знаком дизъюнкции .
18
Преобразовать булеву формулу к с.д.н.ф. можно с помощью эквивалентных формул. Для этого избавляемся от импликации и эквиваленции и
приводим формулу к д.н.ф. Далее дополняем недостающие переменные с помощью закона исключенного третьего.
f x ,..., x
1
n
x x ... x
1
1
,...,
1
2
2
(3)
n
n
n
f 1,..., n 0
*
Каждую булеву функцию f(x1,..., xn)1 можно представить в виде (3),
где выражение (3) называется совершенной конъюнктивной нормальной
формой (с.к.н.ф.)
Если булева функция задана таблицей истинности, то для построения
с.к.н.ф. надо выбрать строки (1, ..., n), в которых f ,..., =0.
Для
каждой
отмеченной
строки
образуем
дизъюнкцию
1
2 ... n . Все полученные дизъюнкции соединим знаком конъюнк1
x x
1
x
2
n
n
ции.
Формулу F можно привести к с.к.н.ф. с помощью эквивалентных преобразований в два этапа.
Этап 1. Приведение F к виду к.н.ф. (F) с помощью законов (9.1)-(9.13).
Этап 2. Приведение к.н.ф. (F) к с.к.н.ф. [F]
Преобразование к.н.ф. (F) в с.к.н.ф. [F] осуществляется на базе закона
дистрибутивности следующим образом:
Пусть к.н.ф. F содержит элементарную дизъюнкцию D xi ... xi и
пусть D не включает в себя переменную xi x1 ,..., xn . Тогда осуществляем
1
k
0
следующее тождественное преобразование: D D 0 D xi xi D xi D xi .
0
0
0
0
Упражнение 1. Привести к с.к.н.ф. формулу
F=F(x1, x2, x3, x4) =(x1x3 x2x3)( x1 x2 x4)
Этап 1. Приведем к к.н.ф.
x x x
x x x x x x x x x x x x
x1 x3 x2 x3 x1 x2 x4 x1 x3 x2 x3
1
3
2
1
2
4
1
3
2
1
1
2
2
4
4
(2)
Этап 2. Преобразование к.н.ф. в с.к.н.ф. с помощью законов дистрибутивности.
А= (x1 x3 x2 x4x4) = (x1 x3 x2 x4) (x1 x3 x2 x4)
В= x1 x2 x4 x3x3=(x1 x2 x4 x3) (x1 x2 x4 x3)
А и В содержат одинаковый сомножитель (подчеркнуты). Поэтому
осуществляет операцию приведения подобных членов: в А или В заменяем
его на 1 или, что то же самое, вычеркиваем его из А или из В.
Окончательно имеем с.к.н.ф.
F = АВ= (x1 x3 x2 x4) (x1 x3 x2 x4) (x1 x2 x4 x3).
19
Глава 4. РАСПОЗНАЮЩИЕ КОНЕЧНЫЕ АВТОМАТЫ
Распознающими конечными автоматами являются конечные автоматы,
результатом работы которых является обнаружение некоторого свойства в
заданном тексте. Обработку произвольного слова во входном алфавите A
автомат начинает из специально выделенного начального состояния. В каждый такт дискретного времени на вход автомата поступает очередная буква
обрабатываемого слова, под ее воздействием автомат меняет свое состояние;
состояние в которое автомат перейдет, определяется предыдущим его состоянием и прочитанной буквой входного слова. Над словом длины l автомат
работает l тактов. Результат работы автомата определяется состоянием, в котором он оказывается по ее завершении.
Формально конечный автомат K определяется как совокупность
K Q , A,q0 , g , F ,
где Q q0 ,q1 ,q2 ,...,qm – множество состояний автомата; A a1 ,a2 ,...,an –
входной алфавит; q0 – специально выделенное состояние автомата, именуемое начальным состоянием; g – функция переходов конечного автомата,
представляющая собой отображение типа Q A Q (если g qi ,a j qk , то автомат из состояния qi под воздействием буквы a j должен перейти в состояние qk ); F – специально выделенное подмножество состояний автомата, которые условно называются «хорошими», F Q . (соответственно «плохими»
называются состояния из множества Q \ F ).
Пусть al ,al ,...,al – входное слово, l p . Через q t обозначим
1
2
p
состояние, в котором оказывается автомат K через t тактов работы над этим
словом (здесь t 0,1,2,..., p ): q 0 q0 , q 1 g q 0,al , q 2 g q 1,al , …,
q p g q p 1, al .
p
1
2
Слово принимается автоматов K , если q p F . Введем в рассмотрение язык LK : слово принадлежит языку LK , если данное слово принимается автоматом K . Язык LK называется языком, распознаваемым данным конечным автоматом.
Определение 1. Язык L называется регулярным, если для него можно
построить распознающий конечный автомат.
Конечный автомат удобно задавать диаграммой его переходов. Диаграмма представляет собой ориентированный граф, вершины которого одноименны состояниям автомата; дуга из вершины qi в вершину qk с надписанной над ней буквой a j проводится тогда и только тогда, когда g qi ,a j qk . В
случае, когда переход из qi в qk осуществляется под воздействием любой из
букв некоторого подмножества S , S A , все буквы этого подмножества
подписываются над соответствующей дугой (вместо перечня всех букв допускается сокращенная запись « x S » или « S ». Если произвольное состоя-
20
ние qi входит в F , то данный факт на диаграмме отмечается жирным кружком, выделяющим вершину qi .
На рис.1 примера 1 показана диаграмма автомата K 1 , работающего над
словами алфавита A a ,b,c. Автомат имеет два состояния: q0 и q1 , причем
«хорошим» является только состояние q1 . Начав работу в состоянии q0 , автомат под воздействием букв a ,b из этого состояния не выходит; под воздействием буквы c реализуется переход в состояние q1 ; любая далее поступающая буква оставляет автомат в том же состоянии. Таким образом, автомат K 1
распознает язык L1 , состоящий из слов, имеющих в своем составе букву c .
Пример 1.
a ,b,c
a ,b
c
q0
q1
Рисунок 1.
Класс регулярных языков замкнут относительно основных теоретикомножественных операций – объединения, пересечения, разности.
Пусть L1 и L2 - регулярные языки, распознаваемые конечными автоматами K 1 Q1 , A, q10 , g1 , F 1 и K 2 Q 2 , A, q 20 , g 2 , F 2 соответственно. Считаем, что
Q1 q10 , q11 , q12 , ..., q1 f и Q 2 q 2 0 , q 21 , q 2 2 , ..., q 2 h . Автомат K Q, A, q0 , g , F , распознающий язык L1 L2 строим следующим образом. Полагаем Q Q1 Q 2 ;
каждое состояние конструируемого автомата содержит две компоненты, левую и правую. Начальным состоянием нового автомата считаем (q01 , q02 ) , а
функцию переходов g определяем следующим образом:
g ((qi1 , q 2j ), ak ) ( g 1 (qi1 , ak ), g 2 (q 2j , ak )) .
Очевидно, по первой компоненте автомат K моделирует действия автомата K 1 , а по второй компоненте – действия автомата K 2 . Входное слово
Принадлежит объединению языков L1 L2 тогда и только тогда, когда
после его обработки автомат K окажется в состоянии, у которого либо первая компонента принадлежит совокупности F 1 , либо вторая компонента принадлежит совокупности F 2 . Таким образом, следует положить:
F ( F 1 Q 2 ) (Q1 F 2 ) .
Все компоненты автомата K определены, его построение закончено.
Автомат K Q, A, q0 , g , F , распознающий язык L1 L2 , отличается от
K только последней своей компонентой. Следует положить
F F1 F 2 .
Автомат K \ Q, A, q0 , g , F \ , распознающий язык L1 \ L2 , отличается от K
только последней своей компонентой. Следует положить
F \ F 1 Q2 .
21
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
ОСНОВНАЯ ЛИТЕРАТУРА
1. Балюкевич, Э.Л. Дискретная математика [Электронный ресурс]: учебное пособие/ Балюкевич Э.Л., Ковалева Л.Ф., Романников А.Н.- Электрон. текстовые данные.- М.: Евразийский открытый институт, 2009.173c.- Режим доступа: http://www.iprbookshop.ru/10661.- ЭБС
«IPRbooks», по паролю
2. Иванов, Б.Н. Дискретная математика. Алгоритмы и программы. Полный курс [Текст]: учеб. пособие для студ. вузов/ Б.Н. Иванов.- М.:
ФИЗМАТЛИТ, 2007.- 408 с.
3. Ковалёва, Л.Ф. Дискретная математика в задачах [Электронный ресурс]: учебное пособие/ Ковалёва Л.Ф..- Электрон. текстовые данные.М.: Евразийский открытый институт, 2011.- 142c.- Режим доступа:
http://www.iprbookshop.ru/10660.- ЭБС «IPRbooks», по паролю
4. Поздняков, С.Н. Дискретная математика [Текст]: учеб. пособие для
студ. вузов / С.Н. Поздняков, С.В. Рыбин.- М.: Академия, 2008.- 448 с.
5. Соболева, Т.С. Дискретная математика [Текст]: учеб. пособие для студ.
вузов/ Т.С. Соболева, А.В.Чечин; под ред. А.В.Чечкина.- М.: Академия,
2006.- 256 с.
6. Хаггарти, Р. Дискретная математика для программистов [Электронный
ресурс]: учебное пособие/ Хаггарти Р..- Электрон. текстовые данные.М.:
Техносфера,
2012.400c.Режим
доступа:
http://www.iprbookshop.ru/12723.- ЭБС «IPRbooks», по паролю
ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА
1. Новиков, Ф.А. Дискретная математика [Текст]: учеб. пособие для студ.
вузов/ Ф.А. Новиков.- СПб.: Питер, 2001.- 304 с.
2. Яблонский, С.В. Введение в дискретную математику [Текст]: учеб. пособие для студ. вузов/ С.В. Яблонский; под ред. В.А. Садовничего.- М.:
Высш.шк., 2001.- 384 с.
22
