Метод Форда-Беллмана нахождения расстояния от источника до всех вершин графа
Метод Форда-Беллмана для нахождения расстояния от источника до всех вершин графа. Алгоритмы поиска расстояний и отыскания кратчайших путей в графах. Блочно-диагональный вид и матрица в исследовании системы булевых функций и самодвойственной функции.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 10.10.2011 |
| Размер файла | 192,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
(ГОУВПО ВГТУ)
Кафедра компьютерных интеллектуальных технологий проектирования
Факультет вечернего и заочного обучения
КУРСОВАЯ РАБОТА
тема: Метод Форда-Беллмана нахождения расстояния от источника до всех вершин графа
по дисциплине: Дискретная математика
Воронеж 2010 г.
Введение
Дискремтная матемамтика -- область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях.
Дискретная математика - одна из важнейших составляющих современной математики. С одной стороны, она включает фундаментальные основы математики - теорию множеств, математическую логику, теорию алгоритмов; с другой стороны, является основным математическим аппаратом информатики и вычислительной техники и потому служит базой для многочисленных приложений в экономике, технике, социальной сфере.
В отличие от традиционной математики (математического анализа, линейной алгебры и др.), методы и конструкции которой имеют в основном числовую интерпретацию, дискретная математика имеет дело с объектами нечисловой природы: множествами, логическими высказываниями, алгоритмами, графами. Благодаря этому обстоятельству дискретная математика впервые позволила распространить математические методы на сферы и задачи, которые ранее были далеки от математики. Примером могут служить методы моделирования различных социальных и экономических процессов. Знание теории множеств, алгебры, математической логики и теории графов совершенно необходимо для четкой формулировки понятий и постановок различных прикладных задач, их формализации и компьютеризации, а также для усвоения и разработки современных информационных технологий. Понятия и методы теории алгоритмов и алгебры логики лежат в основе современной теории и практики программирования. Дискретная математика предусматривает изучение: языка дискретной математики, таких ее основных понятий, как множества, функции, отношения; основ комбинаторики, элементов общей алгебры; введения в математическую логику; теории графов.
1. Метод Форда-Беллмана нахождения расстояния от источника до всех вершин графа
Мы взбираемся на вершину, откуда можем бросить гордый взгляд назад и оценить пройденный путь.
П.Буль.
Начальные понятия
Будем рассматривать ориентированные графы G = ?V, E?, дугам которых приписаны веса. Это означает, что каждой дуге ?u, v? ?E поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.
Полагаем, кроме того, a (u, v) = г , если u -a v.
Если последовательность вершин v0, v1,..., vp определяет путь в G, то его длина определяется как сумма.
.
(Отметим, что если в произвольном графе мы примем вес каждой дуги равным единице, то мы получим обычное определение длины пути как числа дуг; длина пути равна 0 при p = 0).
Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, t ?V. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = г . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v1,..., vp не будет повторов.
С другой стороны, если в графе существует контур отрицательной длины, то расстояние между некоторыми парами вершин становится неопределенным, потому что, обходя этот контур достаточное число раз, мы можем показать путь между этими вершинами с длиной, меньшей произвольного вещественного числа. В таком случае, можно было бы говорить о длине кратчайшего элементарного пути, однако задача, поставленная таким образом, вероятно будет значительно более сложной, так как, в частности, она содержит в себе задачу существования гамильтонова пути.
Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем затем кратчайшие пути между городами. Вес дуги также может соответствовать стоимости (или времени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну ситуацию получаем, когда вес дуги ?u, v? равен вероятности p(u, v) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляющих его дуг. Задачу нахождения наиболее надежного пути легко можно свести к задаче о кратчайшем пути, заменяя веса p(u, v) на a (u, v) = - log p(u, v).
Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этого достаточно отметить, что для произвольных s, t ? V (s ¦ t) существует вершина v, такая что
d (s, t) = d (s, v) + a (v, t).
Действительно, таким свойством обладает предпоследняя вершина произвольного кратчайшего пути из s в t.
Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a (u, v), и т.д.
Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u, ... не содержит повторений и оканчивается вершиной s.
Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.
Алгоритм нахождения кратчайшего пути
Данные: Расстояния D[v] от фиксированной вершины s до всех остальных вершин v О V, фиксированная вершина t, матрица весов ребер, A[u, v], u, v ?V.
Результаты: СТЕК содержит последовательность вершин, определяющую кратчайший путь из s в t.
begin
CTEK := Ж ; CTEK Ь t; v:= t;
while v ¦ s do
begin
u := вершина, для которой D[v] = D[u] + A[u, v];
CTEK Ь u;
v:= u
end
end.
Пусть <V, E>---ориентированный граф, | V|--= n, | E| = m. Если выбор вершины u происходит в результате просмотра всех вершин, то сложность нашего алгоритма - O(n2). Если мы просматриваем только список ПРЕДШ[v], содержащий все вершины u, такие что u ??? v, то в этом случае сложность будет O(m).
Отметим, что в случае положительных весов ребер задача о кратчайшем пути в неориентированном графе легко сводится к аналогичной задаче для некоторого ориентированного графа. С этой целью достаточно заменить каждое ребро {u, v}двумя дугами ? u, v?и ?v, u? , каждая с таким же весом, что и {u, v}. Однако в случае неположительных весов это приводит к возникновению контуров с неположительной длиной.
Далее будем всегда предполагать, что G = ? V, E? является ориентированным графом, ?V? = n, ?E? = m. В целях упрощения изложения и избежание вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых большинство вершин изолированные.
Будем также предполагать, что веса дуг запоминаются в массиве A[u, v], u, v? V (A[u, v] содержит вес a (u, v)).
Кратчайшие пути от фиксированной вершины
Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A[u, v], u, v ? V, вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин v ? V. Каждый раз, когда мы устанавливаем, что
D[u] + A[u, v] < D[v],
оценку D[v] улучшаем:
D[v] = D[u] + A[u, v].
Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно.
Легко можно показать, что значение каждой из переменных D[v] равно тогда d (s, v) - расстоянию от s до v.
Заметим, что для того чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа.
Не известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных.
Описанная общая схема является неполной, так как она не определяет очередности, в которой выбираются вершины u и v для проверки условия минимальности расстояния. Эта очередности, как будет показано ниже, очень сильно влияет на эффективность алгоритма. Опишем теперь более детально методы нахождения расстояния от фиксированной вершины, называемой источником, его всегда будем обозначать через s, до всех остальных вершин графа.
Сначала представим алгоритм для общего случая, в котором предполагается только отсутствие контуров с отрицательной длиной. С эти алгоритмом обычно связывают имена Л.Р. Форда и Р.Е. Беллмана.
Алгоритм нахождения расстояния от источника до всех вершин - метод Форда - Беллмана
Данные: Ориентированный граф ?V, E? с n вершинами с выделенным источником s ? V, матрица дуг A[u, v], u, v ?V (граф не содержит контуров отрицательной длины).
Результаты: Расстояния от источника до всех вершин графа: D[v]=d(s, v), vО V.
1 begin
2 for v О V do D [v] := A[s, v]; D [s]:= 0;
3 for k := 1 to n - 2 do
4 for v О--V \ {s} do
5 for u О V do D [v] := min(D[v], D[u] + A [u, v]);
6 end.
Докажем правильность этого алгоритма. Для этого обозначим через d(m)(v) длину кратчайшего из путей из s в v, содержащих не более m дуг (d(m)(v) = г , если не существует ни одного такого пути). Тогда имеем
d(m+1)(v) = min{d(m)(u) + a[u, v]: u ? V}, v ? V. (1)
В самом деле, для каждого u? V очевидно имеем d(m+1)(v) ?d(m)(u) + a[u, v], причем равенство появляется, когда u является предпоследней вершиной произвольного кратчайшего пути из s в v.
Покажем теперь, что если при входе в очередную итерацию цикла 3
d (s, v) ? D[v] ? d(m)(v) для всех v ? V, (2)
то по окончании этой итерации
d (s, v) ? D[v] ? d(m+1)(v) для всех v ? V. (3)
Действительно, предполагая выполнение условия (2) и анализируя действие оператора в строке 5, мы видим, что по окончании итерации цикла 3 имеем
d (s, v) ? D[v] ? min{d(m)(u) + a[u, v]: u ? V},
что, принимая во внимание равенство (1) дает условие (3).
Отметим, что при входе в цикл 3 имеем D[v] = d 1 (v), v ? V, следовательно, после выполнения n - 2 итераций этого цикла будут выполняться неравенства d (s, v) ? D[v] ?d(n-1)(v), v ? V.
Теперь достаточно показать, что d(n-1)(v) = d (s, v). Это справедливо, поскольку каждый путь более чем с n - 1 дугами содержит контур, устранение которого не увеличивает длины пути (ведь мы предполагаем отсутствие контуров отрицательной длины). Тем самым закончено доказательство корректности алгоритма.
Очевидно, что временная сложность алгоритма есть O(n3). Мы можем, конечно, закончить вычисления, когда выполнение цикла 4 не вызывает изменения ни одной из переменных D[v], v ? V. Это может наступить для k < n - 2, однако такая модификация алгоритма не изменяет существенным образом его сложности. Для редких графов (m << n2) удобнее представлять граф списками инцидентности ПРЕДШ[v], v ? V. Заменяя строку 5 на
for u ? ПРЕДШ[v] do D [v] :=min(D[v], D[u] + A [u, v]),
получаем алгоритм со сложностью O(nm).
Работа алгоритма Форда - Беллмана проиллюстрирована на следующем рисунке (V = {1, ..., 5}, веса дуг даны числами в скобках, циклы 4 и 5 выполняются в порядке возрастания номеров вершин).
Большинство алгоритмов поиска расстояний между двумя фиксированными вершинами s и t включают в себя следующие действия: по данной матрице весов дуг A*u,v] (u,vеV) вычисляют некоторые верхние ограничения D*v+ на расстояние от s до всех вершин v. На каждом шаге, если D*v++A*u,v+<D*v+ оценку D*v+ улучшают: D*v+=D*u++A*u,v+. Процесс прекращается, когда дальнейшее улучшение ни одного из ограничений невозможно. 4
Алгоритм Форда-Беллмана позволяет найти расстояние от источника до всех вершин D[v]=d(s,v), vеV ориентированного графа при условии, что граф не содержит контуров отрицательной длины (n - количество вершин в графе). Исходными данными для этого алгоритма являются матрица весов дуг A[u,v].
На рисунке 1 приведен: (а) граф; (б) соответствующая ему матрица весов дуг; (в) результаты работы алгоритма Форда-Беллмана.
а) б) в)
Рис. 1: Пример выполнения алгоритма Форда-Беллмана.
Приведенный алгоритм отыскания кратчайших путей в графах с отрицательными длинами дуг, принадлежащий Форду, Муру и Беллману, может служить одним из возможных способов обнаружения контуров отрицательной длины (или циклов в неориентированном графе).
2. Практическая часть
Задание № 1
Упростите .
Решение:
Задание № 2
Определите свойства отношения.
R={(x,y)| x,yR и 2x 3y}.
Решение:
Так как
а) ,
б) . R не рефлексивно.
Рассмотрим элемент (4,2). , но и не , следовательно, R - несимметричное отношение.
, R - не транзитивно.
Задание № 3
Для отношения, заданного матрицей, определить является ли оно отношением эквивалентности. Если является, то определить классы эквивалентности.
|
R |
а |
b |
с |
d |
е |
f |
|
|
А |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
B |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
С |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
D |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
Е |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
F |
0 |
0 |
1 |
0 |
0 |
1 |
Решение:
Переставляя строки и столбцы, попробуем привести матрицу отношения R к блочно-диагональному виду. Поменяем местами столбцы a, d и строки a, d, получим:
|
R |
а |
b |
с |
d |
е |
f |
R |
d |
b |
с |
а |
е |
f |
R |
d |
b |
с |
а |
е |
f |
|||
|
А |
1 |
а |
1 |
d |
1 |
1 |
|||||||||||||||||
|
B |
1 |
1 |
b |
1 |
1 |
b |
1 |
1 |
|||||||||||||||
|
С |
1 |
1 |
с |
1 |
1 |
с |
1 |
1 |
|||||||||||||||
|
D |
1 |
1 |
d |
1 |
1 |
а |
1 |
||||||||||||||||
|
Е |
1 |
е |
1 |
е |
1 |
||||||||||||||||||
|
F |
1 |
1 |
f |
1 |
1 |
f |
1 |
1 |
Поменяем местами столбцы c, e и строки c, e, получим
|
R |
d |
b |
с |
а |
е |
f |
R |
d |
b |
е |
а |
с |
f |
R |
d |
b |
е |
а |
с |
f |
|||
|
D |
1 |
1 |
d |
1 |
1 |
d |
1 |
1 |
|||||||||||||||
|
B |
1 |
1 |
b |
1 |
1 |
b |
1 |
1 |
|||||||||||||||
|
С |
1 |
1 |
с |
1 |
1 |
е |
1 |
||||||||||||||||
|
А |
1 |
а |
1 |
а |
1 |
||||||||||||||||||
|
Е |
1 |
е |
1 |
с |
1 |
1 |
|||||||||||||||||
|
F |
1 |
1 |
f |
1 |
1 |
f |
1 |
1 |
Матрицу отношения привели к блочно-диагональному виду, значит R является эквивалентностью, и по полученной матрице можно определить классы эквивалентности К,К,К, К.
Таким образом К= {d, b}, К= {e}, К= {a}, К={c, f}.
Задание № 4
Для графа построить матрицу смежности, матрицу инцидентности; получить матрицу достижимостей; найти сильные компоненты и построить граф конденсации.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Решение:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Матрица смежности:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||||
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|||
|
2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|||
|
3 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|||
|
4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
|
5 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|||
|
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|||
|
7 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|||
|
8 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Матрица инцидентности:
|
(2,1) |
(1,3) |
(2,3) |
(3,6) |
(4,2) |
(5,2) |
(5,4) |
(5,6) |
(5,7) |
(5,8) |
(6,8) |
(7,4) |
(8,7) |
|||||
|
1 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||||
|
2 |
1 |
0 |
1 |
0 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||||
|
3 |
0 |
-1 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||||
|
В= |
4 |
0 |
0 |
0 |
0 |
1 |
0 |
-1 |
0 |
0 |
0 |
0 |
-1 |
0 |
|||
|
5 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
||||
|
6 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
0 |
||||
|
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
-1 |
||||
|
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
0 |
1 |
Матрица достижимостей:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||||
|
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|||
|
2 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|||
|
3 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|||
|
4 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|||
|
5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|||
|
6 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|||
|
7 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|||
|
8 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
Граф конденсации:
Cк1: {1;2;3;4;6;7;8}
Cк2: {5}
Граф конденсации
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Задание № 5
Для графа построить, если это возможно, его укладку на плоскости.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Решение:
Уложим сначала цикл С =(1, 2, 4, 5, 1), который разбивает плоскость на две грани Г1 в Г2. На рисунке изображены граф G'=С и сегменты S1, S2, S3 относительно G' с контактными вершинами, обведенными кружками. Так как Г(Si)={Г1, Г2} (i=1, 2, 3), то любую -цепь произвольного сегмента можно укладывать в любую допустимую для него грань. Поместим, например, -цепь L = (2, 6, 5) в Г1. Возникает новый граф G' и его сегменты. При этом Г(S1) = {Г3}, Г(S2) = {Г1, Г2}, Г(S3) = {Г1, Г2, Г3}. Укладываем цепь L = (6, 1) в Г3. Тогда Г(S1) = {Г1, Г2}, Г(S2) = {Г1, Г2}. Далее, уложим -цепь L = (2, 3, 5) сегмента S1 в Г1 . В результате имеем Г(S1) = {Г5}, Г(S2) = {Г1, Г2, Г3}. Наконец, уложив ребро (3,4) в Г5, а ребро (2,5) - например, а Г1, получаем укладку графа G на плоскости
граф расстояние булевый самодвойственный
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Задание № 6
Упростить ПФ, используя равносильные преобразования.
.
Решение:
Задание № 7
Составить таблицу истинности ПФ и определить тип ПФ.
.
Решение:
|
X |
Y |
Z |
||||||
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
|
|
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
|
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
Как видно из таблицы истинности, данная ПФ является выполнимой, так как на некоторых наборах значений переменных она принимает значение 1.
Задание № 8
Привести ПФ к совершенным нормальным формам.
.
Решение:
Приведем ПФ к совершенным нормальным формам.
Для приведения к совершенным нормальным формам воспользуемся алгоритмами «(табличный способ приведения к СДНФ)» и «(табличный способ приведения к СКНФ)» Построим таблицу истинности и на ее основе составим СДНФ и СКНФ.
|
X |
Y |
||||||||
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1) Для нахождения СКНФ нужно из таблицы истинности выделить лишь те строки, результат которых равен 0.
|
X |
Y |
||||||||
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
Далее, для каждой строки выписываем дизъюнкцию всех переменных по следующему алгоритму: если значение переменной в данной строке равно 0, то в дизъюнкцию записываем саму переменную, а если равно 1, то - отрицание этой переменной. После этого все дизъюнкции связываем в конъюнкцию. В результате, совершенная конъюнктивно - нормальная форма (СКНФ) нашей функции равна:
2) Для нахождения СДНФ нужно из таблицы истинности выделить лишь те строки, результат которых равен 1.
|
X |
Y |
||||||||
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
Далее, для каждой строки выписываем конъюнкцию всех переменных по следующему алгоритму: если значение переменной в данной строке равно 1, то в конъюнкцию записываем саму переменную, а если равно 0, то - отрицание этой переменной. После этого все конъюнкции связываем в дизъюнкцию. В результате, совершенная дизъюнктивно-нормальная форма (СДНФ) нашей функции равна:
Задание № 9
Исследовать систему булевых функций на полноту.
Решение:
Для проверки полноты системы булевых функций будем использовать критерий полноты - теорему Поста. Составим таблицу Поста.
|
f |
||||||
|
+ |
+ |
+ |
- |
- |
||
|
- |
- |
- |
+ |
+ |
следовательно в то время как .
, следовательно в то время как так как
Для проверки монотонности воспользуемся таблицей истинности.
|
X |
Y |
|||
|
0 |
0 |
0 |
1 |
|
|
0 |
1 |
0 |
1 |
|
|
1 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
Анализ показывает, что является монотонной функцией, a таковой не является, так как
Для определения линейности функции построим многочлен Жегалкина.
Таким образом, - линейная функция, а - нет.
Определим являются ли исследуемые функции самодвойственными. Так как , то - самодвойственная функция. В то время, как , и поэтому .
Для полноты системы необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один “-“. Построенная таблица доказывает, что система является полной.
Заключение
В отличие от традиционной математики (математического анализа, линейной алгебры и др.), методы и конструкции которой имеют в основном числовую интерпретацию, дискретная математика имеет дело с объектами нечисловой природы: множествами, логическими высказываниями, алгоритмами, графами. Благодаря этому обстоятельству дискретная математика впервые позволила распространить математические методы на сферы и задачи, которые ранее были далеки от математики. Дискретная математика предусматривает изучение: языка дискретной математики, таких ее основных понятий, как множества, функции, отношения; основ комбинаторики, элементов общей алгебры; введения в математическую логику; теории графов.
Одной из задач, рассматриваемых в дискретной математике, а конкретно в теории графов - это нахождение кратчайших путей в графе. Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга - некоторому пути, длина которого представлена весом дуги. В теоретической части данной курсовой рассматривается один из алгоритмов расчета кратчайшего пути, принадлежащий Форду, Муру и Беллману.
Во второй, практической части рассматривается решение задач на множества, их свойства, определения отношения эквивалентности матрицы, построение матриц смежности, инцидентности, а также получение матрицы достижимости для графа, укладка графа на плоскости, построение таблиц истинности ПФ, нахождение СКНФ и СДНФ, исследование систем булевых функций на полноту.
На сегодняшний день дискретная математика является важным звеном математического образования.
Список использованной литературы
1. Андерсон Джеймс Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. -- М.: «Вильямс», 2006. -- С. 960. -- ISBN 0-13-086998-8
2. Белоусов А.И., Ткачев С.Б. Дискретная математика. Серия: Математика в техническом университете. Изд-во: МГТУ им. Н.Э. Баумана, 2001.- 744 с. ISBN 5-7038-1769-2, 5-7038-1270-4
3. Виленкин Н.Я. Комбинаторика. -- М.: 1969.
4. Ерусалимский Я.М. Дискретная математика. -- М.: 2000.
5. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. Издательство: Физматлит, 2007. - 408 с. ISBN 978-5-9221-0787-7
6. Капитонова Ю.В., Кривой С.Л., Летичевский А.А., Луцкий Г.М. Лекции по дискретной математике. -- СПб.: БХВ-Петербург, 2004. -- С. 624. -- ISBN 5-94157-546-7
7. Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. -- М.: 1963. -- С. 486.
8. МЭС (1995), -- М., БРЭ.
9. Новиков Ф.А. Дискретная математика для программистов. -- 2-е изд. -- СПб.: «Питер», 2005. -- С. 364. -- ISBN 5-94723-741-5
10. Редькин Н.П. Дискретная математика. Издательство: Лань, 2006. - 96 с. ISBN 5-8114-0522-7
11. Романовский И.В. Дискретный анализ. -- 3-е изд. -- СПб.: Невский Диалект; БХВ-Петербург, 2003. -- С. 320.
12. Яблонский С.В. Введение в дискретную математику. -- М.: Наука, 1979. -- С. 272.
Размещено на Allbest.ru
Подобные документы
Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
реферат [108,4 K], добавлен 01.12.2008Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
презентация [36,1 K], добавлен 16.09.2013Алгоритм перехода к графическому представлению для неориентированного графа. Количество вершин неориентированного графа. Чтение из матрицы смежностей. Связи между вершинами в матрице. Задание координат вершин в зависимости от количества секторов.
лабораторная работа [34,0 K], добавлен 29.04.2011Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа [109,1 K], добавлен 22.01.2016Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Понятие "граф" и его матричное представление. Свойства матриц смежности и инцидентности. Свойства маршрутов, цепей и циклов. Задача нахождения центральных вершин графа, его метрические характеристики. Приложение теории графов в областях науки и техники.
курсовая работа [271,1 K], добавлен 09.05.2015Понятия и определения орграфа и неориентированного графа, методы решения. Неориентированные и ориентированные деревья. Подробное описание алгоритмов нахождения кратчайших путей в графе: мультиграф, псевдограф. Матрица достижимостей и контрдостижимостей.
курсовая работа [251,0 K], добавлен 16.01.2012Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009
