Раздел 5. Основные прикладные задачи теории графов
Тема 16. Нахождение кратчайшего остовного дерева в графе
Нахождение кратчайшего остовного дерева в графе с помощью алгоритмов Краскала и Прима.
Тема 17. Нахождение кратчайших путей в графах
Нахождение кратчайших путей в графах. Алгоритм Дейкстры. Алгоритм Флойда.
Тема 18. Нахождение максимального потока в графе
Потоки в сетях. Задача о нахождении максимального потока в графе. Теорема и алгоритм Форда-Фалкерсона.
Тема 19. Задача о назначениях
Паросочетания в двудольных взвешенных графах. Задача о назначениях, венгерский метод решения.
Тема 20. Задача о коммивояжёре
Метод ветвей и границ. Задача о коммивояжёре. «Жадные» алгоритмы.
КОНТРОЛЬНАЯ РАБОТА
I. Докажите тождество
1.(AÇ(( 
)È( 
)))È( 
) = A.
2. (AÇC)È(BÇ 
)È( 
ÇC)È( 
) = U.
3. (A\B)È(AÇB)È( 
=U.
4. (AÇC)È( A\C)È 
= 
.
5. (AÇB)È( 
)È( È( Ç 
))=U.
6. ((A\B)È(AÇB)) Ç ( 
=Ø.
7. (AÇBÇC)È(C\А)È( ÇC) = C.
8. 
.
9. (AÇBÇC)È( ÇBÇC)È È = U.
10. 
= 
.
II. С помощью основных равносильностей (без построения таблицы истинности) привести заданную булеву функцию к виду СДНФ.
11. 
. 16. 
.
12. 
. 17. 
.
13. 
. 18. 
.
14. 
19. 
.
15. 
. 20. 
.
III. Составить таблицу истинности для заданной булевой функции. По таблице истинности составить СДНФ, СКНФ этой булевой функции и получить представление этой булевой функции в виде полинома Жегалкина и арифметического полинома.
|
|
|
21. 
. 26. 
.
22. 
. 27. 
.
23. 
. 28. 
.
24. 
. 29. 
.
25. 
. 30. 
.
IV. Построить по матрице смежности граф и его реберный граф.
31. 
. 36. 
.
32. 
. 37. 
.
33. 
. 38. 
.
34. 
. 39. 
.
35. 
. 40. 
.
V. Для изображенного графа записать последовательность степеней, построить матрицу смежности, найти центр и центр тяжести.
Дата добавления: 2018-04-05; просмотров: 251; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!