Дискретная математика / расчетная_робота
.doc
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
МЕТОДИЧНІ ВКАЗІВКИ
ДО РОЗРАХУНКОВОЇ РОБОТИ
З ДИСЦИПЛІНІ
"ДИСКРЕТНА МАТЕМАТИКА"
для студентів спеціальностей
7.091501: "Комп'ютерні системи та мережі"
7.091502: ”Системне програмування”
Затверджено
на засіданні кафедри КІ
Протокол № 1 від
30.08.2010
Рекомендовано до видання
методичною комісією
спеціальностей 7.091501 і 7.091502
Протокол № від
Донецьк
УДК 681.973
МЕТОДИЧНІ ВКАЗІВКИ ДО РОЗРАХУНКОВОЇ РОБОТИ З ДИСЦИПЛІНІ «ДИСКРЕТНА МАТЕМАТИКА»(для студентів очної, заочної та очно – заочної форми навчання).
Ціллю розрахункової роботи з дисципліни “Дискретна математика” є вдосконалення знань студентів із одного з розділів дискретної математики – теорії графів.
Укладачі: А.Ю. Іванов, ст. викл., О.Ю.Череднікова, ас.
Рецензент: Kраснокутський В.О., к.т.н., доц.
Ладиженський Ю.В., к.т.н., доц.
Література
1.Форд Л., Потоки в мережах - М.:Мир,1966
2.Цой С., Цхай С.М. Прикладна теорія графів - Алма-Ата. 1971
ЗАВДАННЯ ДО РОЗРАХУНКОВОЇ РОБОТИ.
Згідно з варіантом у журналі старости виконати ручний розрахунок пунктів для відповідного графу:
-
засоби представлення графу (матриці суміжності, інцидентності, список пар, список інцидентності);
-
визначення всіх чисельних метричних характеристик:
- радіус
- діаметр
- хроматичне число
- хроматичний клас
- цикломатичне число ( згідно з формулою та за допомогою побудови
максимального граф-дерева)
-
матриця досяжності (для орієнтованого графу)
-
шлях між кінцевим вершинами графу за алгоритмом Дейкстри (Флойда), дозволяється привести програму з результатом її роботи;
-
максимальний потік в мережі (метод Форда-Фалкерсона);
-
Ейлерів ланцюг або цикл;
-
Гамільтонов ланцюг або цикл.
Звіт виконується в зошиті і здається на перевірку до складання заліку (модуля).
Варіанти завдань
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)