Основы дискретной математики (стр. 13 из 23)
end;
begin
for i:=1 to 7 do
if((s1 [i])=(s2 [i])) and ((s3 [i])=(s2 [i])) and ((s3 [i])='1') then
s4:=s4+'1' else
s4:=s4+'0';
s44:=' {'+s4+'}';
label17. Caption:=s44;
{Находим Характеристический вектор
множества Vd}
end;
begin
for i:=1 to 7 do
if s4 [i]='1' then
s5:=s5+inttostr(i);
s55:=' {'+s5+'}';
label21. Caption:=s55;
{Переходим от Vd к D}
end;
end;
procedure TForm1. Button2Click
(Sender: TObject);
begin
close;
end;
end.
2.2.3 Вариантызаданий
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
16)
17)
18)
19)
20)
21)
22)
23)
24)
25)
26)
27)
28)
29)
30)
31)
32)
33)
34)
35)
36)
37)
38)
39)
40)
41)
42)
43)
44)
45)
46)
47)
47)
49)
50)
2.3 Вопросы для самопроверки
1) Какие основные символы, используемые в теории множеств, вы знаете?
2) Перечислите основные операции над множествами и функции, применимые к множествам, которые используются в Delphi.
3) Что такое множество? Как его обозначить? Как можно задать множество?
4) Какое множество называют счетным? Какое – пустым?
5) Что такое подмножество?
6) Сформулируйте основные свойства счетных множеств.
7) Определите понятие вектора, булеана.
8) Сформулируйте основные аксиомы теории множеств.
9) Какие соотношения (действия) между множествами вы знаете, как они обозначаются?
10) Какое множество можно назвать универсальным?
11) Какие операции (из аналогичных арифметическим) нельзя производить с множествами?
12) Что такое диаграмма Эйлера-Венна? Проиллюстрируйте с помощью диаграмм Эйлера-Венна объединение и пересечение трех множеств.
13) Дайте определение декартова произведения множеств; какие теоремы о декартовом произведении Вы знаете?
14) Поясните термин «мощность множества».
15) Сформулируйте (и докажите) основные тождества алгебры множеств.
16) Дайте определение проекции вектора.
17) Что понимается под соответствием между множествами?
18) Дайте определение функции с точки зрения теории множеств. Приведите пример.
19) Дайте определение бинарного отношения, перечислите свойства.
20) Какие отношения называют рефлексивными, транзитивными?
21) Что такое «класс эквивалентности»?
22) Для чего нужна диаграмма Хассе?
23) Дайте определение нечёткого множества.
24) Какие операции допустимы над нечёткими множествами?
25) Дайте определение расстояний Хемминга и его основных свойств.
26) Перечислите основные алгоритмы генерации множеств.
Практическая работа № 3. Элементы теории графов
Цель работы: изучение математических структур для представления графов, изучение наиболее известных алгоритмов на графах и построение приложений на Delphi для описания графов в виде математических структур, реализации некоторых алгоритмов на графах.
3.1 Теоретическая часть
В данном параграфе многие определения и рисунки взяты из [17] и [19], являются дополнительными сведениями для материала, рассматриваемого в [24].
Пусть V – конечное множество (множество вершин), А – множество упорядоченных пар вершин, элементы которого называются ребрами.
Тогда графом G (V, A) называется совокупность множества вершин и множества ребер. Вершины а и с соединяются ребром, если (а, с)ÌА.
Пусть дано множество вершин V и декартово произведение VхV – множество всевозможных пар вершин. Тогда графом G является подмножество декартового произведения.
Ребро графа G ориентировано, если порядок пары (a, b) существенен.
Ребро графа G не ориентировано, если порядок пары (a, b) несущественен.
Рисунок 3.1 – Ориентированный граф
Граф называется ориентированным, если все его ребра ориентированы.
Граф G называется неориентированным, если все его ребра неориентированы.
Смешанным графом называется граф, у которого есть как ориентированные, так и неориентированные ребра.
Каждому ребру E=ía, bý можно поставить в соответствие некоторое число.
Граф G, каждому ребру которого присвоено число (например, расстояние) называется сетью.
Пусть даны a, b – вершины графа. Ребро E их соединяет. Тогда говорят, что ребро E инцидентно вершинам a и b. И обратно – вершины a и b инцидентны ребру E.
При изображении графа имеется большая свобода в размещении вершин и дуг.
Рисунок 3.2 – Три изображения одного и того же графа
Пусть G и G1 графы, V и V1 – множества их вершин соответственно. Графы G и G1 изоморфны, если существует взаимнооднозначное соответствие между множествами их вершин V и V1 и вершины в графе G соединены ребром в том и только том случае, если соответствующие вершины соединены ребром в графе G1.
Если графы G и G1 ориентированы, то направления ребер должны соответствовать друг другу. Изоморфные графы имеют одинаковые свойства.
Вершина, не инцидентная никакому ребру, называется изолированной. Граф, состоящий из изолированных вершин, называется нуль граф. Обозначается через О.
Граф, любые две вершины которого соединены ребром, называется полным графом U=U(V).
Петлей называется ребро L=(a, a). Петля считается неориентированным ребром.
Рисунок 3.3 – Петля
Пара вершин может соединяться несколькими различными ребрами.
Пара ребер Ei Ej, ориентированная в противоположном направлении, эквивалентна одному неориентированному ребру.