Xreferat.com » Рефераты по информатике и программированию » Основы дискретной математики

Основы дискретной математики

0, 0, 1)) = (1, 1, 0, 1, 0, 0) или (0, 0, 1, 0, 0, 0) = (1, 1, 1, 1, 0, 0).

Таким образом, А Δ В = {1, 2, 3, 4}.


2.2 Практическая часть


2.2.1 Задание к работе

1. Изучить теоретический материал, включая и дополнительные сведения, представленные в теоретической части.

2. Задать самостоятельно универсальное множество X, множества A, B, C (или некоторые из них, т. к. в некоторых вариантах используются только два множества).

3. Cформировать характеристические векторы для исходных множеств и получить результирующее множество (по варианту), используя характеристические вектора.

4. Вычислить элементы результирующего множества (по варианту), используя операции над множествами.

5. Вывести результаты, полученные в пункте 3 и пункте 4.

6. Сравнить эти результаты и сделать выводы.

7. Пункты 3 и 4 выполнить двумя способами: аналитически и реализовать в виде приложения на Delphi.

Примечание:

1. Если в выражении используется операция разности или симметрической разности, то при выполнении действий с характеристическими векторами (пункт 3) заменить их другими операциями на множествах (использовать формулы из лекций и [23]).

2. При выполнении пункта 4 операцию симметрической разности заменить другими операциями, которые используются в Object Pascal.

3. В качестве дополнительного задания предлагается реализовать любой описанный в теоретической части алгоритм в виде приложения на Delphi.


2.2.2 Примеры выполнения

Пример 1.

1) Задание по варианту

I:={1,2,3,4,5,6,7}

Значения векторов A, B, C берутся произвольно, но с учетом, что количество элементов не должно быть больше 7.

Найти: характеристический вектор множеств A, B и C, характеристический вектор множества D – Vd, перейти от Vd к D.

2) Создать приложение в среде Delphi, которое решит данную задачу.

3) Решить задачу аналитически.

4) К защите данной работы необходимо знать теоретический материал по данной теме из лекций и методички, а также ответить на «Вопросы для самопроверки».

D=Основы дискретной математики

Аналитическое решение:


Основы дискретной математики

Основы дискретной математики

Основы дискретной математики

Основы дискретной математики

Основы дискретной математики


Характеристические векторы


A:={1,0,1,0,1,0,1}

B:={1,1,1,1,0,0,0}

C:={1,0,1,1,1,0,1}

Основы дискретной математики


Переходим от Основы дискретной математики к D

D:= Основы дискретной математики={1,3}

Форма


Основы дискретной математики

Рисунок 2.10 – Формы с результатами


Код программы

implementation

procedure TForm1. Button1Click (Sender: TObject);

var

n, A, B, C: set of char;

s, s1, s2, s3, s11, s22, s33, s4, s44, s5, s55:string;

i:integer;

begin

s:='1234567';

n:=['1'..'7'];

A:=['1', '3', '5', '7'];

B:=['1', '2', '3', '4'];

C:=['1', '3', '4', '5', '7'];

begin

for i:=1 to 7 do

begin

if (s[i] in A) then

s1:=s1+'1'

else

s1:=s1+'0';

end;

s11:=' {'+s1+'}';

label7. Caption:=s11;

end;

begin

for i:=1 to 7 do

begin

if (s[i] in B) then

s2:=s2+'1'

else

s2:=s2+'0';

end;

s22:=' {'+s2+'}';

label12. Caption:=s22;

end;

begin

for i:=1 to 7 do

begin

if (s[i] in C) then

s3:=s3+'1'

else

s3:=s3+'0';

end;

s33:=' {'+s3+'}';

label13. Caption:=s33;

{Задаем характеристические векторы}

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, ориентированная в противоположном направлении, эквивалентна одному неориентированному ребру.

Таким образом, мы можем любой неориентированный граф превратить в ориентированный. При этом количество ребер увеличивается в 2 раза.

Граф называется плоским, если может быть изображен на плоскости так, чтобы его ребра пересекались только в вершинах.

Граф назовем однородным степени k, если локальные степени во всех его вершинах равны k, т. е. Основы дискретной математики


Основы дискретной математики

Рисунок 3.4 – Бесконечный однородный граф

Основы дискретной математики

Рисунок 3.5 – Конечный однородный граф


Граф H называется частью графа G, если подмножество вершин его V(H) содержится во множестве вершин V(G) и все ребра части графа H являются ребрами G и обозначается HМG.

Для любой части H графа G существует дополнение Основы дискретной математики, которое состоит из всех ребер графа G, не принадлежащих H.

Основы дискретной математикиОсновы дискретной математикиОсновы дискретной математикиОсновы дискретной математики

Рисунок 3.6 – Граф G Рисунок 3.7 – Часть графа G


Пусть H1 и H2 – две части графа G. Сумма этих частей H1UH2 есть часть, состоящая из ребер, принадлежащих H1 или H2. Пересечение D=H1Основы дискретной математикиH2 – есть часть, состоящая из ребер, принадлежащих H1 и H2 одновременно. Две части не пересекаются по вершинам, если они не имеют общих вершин, и, следовательно, ребер. Части H1 и H2 не пересекаются по ребрам, если они не имеют общих ребер H1Основы дискретной математикиH2=0. Если H1 и H2 непересекающиеся части графа G, то их сумма называется прямой и H1UH2=G.

Бинарные отношения и графы

Бинарные отношения можно изобразить графом: вершины графа – элементы множества V, ребра графа соединяют вершины, которые находятся в отношении друг к другу.

Любой граф определяет бинарное отношение R на множестве вершин V, если для каждого ребра (a, b) выполняется aRb. Нельзя говорить о взаимнооднозначном соответствии между графами и бинарными отношениями. Пустому бинарному отношению соответствует нуль-граф О. Универсальному бинарному отношению отвечает полный граф U. Бинарному отношению aRb, где R – отрицание R (дополнительное бинарное отношение) отвечает граф G(R)=U(V) – G(R). Обратному бинарному отношению bR*a отвечает обратный граф G (R*), т. е. граф с измененной ориентацией ребер. Операции, которые вводятся для бинарных отношений, могут быть перенесены на графы.

Симметричное бинарное отношение: если aRb, то bRa.

Рефлексивность: бинарное отношение aRa соответствует графу с петлей в каждой вершине.

Транзитивность: если aRb и bRc, то aRc. Для графа это означает, что если существует ребро (a, b) и ребро (b, c), то существует ребро (a, c). Такой граф называется связным.

Свойство связности можно рассмотреть как бинарное отношение, которое:

а) рефлексивно: вершина а связана сама с собой;

б) симметрично: если вершина а связана с вершиной b, то и вершина b связана с вершиной a;

в) транзитивно: если вершина a связана с вершиной b, и b связана с вершиной с, то вершина a связана с вершиной c.

Отношение связности есть отношение эквивалентности, т. е. оно разбивает множество вершин на попарно непересекающиеся классы.

Так как каждое множество Vi – множество связанных вершин, а вершины из разных множеств Vi не связаны, то имеем разложение графа G на части, которые не пересекаются и каждая часть – связная.

Подграфы G(Vi) называются связными компонентами графа G.

Каждый неориентированный граф распадается единственным образом в прямую сумму всех своих связных компонент.

Покрывающие деревья

Граф, не содержащий циклов, называется ациклическим. Деревом называется связный граф, не содержащий циклов. Пусть VG – число элементов в множестве вершин, VL – число элементов множества ребер дерева.


Основы дискретной математики

Рисунок 3.8 – Дерево


VG =VL 1

Добавим ребро – появляется цикл, удалим ребро – теряется связность. Лесом называется несвязный граф, компонентами которого являются деревья.

Пусть VLl – число элементов в множестве ребер леса, VGl – число элементов в множестве вершин леса, k – число деревьев в лесе.

VLl = VGl - k

Если дерево Т имеет корень, то дерево называется деревом с корнем. Выделим в дереве Т некоторую цепь.


Основы дискретной математики

Рисунок 3.9 – Дерево


Задача.

Как узнать, существуют ли циклы в графе?

Для дерева связь между числом ребер и числом вершин такова

Vl=VG 1. Рассмотрим s= Vl-VG+1, s называется цикломатическим числом. Если граф G – дерево, то s=0, если s не равно нулю, то в графе G есть циклы.

Алгоритм построения произвольного покрывающего дерева [20]

Ограничения: в графе не должно быть петель. Букетом называется произвольное дерево в графе.

Шаг 1. Выбираем произвольное ребро и помечаем его х (красим в голубой цвет).

Шаг 2. Выбираем другое произвольное непомеченное ребро. Если оба конца ребра лежат в одном букете, красим ребро в красный цвет. В противном случае – в голубой.

Шаг 3. Если все вершины графа вошли в один букет, то процедура заканчивается, т. к. помеченные голубым ребра образуют покрывающее дерево. В противном случае – перейти к шагу 2.


Основы дискретной математики

Рисунок 3.10 – Граф


1 шаг: (a, d) – помечаем голубым

2 шаг: (b, e) – помечаем голубым

3 шаг: (d, e) – помечаем голубым

4 шаг: (a, b) – помечаем красным

5 шаг: (a, c) – получаем голубым


Основы дискретной математики

Рисунок 3.11 – Дерево


Алгоритм построения минимального и максимального покрывающего дерева [21]

Пусть каждому ребру графа G присвоена длина (вес) l (x, y) (таблица 3.1). Весом дерева называется сумма весов ребер, входящих в дерево. Минимальным деревом называется дерево с минимальным весом.

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

Таблица 3.1 – Веса ребер графа


A b c d e
a 0 5 50 85 90
b 5 0 70 60 50
c 50 70 0 8 20
d 85 60 8 0 10
e 90 50 20 10 0

Порядок просмотра

(a, b) – 5 (b, e) – 50 упорядочим ребра по возрастанию

(c, d) – 8 (b, d) – 60

(d, e) – 10 (b, c) – 70

(c, e) – 20 (a, d) – 85

(a, c) – 50 (a, b) – 90

1 шаг: (a, b) – помечаем голубым

2 шаг: (c, d) – помечаем голубым

3 шаг: (d, e) – помечаем голубым

4 шаг: (c, e) – помечаем красным

5 шаг: (a, c) – помечаем голубым

Дерево построено!


Основы дискретной математики

Рисунок 3.12 – Дерево


Алгоритм построения максимального ориентированного дерева(алгоритм Эдмонса) [15]:

Шаг 1. Последовательно в произвольном порядке просматриваем вершины графа G0. Просмотр вершины заключается в том, чтобы из дуг, заходящих в эту вершину, выбрать дугу с максимальным весом. При просмотре следующих вершин к уже отобранным ранее дугам добавляются новые дуги. Если добавление ребра не нарушает свойства букета, то добавление ребер продолжается. Если новое ребро образует контур, перейти к шагу 2.

Шаг 2. В случае формирования контура строится уменьшенный граф путем стягивания дуг и вершин выявленного контура исходного графа Go в одну вершину V.

В новом графе веса ребер (xi, vi) полагаются равными


l (x, vi)=l (x, y)+l (r, s) – l (t, y),


где К – контур, а у – вершина, принадлежащая контуру.

l (x, vi) – ребро, переходящее в ребро l (x, vi)

l (r, s) – ребро, имеющее в контуре минимальный вес

l (t, y) – ребро, заходящее в вершину у и имеющее максимальный вес

Шаг 3. Выполняется тогда, когда вершины нового графа попадают в букет, а дуги образуют дерево.

Возможны 2 случая:

вершина Vo является корнем дерева, тогда необходимо рассмотреть ребра букета в новом графе совместно с ребрами контура. Удалить из рассматриваемого множества ребер ребро с минимальным весом;

если Vo не является корнем дерева – в букете нового графа имеется лишь одно ребро, заходящее в некоторую вершину Z и одно ребро контура, заходящее в ту же вершину. Удаляем ребро контура, заходящее в вершину Z.

Пример.


Основы дискретной математики

Рисунок 3.13 – Граф


Просмотр вершин: Букет получаемых ребер

a (da)

b (da) (cb)

c (da) (cb) (ac)

d (da) (cb) (ac) (bd)

Ребра (ac) (cb) (bd) (da) образуют контур. Минимальный вес ребра в контуре 2.

Стягиваем контур в одну вершину и рассматриваем граф:


Основы дискретной математики

Рисунок 3.14 – Граф


l(fe)=1

l (e, Vo)=l(ea)+2–3=3+2–3=2

l (f, Vo)=l (f, a)+2–3=-1

l (f, Vo) 1=l(fd)+2 l (b, d)=1+2–2=1

Просмотр вершин Букет ребер

e (fe)

f (fe)

Vo (fe) (eVo)

Получили множество ребер исходного графа Go такое:

(fe) (ea) – образуют букет

(ac) (cb) (bd) (da) – образуют контур

Vo не является контуром дерева, удаляем (da), поскольку (da) – ребро из контура. Получили дерево:

(fe) (ea) (ac) (cb) (bd) с весом l=1+2+3+2+2=10

Задача о кратчайших путях

Пусть G – ориентированный граф, Е – ребра графа. Каждому ребру соответствует число.


Основы дискретной математики

Рисунок 3.15 – Эйлеров цикл


Задача Эйлера о Кенигсбергских мостах [19]: необходимо выйти из любой точки города и вернуться в нее, при этом пройдя по каждому мосту только один раз. Эйлер свел эту задачу к графу: существует ли в конечном графе такой цикл, в котором каждое ребро участвует только один раз? Цикл, в котором каждое ребро графа G участвует всего один раз, называется эйлеровым циклом. Граф, содержащий эйлеров цикл, называется эйлеровым.

Дальнейшее развитие задачи об Эйлеровом цикле

Припишем ребрам графа длину μ (ai, aj). Требуется найти путь в графе, который проходит через все ребра и имеет наименьшую длину.

Пример.


Основы дискретной математики

Рисунок 3.16 – Граф


S – стартовая вершина. Из вершины S надо пройти по всем ребрам так, чтобы маршрут имел минимальную длину. Очевидно, что длина маршрута будет минимальной, если каждое ребро будет пройдено всего один раз – т. е. маршрут будет эйлеровым циклом.

Все локальные степени – четные, значит граф эйлеров.

Варианты прохождения по циклу:


1)

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: