ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с

• Название: В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
• Дата: 12.09.2022
• Размер: 4.33 Mb.
• Имя файла: ДИСКРЕТНАЯ МАТЕМАТИКА (1).pdf
• Тип: Реферат; #673155
• страница: 13 из 25

Задания
1. Изучить и программно реализовать алгоритмы 3.10 — 3.12 вычисления транзитивного замыкания.
2. Усовершенствовать алгоритм 3.11 объединения степеней (АОС). Доказать, что A

(I

A )
N-2
= A

A
2

…

A
N-1
и вычислить транзитивное замыкание C отношения A по формуле A

(I

A)
N-2 3. Усовершенствовать алгоритм 3.12 Уоршалла (АУ) следующим образом. Рассмотрим выражение C
x,y
:= C
x,y
or C
x,z
and C
z,y
из алгоритма
Уоршалла. Здесь C
x,y
может изменить значение сложного на истинное только в том случае, если истинны C
x,z
и C
z,y
. Поэтому, если C
x,z
ложно, то C
x,y значение не изменит и нет смысла в поиске пары (z,y).
4. Разработать и программно реализовать генератор отношений на множестве мощности N и содержащих заданное число пар.
5. Разработать и написать программу, которая генерирует 100 отношений на множестве мощности N с заданным числом пар, для каждого отношения вычисляет транзитивное замыкание пятью алгоритмами и подсчитывает количество k выполнений операции сравнения. Значение
k при обработке различных отношений на множестве мощности N с заданным числом пар может быть разным, поэтому программа должна определять минимальное и максимальное значение k. Отношение, при обработке которого получено минимальное (максимальное) k, и его транзитивное замыкание, сохранить в файле. Выполнить программу при
N = 5, 10 и 15. Результат для каждого N представить в виде таблицы табл. 3.2), а сохраненные отношения — в виде графа. Таблица 3.2 Количество k выполнений операции сравнения Число пар в отношении
1
N
2
/4
N
2
/2
N
2

2/3
N
2
min max min max min max min max min max Алгоритм 3.10 Алгоритм 3.11 Усовершенствованный
АОС Алгоритм 3.12 Усовершенствованный АУ

147 Практическое занятие 3.3
Фактормножества Цель занятия научиться программно формировать фактормножества для заданного отношения эквивалентности и находить отношение эквивалентности для заданного разбиения. Задания
1. Отношение на множестве {1,2,3,4,5,6,7,8,9,10} (табл. 3.3) представить графом и характеристической функцией в матричной форме. Найти разбиение Ф, определяемое заданным отношением эквивалентности. Таблица 3.3 Варианты заданий
Вариант Отношение
1 Аи и x<11 и y<11 и ((x и y четные или x=y)}
2 Аи и x<11 и y<11 и ((x и y четные или
(x и y нечетные
A={(x,y) | x

N и y

N и x<11 и y<11 и (|x–y| кратно 5 или x=y)}
4 Аи и x<11 и y<11 и (x и y кратно 4 или x и y кратно 5 или x=y)}
5 Аи и x<11 и y<11 и (x+y — четно Аи и x<11 и y<11 и (|x–y| — четно Аи и x<11 и y<11 и (|x–y| кратно 3 или x=y)}
8 Аи и x<11 и y<11 и (x и y меньше 3 или x и y больше 3 или x=y)}
9 Аи и x<11 и y<11 и (|x–y| кратно 4 или x=y)}
10 Аи и x<11 и y<11 и (x и y кратно 3 или x и y кратно 5 или x=y)}
11 Аи и x<11 и y<11 и (x и y четно и меньше 5 или
x и y нечетно и больше 5 или x=y)}
12 Аи и x<11 и y<11 и (x и y четно и меньше 7 или
x=y)}
13 Аи и x<11 и y<11 и или
(x,y)

{6,7,8,9}
2
или x=y)}
14 Аи и x<11 и y<11 и или
(x,y)

{3,7,8,9}
2
или x=y)}
15 А | или (x,y)

{2,7,8,9}
2
или (x,y)

{4,5,6}
2
}
2. Программно реализовать алгоритм построения отношения эквивалентности по разбиению S множества М.

148 Практическое занятие 3.4 Упорядоченные множества Цель занятия изучить упорядоченные множества, алгоритм топологической сортировки, научиться представлять множества диаграммами Хассе, находить минимальные (максимальные) и наименьшие (наибольшие) элементы упорядоченного множества.
Задания Даны множества точек на плоскости М (рис. 3.23), М (рис. 3.24) и отношение порядка (табл. 3.5). Для определения отношения на множестве точек примем следующие обозначения a
x
— абсцисса точки a;
a
y
— ордината a. На рис. 3.23 координаты правой верхней точки считать
(1,1). На рис. 3.24 координаты самой верхней точки считать (0,2), а координаты самой правой точки считать (2,0).
1. Написать программы, формирующие матрицы отношения порядка, в соответствии с вариантом задания (табл. 3.5), на множествах Ми М 2. Написать программы, формирующие матрицы отношения доминирования по матрицам отношения порядка.
3. Написать программу, реализующую алгоритм топологической сортировки по матрице отношения доминирования.
4. Изобразить диаграмму Хассе отношения доминирования на множествах Ми М 5. Найти минимальные и максимальные элементы множеств Ми М 6. Найти, если существуют, наименьший и наибольший элементы множеств Ми М
2
Рис. 3.23. Множество М Рис. 3.24. Множество М
Y
X
X

149 Таблица 3.5 Варианты заданий Вариант Отношение
1 Аи Аи А | a
x
– a
y
≤
b
x
– b
y
}
5 Аи А | a
x
– b
x
≤
a
y
– b
y
}
7 А | a
y
≤ b
y
}
8 А | a
x
2
+ a
y
2
<
b
x
2
+ b
y
2
}
9 Аи А | a
x
–
b
x
≤ b
y
–
a
y
}
11 А | a
x
≤ b
y
}
12 Аи Аи А | a
x
+ a
y
<
b
x
+ b
y
}
15 Аи Контрольные вопросы и задания
1. Что называется упорядоченной парой Чем различаются упорядоченная пара и двухэлементное множество Какое отличие в обозначениях упорядоченной пары и двухэлементного множества
2. Что является прямым (декартовым) произведением множеств
3. Определите мощность прямого (декартова) произведения двух заданных конечных множеств.
4. Что называется бинарным соответствием
5. Что является областью отправления и областью определения бинарного соответствия Что является областью прибытия и областью значений бинарного соответствия
6. Определите область отправления, область определения, область прибытия и область значений заданного бинарного соответствия.
7. Что называется образом и прообразом элемента при бинарном соответствии. Определите образ каждого элемента из области определения заданного соответствия. Определите прообраз каждого элемента из области прибытия заданного соответствия.
9. Какое бинарное соответствие называется функциональным

150 10. Какое соответствие называется полностью определенным Что называется отображением
11. Какая функция называется сюръективной, а какая — инъектив- ной
12. Что называется взаимно-однозначным отображением
13. Что называется бинарным отношением
14. Какое бинарное отношение называется пустым, тождественным, универсальным
15. Приведите примеры задания отношений различными способами.
16. Определите, принадлежит ли заданная упорядоченная пара композиции заданных отношений. Назовите упорядоченную пару, принадлежащую композиции заданных отношений и упорядоченную пару, не принадлежащую композиции этих отношений.
17. Дайте определения основными производным свойствам отношений. Определите свойства заданного отношения.
18. Что называется замыканием отношения относительно заданного свойства
19. Получите транзитивное замыкание отношения, заданного графом. Определите порядок функции временной сложности изученных алгоритмов вычисления транзитивного замыкания.
21. Что называется классом эквивалентности и фактормножеством?
22. Постройте отношение эквивалентности, определяемое заданным разбиением.
23. Что называется упорядоченным множеством
24. Какие элементы упорядоченного множества называются сравнимыми, а какие — несравнимыми
25. Какое множество называется линейно упорядоченным
26. Постройте отношение строгого порядка, ассоциированного с заданным отношением порядка. Используйте матричное и графовое представление отношений.
27. Постройте отношение доминирования, ассоциированного с заданным отношением порядка. Используйте матричное и графовое представление отношений.
28. Что представляет собой транзитивное замыкание отношения доминирования, ассоциированного с заданным отношением порядка
29. Определите основные свойства отношения доминирования.
30. Является ли отношение доминирования отношением порядка
31. Что такое диаграмма Хассе?
32. Что такое топологическая сортировка Примените алгоритм топологической сортировки к отношению, граф которого имеет циклы.

151
4. ГРАФЫ
4.1. Основные понятия Первая работа по теории графов принадлежит Л. Эйлеру, и опубликована она была в 1736 г, однако термин граф впервые появился в книге венгерского математика Д. Кенига в 1936 г. Дадим определение графа. Пусть V — непустое множество, V
{2}
— множество всех его двухэлементных подмножеств. Пара (V,E), где Е

V
{2}
называется графом неориентированным графом. Граф называется конечным, если множество V конечно. В дальнейшем под термином граф будем понимать конечные графы. Элементы множества V называются вершинами графа, а элементы множества Е называются ребрами графа. Число вершин графа G = называется его порядком. Исходя из определения графа, каждому ребру соответствует двухэлементное подмножество вершин. Если подмножество {v
1
,v
2
} соответствует ребру е, то ребро е инцидентно вершинами, а вершины v
1
и
v
2
смежны. Вершины v
1
и v
2
называются концевыми вершинами ребра е. Два ребра, инцидентные одной вершине, называются смежными. Таким образом, смежность есть отношение между однородными элементами графа, а инцидентность — отношение между разнородными элементами графа. Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается Г. Если A

V, то ГА — множество всех вершин, смежных с вершинами из А . Количество ребер, инцидентных вершине v, называется степенью вершины v и обозначается d(v). d(v) = Г Если степени всех вершин равны k, то граф называется регулярным степени k . Граф можно представить графически в виде диаграммы каждая вершина представляется точкой или окружностью, а каждое ребро представляется линией, соединяющей его концевые вершины. Граф G = (V,E), V = {v
1
,v
2
,v
3
,v
4
}, E = {{v
1
,v
2
}, {v
1
,v
4
}, {v
2
,v
3
}, {v
2
,v
4
},
{v
3
,v
4
}} представлен диаграммой на рис. Один и тот же граф может быть представлен различными диаграммами, так как расположение вершин не имеет значения. На рис представлена другая диаграмма графа G.

152
v
1
v
2
v
2
v
3
v
4
v
1
v
4
v
3
Рис.4.1.
Диаграмма графа G Рис. Диаграмма графа G Часто рассматриваются следующие родственные графам объекты.
1. Если элементами множества E являются упорядоченные пары, то граф называется ориентированным или орграфом. В этом случае элементы множества Е называются дугами. Если дуга (v
1
,v
2
)

E, то вершины и называются ее началом и концом соответственно. Дуга имеет направление от начала к концу. На диаграмме направление дуги указывается стрелочкой. На рис приведен пример диаграммы орграфа. Число дуг, выходящих из вершины, называется полустепенью исхода, а число входящих дуг — полустепенью захода. Орграф называется симметричным, если полустепень исхода каждой вершины равна полу- степени захода.
v
1
v
2
v
3
Рис Диаграмма орграфа. Если элементом множества E может быть пара одинаковых не различных) элементов множества V, то такой элемент множества E называется петлей, аграф называется псевдографом. На рис приведен пример диаграммы псевдографа.
v
1
v
2
v
3
Рис. Диаграмма псевдографа

153 3. Если E является мультимножеством, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, аграф называется мультиграфом. На рис приведен пример диаграммы мультиграфа.
v
1
v
2
v
3
v
4
Рис. Диаграмма мультиграфа
4. Если элементом множества E являются необязательно двухэлементные, а любые подмножества множества V, то такие элементы множества называются гиперребрами, аграф называется гиперграфом. На диаграмме гиперграфа гиперребро представляет собой замкнутую линию, охватывающую инцидентные гиперребру вершины. Диаграмма гиперграфа GG = (V,E), V = {v
1
,v
2
,v
3
,v
4
}, E = {{v
1
,v
2
,v
4
}, {v
1
,v
2
}, представлена на рис.
v
1
v
2
v
3
v
4
Рис. Диаграмма гиперграфа
5. Если задана функция F: V

M и/или H: E

M, то множество М называется множеством весов, аграф называется взвешенным. На диаграмме весами отмечаются вершины и/или ребра. В качестве весов обычно используются числа или символы. На рис приведен пример диаграммы взвешенного графа.

154
















0 1
0 1
0 1
0 1
1 1
0 1
0 0
1 1
1 0
0 1
0 1
1 1
0
v
1 10 6
v
2 20 15 1 4 90 22
v
3
v
4 30 Рис. Диаграмма взвешенного графа
4.2. Матричные способы представления графов Любой граф может быть представлен в матричной форме. Матрицей смежности графа G = (V,E) называется матрица A порядка, где n = |V|. Элемент матрицы смежности а
= 1, если (v
i
,v
j
)

Е,
v
i
,v
j

V и a
ij
= 0, если (v
i
,v
j
)

Е. В матрице смежности строки и столбцы соответствуют вершинам графа. На рис. 4.8 представлены граф в виде диаграммы и его матрица смежности. а v
1
v
2
v
5
v
3
б
А Рис. Граф в виде диаграммы и матрица смежности:
а — диаграмма графа б — матрица смежности Для неориентированных графов матрица смежности симметрична относительно главной диагонали.

155
















1 0
1 0
0 0
0 1
1 0
1 1
0 0
0 1
0 0
0 1
0 0
0 1
1 0
0 1
0 0
0 0
1 1
1
















0 1
0 1
0 0
0 1
0 0
0 0
0 0
0 0
1 1
0 0
1 0
0 0
0





















1 0
0 0
1 1
1 1
0 0
0 1
0 1
0 0
0 1
1 0
0 0
0 Матрицей инцидентности графа G = (V,E) называется матрица B порядка n

m, где n = |V|, m = |E|. Элементы матрицы инцидентности b
ij определяются следующим образом b
ij
= 1, если я вершина является началом й дуги, b
ij
= –1, если я вершина является концом й дуги,
b
ij
= 0, если я вершина и я дуга не инцидентны. Для неориентированных графов в матрице инцидентности элементам достаточно присваивать только два символа (1 и 0). В матрице инцидентности строки соответствуют вершинам графа, а столбцы — ребрам (дугам. Для графа, представленного на рис, матрица инцидентности имеет вид
В
На рис приведен пример диаграммы орграфа и его матрицы смежности и инцидентности. а v
1
v
2
v
3
v
5
б в
А В Рис. Диаграмма орграфа, матрицы смежности и инцидентности: а — диаграмма орграфа б — матрица смежности в — матрица инцидентности

156






4 3
4 3
5 5
4 2
2 Матрицей дуг (списком дуг графа G = (V,E) называется матрица С порядка 2

m, где m = |E|. Элементы матрицы С
определяются следующим образом си с
= v
j
, если e
k
= (v
i
,v
j
), те. если я вершина является началом й дуги, а я вершина является концом й дуги. Для графа, представленного на рис, матрица дуг имеет вид
C= Для представления взвешенного графа c взвешенными дугами вместо единичных элементов матрицы смежности удобно записать веса соответствующих дуга веса несуществующих дуг полагать равными Такая матрица называется матрицей весов. Если граф представлен матрицей инцидентности или матрицей дуг, то задать веса дуг можно m- разрядным вектором (m — количество дуг в графе, в котором й элемент определяет вес й дуги. Если в графе взвешены вершины, то задать веса вершин можно разрядным вектором (n — количество вершин в графе, в котором й элемент определяет вес й вершины. Для хранения в памяти ЭВМ матриц смежности, инцидентности, матриц дуги матриц весов удобно использовать двумерные массивы.