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

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

(sa) (ab) (bc) (cd) (db) (ds)

2) (sa) (ab) (bd) (dc) (cb) (bs)

3) (sb) (bc) (cd) (db) (ba) (as)

4) (sb) (bd) (dc) (cb) (ba) (as)


Длина эйлерова цикла – 22. Любой из вариантов 1–4 содержит каждое ребро графа, следовательно, длина одинакова для всех циклов 1–4. Длина эйлерова цикла не зависит от того, какая вершина будет выбрана за исходную.

Задача поиска эйлерова цикла – это задача о: – поиске наилучшего способа прохождения бригады по дорогам; – прохождении с/х техники по полям.

Впервые эта задача рассматривалась в связи с нахождением оптимального маршрута следования почтальона, который доставляет письма своим адресатам и должен при этом пройти минимальный путь.

Алгоритм нахождения эйлерова цикла для неориентированного графа [19]:

Дан эйлеров граф – т. е. граф с четными локальными степенями.

Найдем первое ребро х, инцидентное вершине S. Затем найдем ребро, смежное с ребром х, которое не образует цикл и еще не было использовано. Продолжим этот процесс до тех пор, пока не вернемся в вершину S. Если в построенный цикл С1 вошли все ребра графа – задача решена.

Если в построенный цикл С1 вошли не все ребра – строим цикл С2, состоящий из неиспользованных ребер и начинающийся с произвольного неиспользованного ребра.

Таким образом, строим циклы С2, С3,….Образование циклов продолжается до тех пор, пока не будут использованы все ребра.

Все циклы Сi необходимо объединить в один цикл. Условие объединения циклов С1 и С2 – наличие у них общей вершины х. Начинаем движение с любой вершины и двигаемся по циклу С1 до тех пор, пока не дойдем до х. Затем проходим ребро. С» и возвращаемся в х. Продолжаем обход по оставшимся ребрам до возвращения к исходной точке. Эта процедура легко обобщается на случай любого числа объединяемых циклов.

Циклы Эйлера для ориентированного графа

Алгоритм построения эйлерова цикла в эйлеровом ориентированном графе является аналогом алгоритма построения эйлерова цикла для неориентированного графа.

Строятся циклы Сi с учетом ориентации ребер, и затем все циклы объединяются в один.

Гамильтонов цикл (задача о коммивояжере)

Простой цикл, проходящий через каждую вершину графа только один раз, называется гамильтоновым циклом.

Если ребрам приписана длина, то различные варианты циклов отличаются друг от друга. Поэтому ставится задача нахождения гамильтонова цикла, имеющего минимальную длину.

Гамильтонов цикл наименьшей длины называется оптимальным гамильтоновым циклом (ОГЦ)

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

Решением задачи о коммивояжере не всегда является ОГЦ.

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


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

Рисунок 3.17 – Ребра, входящие в гамильтонов цикл С


К сожалению, алгоритм решения данной задачи, дающий оптимальное решение, пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно. Однако существуют алгоритмы поиска субоптимального решения [1]. Субоптимальное решение необязательно даст цикл минимального общего веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамильтоновых циклов! Один из таких алгоритмов – алгоритм ближайшего соседа.

Этот алгоритм выдает субоптимальное решение задачи коммивояжера, генерируя гамильтоновы циклы в нагруженном графе с множеством вершин V. Цикл, полученный в результате работы алгоритма, будет совпадать с конечным значением переменной маршрут, а его общая длина – конечное значение переменной w.

begin

Выбрать v ? V;

маршрут:=v;

w:=0;

v':=v;

Отметить v';

while остаются неотмеченные вершины do begin

Выбрать неотмеченную вершину и,

ближайшую к v';

маршрут:= маршрут u;

w:= w + вес ребра v'u;

v':=u;

Отметить v';

end

маршрут:= маршрут v;

w:= w + вес ребра v'v;

end

Пример. Примените алгоритм ближайшего соседа к графу, изображенному на рисунке 3.18. За исходную вершину возьмите вершину D.


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

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

Таблица 3.2 – Алгоритм ближайшего соседа


и маршрут w

v'


Исходные значения – D 0 D

С dc 3 С

А DCA 9 A

В DCAB 14 В
Последний проход В DCABD 24 В

В результате работы алгоритма был найден гамильтонов цикл DCABD общего веса 24. Делая полный перебор всех циклов в этом маленьком графе, можно обнаружить еще два других гамильтоновых цикла: ABCDA общего веса 23 и ACBDA общего веса 31. В полном графе с двадцатью вершинами существует приблизительно 6,1 * 10^16 гамильтоновых циклов, перечисление которых требует чрезвычайно много машинной памяти и времени.

Реализация примера данного алгоритма в Delphi:

procedure TForm1. Button1Click (Sender: TObject);

const mat:array [1.. 4,1..4] of byte=((0,5,6,8), (5,0,7,10), (6,7,0,3), (8,10,3,0));

Versh:array [1..4] of char=('a', 'b', 'c', 'd');

buk:char='d';

Type t=set of 'a'..'d';

Var dlina, i, j, min, n, k, s:byte;

put:string;

z:t;

begin

dlina:=0;

Memo1. Lines. Clear;

for i:=1 to 4 do if versh[i]=buk then begin n:=i; s:=i;

include (z, buk);

put:=put+buk;

end;

for j:=1 to 3 do begin

if mat [n, 1]<>0 then begin min:=mat [n, 1]; k:=1; end

else begin min:=mat [n, 2]; k:=2; end;

for i:=1 to 4 do

if (mat [n, i]<min) and (mat [n, i]<>0) and (not (versh[i] in z)) then begin

min:=mat [n, i];

k:=i;

end;

dlina:=dlina+min;

put:=put+versh[k];

include (z, versh[k]);

n:=k;

end;

put:=put+'d';

dlina:=dlina+mat [k, s];

Memo1. Lines. Add ('маршрут:'+' '+put);

Memo1. Lines. Add ('длина маршрута='+IntToStr(dlina));

end;

end.


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

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


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


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

1 изучить теоретический материал по методическому пособию [24], лекциям и записям на практических занятиях;

2 получить задание по индивидуальному варианту в виде графа или матрицы смежности, в первом случае построить матрицу смежности, во втором – нарисовать граф;

3 составить подробное описание графа: ориентированный или неориентированный, количество вершин, дуг (рёбер), содержит ли циклы и какие, найти степени вершин, количество компонент связности и т. д.;

4 создать приложение на Delphi для расчёта матрицы инцидентности по известной матрице смежности (если граф достаточно сложный, то можно взять подграф этого графа);

5 в качестве дополнительного творческого задания создать приложение на Delphi для реализации алгоритма ближайшего соседа, алгоритма Прима, алгоритма Уоршелла, алгоритма Дейкстры, алгоритма определения количества компонент связности графа и других известных алгоритмов на графах. [13], [17], [18], [19], [20], [21].


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

Пример 1: По заданной матрице смежности построить матрицу инцидентности.

implementation

procedure TForm1. UpDown1Click (Sender: TObject; Button: TUDBtnType);

begin

with UpDown1 do begin

with StringGrid1 do begin

RowCount:=Position;

ColCount:=Position;

end;

StringGrid2. RowCount:=Position;

end;

end;

procedure TForm1. BitBtn1Click (Sender: TObject);

var i, j, CD, P, n:byte;

MS:array of array of byte;

MI:array of array of ShortInt;

begin

P:=StrToInt (Edit1. Text);

SetLength (MS, P, P);

CD:=0;

for i:=0 to P 1 do for j:=0 to P 1 do begin

MS [i, j]:=StrToInt (StringGrid1. Cells [j, i]);

if MS [i, j]=1 then inc(CD);

end;

SetLength (MI, P, CD);

for i:=0 to High(MS) do for j:=0 to CD 1 do MI [i, j]:=0;

n:=0;

for i:=0 to High(MS) do for j:=0 to High(MS) do

if MS [i, j]=1 then begin

MI [i, n]:=1;

MI [j, n]:=-1;

inc(n);

end;

StringGrid2. ColCount:=CD;

for i:=0 to High(MS) do for j:=0 to CD 1 do

StringGrid2. Cells [j, i]:=IntToStr (MI[i, j]);

end;

end.


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

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


Пример 2: По заданной матрице смежности построить матрицу инцидентности.

var

Form1: TForm1;

const maxv=4;

type canh=record dinh1, dinh2:byte;

dodai:real; end;

dothi=record n:byte;

l:array [1..maxv, 1..maxv] of real;

x, y:set of 1..maxv;

t:array [1..maxv] of canh;

nt:byte;

it:real; end;

implementation

{$R *.dfm}

procedure TForm1. Button1Click (Sender: TObject);

var g:dothi;

min:real;

x, y, x0, y0:1..maxv;

i, j:byte;

begin memo1. Clear;

g.n:=maxv;

edit1. Text:=inttostr(maxv);

stringgrid1.cells [0,0]:=' Номер';

for i:=1 to maxv do begin

stringgrid1.cells [0, i]:=inttostr(i);

stringgrid1.cells [i, 0]:=inttostr(i); end;

g.nt:=0; g.it:=0; g.x:=[1..g.n]; g.y:=[1];

for i:=1 to maxv do

for j:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]);

while g.nt<g.n 1 do begin

min:=-1;

for x:=1 to g.n do

for y:=1 to g.n do

if (x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then

begin

if (min=-1) or (min>g.l [x, y]) then begin

min:=g.l [x, y];

x0:=x; y0:=y; end;

end;

g.y:=g.y+[y0];

g.nt:=g.nt+1;

g.it:=g.it+min;

with g.t [g.nt] do begin

dinh1:=x0;

dinh2:=y0;

dodai:=min; end; end;

for i:=1 to (maxv 1) do

with g.t[i] do

memo1. Lines.add ('Ребро: '+inttostr(dinh1)+inttostr(dinh2)+' '+

'Весом: '+floattostr(dodai));

end;

end.


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

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


Пример 3: Составить приложение на Delphi, реалилующее алгоритм Уоршелла.

var

Form1: TForm1;

const maxv=4;

type canh=record dinh1, dinh2:byte;

dodai:real; end;

dothi=record n:byte;

l:array [1..maxv, 1..maxv] of real;

x, y:set of 1..maxv;

t:array [1..maxv] of canh;

nt:byte;

it:real; end;

implementation

{$R *.dfm}

procedure TForm1. Button1Click (Sender: TObject);

var g:dothi;

min:real;

x, y, x0, y0:1..maxv;

i, j:byte;

begin memo1. Clear;

g.n:=maxv;

stringgrid1.cells [0,0]:=' Номер';

for i:=1 to maxv do begin

stringgrid1.cells [0, i]:=inttostr(i);

stringgrid1.cells [i, 0]:=inttostr(i); end;

g.nt:=0; g.it:=0; g.x:=[1..g.n]; g.y:=[1];

for i:=1 to maxv do

for j:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]);

while g.nt<g.n 1 do begin

min:=-1;

for x:=1 to g.n do

for y:=1 to g.n do

if (x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then

begin

if (min=-1) or (min>g.l [x, y]) then begin

min:=g.l [x, y];

x0:=x; y0:=y; end;

end;

g.y:=g.y+[y0];

g.nt:=g.nt+1;

g.it:=g.it+min;

with g.t [g.nt] do begin

dinh1:=x0;

dinh2:=y0;

dodai:=min; end; end;

for i:=1 to (maxv 1) do

with g.t[i] do

memo1. Lines.add ('Ребро: '+inttostr(dinh1)+inttostr(dinh2)+' '+

'Весом: '+floattostr(dodai));

end;

end.


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

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


3.2.3 Вариантв заданий


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


3.3 Вопросы для самопроверки


1) Какие операции над графами Вы знаете?

2) Как формируется матрица смежности?

3) Как формируется матрица весов?

4) Как формируется матрица достижимости?

5) Как формируется матрица инцидентности?

6) Перечислите основные понятия, относящиеся к графам-деревьям.

7) Приведите пример сортировки и поиска в деревьях.

8) Для чего применяется алгоритм, подобный алгоритму Дейкстры, в коммуникационных сетях?

9) Перечислите известные Вам алгоритмы обхода графов.

10) Что такое транспортная сеть? Приведите пример.

11) Какой граф называется эйлеровым? Приведите пример эйлерова графа.

12) Какой граф называется гамильтоновым? Приведите пример гамильтонова графа.

13) Какой вид отношений на графах представляет изоморфизм графов?

14) Приведите пример отношения порядка и отношения эквивалентности на графе.

15) Какие алгоритмы обхода графов Вам известны?

16) Какие виды графов Вы знаете?

17) Что понимается под степенью вершины?

18) Как определяются числа внутренней и внешней устойчивости графа?

19) Как определяются хроматическое и цикломатическое числа графа?

20) Сформулируйте транспортную задачу и связанные с ней понятия?

21) Опишите кратко алгоритм управления проектами.

22) Приведите пример построения разреза графа.

23) Приведите пример дерева с корнем.

Практическая работа № 4. Элементы теории множеств и алгебры логики


Цель работы: применение знаний теории множеств и алгебры логики для решения практической задачи.


4.1 Указание к выполнению


Данная практическая работа сочетает в себе использование элементов теории множеств и алгебры логики. Все теоретические сведения, необходимые для выполнения данной работы, изложены в лекциях и в уже изданных методических пособиях [23], [25]. Выполнение данной работы рекомендуется выполнять по образцу, рассмотренному далее.


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


1. Составить множества из букв Ф.И.О..

2. Представить полученные множества на кругах Эйлера.

3. Представить буквы Ф.И.О. в двоичной системе.

4. Представить диаграмму Венна. СНДФ.

5. Перевести числа даты рождения в двоичную систему счисления.

Примечание: желательно реализовать основные вычисления в приложении на Delphi.


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


Пример 1:

1 Множества из букв Ф.И.О.

МОРОЗОВ ОЛЕГ ЕВГЕНЬЕВИЧ

Ф = {М, О, Р, З, В};

И = {О, Л, Е, Г};

О = {Е, В, Г, Н, Ь, И, Ч};

2 Круги Эйлера и диаграммы Венна


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

Рисунок 4.1 – Круги Эйлера


Таблица 4.1 – Буквы алфавита в двоичной системе

А 00001 Л 01011 Ц 10110
Б 00010 М 01100 Ч 10111
В 00011 Н 01101 Ш 11000
Г 00100 О 01110 Щ 11001
Д 00101 П 01111 Ъ 11010
Е 00110 Р 10000 Ы 11011
Ж 00111 С 10001 Ь 11100
З 01000 Т 10010 Э 11101
И 01001 У 10011 Ю 11110
К 01010 Ф 10100 Я 11111


Х 10101


Таблица 4.2 – Буквы Ф.И.О. в двоичной системе


М О Р З В О Л Е Г Е В Г Н Ь И Ч

0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 3
F1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1 0 8
F2 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 10
F3 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 8

0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 6


Таблица 4.3 – СНДФ из букв Ф.И.О.

x1 x2 x3 x4 F1 F2 F3
0 0 0 0 1 1 0
0 0 0 1 1 1 1
0 0 1 0 0 0 0
0 0 1 1 1 0 0
0 1 0 0 0 0 1
0 1 0 1 1 1 1
0 1 1 0 1 0 1
0 1 1 1 0 1 1
1 0 0 0 0 1 0
1 0 0 1 0 1 1
1 0 1 0 0 0 1
1 0 1 1 0 1 0
1 1 0 0 1 1 0
1 1 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 1 1

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

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

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

F1


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

F2

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

F3

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

Рисунок 4.2 – Диаграммы Венна для функций F1, F2, F3


3 Перевод даты рождения в двоичную систему

1982.0212

1982 2









991 0 2









495 1 2









247 1 2









123 1 2









61 1 2









30 1 2









15 0 2









7 1 2









3 1 2










1 1


0.0212
0.3568
1.4272

2
2
2
0 0.0424 0 0.7136 0 0.8544

2
2
2
0 0.0848 1 1.4272 1 1.7088

2



0 0.1696




2



0 0.3392




2



0 0.6784




2



1 1.3568




(1982.0212) 10=(11110111110.0000010101) 2


Пример 2: автор – Якухин Дмитрий

var

k:byte;

Form1: TForm1;

type R = set of 'A'..'Я';

implementation

{$R *.dfm}

procedure SNDF (y:byte; t:string);

var i:byte;

begin

for i:=1 to 5 do begin

Form1. StringGrid1. Cells [y, i]:=t[i];

end;

for i:=1 to 3 do begin

Form1. StringGrid2. Cells [i+4, y]:=t [i+1];

end;

end;

procedure Perebor (T:R; S:TMemo);

begin

if ('А' in T) then begin S. Lines. Add ('А = '+' 00001'); inc(k); SNDF (k, '00001'); Form1. StringGrid1. Cells [k, 0]:='А'; end;

if ('Б' in T) then begin S. Lines. Add ('Б = '+' 00010'); inc(k); SNDF (k, '00010'); Form1. StringGrid1. Cells [k, 0]:='Б'; end;

if ('В' in T) then begin S. Lines. Add ('В = '+' 00011'); inc(k); SNDF (k, '00011'); Form1. StringGrid1. Cells [k, 0]:='В'; end;

if ('Г' in T) then begin S. Lines. Add ('Г = '+' 00100'); inc(k); SNDF (k, '00100'); Form1. StringGrid1. Cells [k, 0]:='Г'; end;

if ('Д' in T) then begin S. Lines. Add ('Д = '+' 00101'); inc(k); SNDF (k, '00101'); Form1. StringGrid1. Cells [k, 0]:='Д'; end;

if ('Е' in T) then begin S. Lines. Add ('Е = '+' 00110'); inc(k); SNDF (k, '00110'); Form1. StringGrid1. Cells [k, 0]:='Е'; end;

if ('Ж' in T) then begin S. Lines. Add ('Ж = '+' 00111'); inc(k); SNDF (k, '00111'); Form1. StringGrid1. Cells [k, 0]:='Ж'; end;

if ('З' in T) then begin S. Lines. Add ('З = '+' 01000'); inc(k); SNDF (k, '01000'); Form1. StringGrid1. Cells [k, 0]:='З'; end;

if ('И' in T) then begin S. Lines. Add ('И = '+' 01001'); inc(k); SNDF (k, '01001'); Form1. StringGrid1. Cells [k, 0]:='И'; end;

if ('К' in T) then begin S. Lines. Add ('К = '+' 01010'); inc(k); SNDF (k, '01010'); Form1. StringGrid1. Cells [k, 0]:='К'; end;

if ('Л' in T) then begin S. Lines. Add ('Л = '+' 01011'); inc(k); SNDF (k, '01011'); Form1. StringGrid1. Cells [k, 0]:='Л'; end;

if ('М' in T) then begin S. Lines. Add ('М = '+' 01100'); inc(k); SNDF (k, '01100'); Form1. StringGrid1. Cells [k, 0]:='М'; end;

if ('Н' in T) then begin S. Lines. Add ('Н = '+' 01101'); inc(k); SNDF (k, '01101'); Form1. StringGrid1. Cells [k, 0]:='Н'; end;

if ('О' in T) then begin S. Lines. Add ('О = '+' 01110'); inc(k); SNDF (k, '01110'); Form1. StringGrid1. Cells [k, 0]:='О'; end;

if ('П' in T) then begin S. Lines. Add ('П = '+' 01111'); inc(k); SNDF (k, '01111'); Form1. StringGrid1. Cells [k, 0]:='П'; end;

if ('Р' in T) then begin S. Lines. Add ('Р = '+' 10000'); inc(k); SNDF (k, '10000'); Form1. StringGrid1. Cells [k, 0]:='Р'; end;

if ('С' in T) then begin S. Lines. Add ('С = '+' 10001'); inc(k); SNDF (k, '10001'); Form1. StringGrid1. Cells [k, 0]:='С'; end;

if ('Т' in T) then begin S. Lines. Add ('Т = '+' 10010'); inc(k); SNDF (k, '10010'); Form1. StringGrid1. Cells [k, 0]:='Т'; end;

if ('У' in T) then begin S. Lines. Add ('У = '+' 10011'); inc(k); SNDF (k, '10011'); Form1. StringGrid1. Cells [k, 0]:='У'; end;

if ('Ф' in T) then begin S. Lines. Add ('Ф = '+' 10100'); inc(k); SNDF (k, '10100'); Form1. StringGrid1. Cells [k, 0]:='Ф'; end;

if ('Х' in T) then begin S. Lines. Add ('Х = '+' 10101'); inc(k); SNDF (k,

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

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

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

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