Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
МЕТОДИЧНІ ВКАЗІВКИ
ДО РОЗРАХУНКОВОЇ РОБОТИ
З ДИСЦИПЛІНІ
"ДИСКРЕТНА МАТЕМАТИКА"
для студентів спеціальностей
7.091501: "Комп'ютерні системи та мережі"
7.091502: ”Системне програмування”
Затверджено
на засіданні кафедри КІ
Протокол № 1 від
30.08.2010
Рекомендовано до видання
методичною комісією
спеціальностей 7.091501 і 7.091502
Протокол № 1 від
Донецьк
МЕТОДИЧНІ ВКАЗІВКИ ДО РОЗРАХУНКОВОЇ РОБОТИ З ДИСЦИПЛІНІ «ДИСКРЕТНА МАТЕМАТИКА»(для студентів очної, заочної та очно – заочної форми навчання).
Ціллю розрахункової роботи з дисципліни “Дискретна математика” є вдосконалення знань студентів із одного з розділів дискретної математики – теорії графів.
Укладачі: А.Ю. Іванов, ст. викл., О.Ю.Череднікова, ас.
Рецензент: Kраснокутський В.О., к.т.н., доц.
Ладиженський Ю.В., к.т.н., доц.
Література
1.Форд Л., Потоки в мережах - М.:Мир,1966
2.Цой С., Цхай С.М. Прикладна теорія графів - Алма-Ата. 1971
Згідно з варіантом у журналі старости виконати ручний розрахунок пунктів для відповідного графу:
- радіус
- діаметр
- хроматичне число
- хроматичний клас
- цикломатичне число ( згідно з формулою та за допомогою побудови остова)
Звіт виконується в зошиті і здається на перевірку до складання заліку.
Варіанти завдань
1)
2)
3)
4)
5)
6)
7)
8)
10)
11)
12)
14)
16)
17)
18)
19)
20)
21)
22)
23)
24)
25)
26)
27)
28)
29)
30)
31)
32)
33)
34)
Приклад виконання.
1. Засоби представлення графу.
Матриця суміжностей:
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
M |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
U |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
H |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
P |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
S |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
T |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
R |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
Матриця інцидентностей.
|
DM |
DU |
DP |
MU |
MS |
MR |
MH |
UP |
US |
ST |
PH |
PR |
TR |
TH |
|
|
D |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
M |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
U |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
H |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
P |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
S |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
T |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
|
R |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
Список суміжності.
|
D |
M |
P |
U |
||
|
M |
D |
U |
S |
R |
H |
|
U |
D |
M |
P |
S |
|
|
H |
M |
P |
T |
||
|
P |
D |
U |
H |
R |
|
|
S |
U |
M |
T |
||
|
T |
S |
H |
R |
||
|
R |
M |
P |
T |
2. Визначення всіх метричних характеристик графу.
Кількість верхівок: 8.
Кількість ребер: 14.
Ступені верхівок:
|
D |
M |
U |
H |
P |
S |
T |
R |
|
3 |
5 |
4 |
3 |
4 |
3 |
3 |
3 |
Дистанції між парами верхівок.
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
1 |
1 |
2 |
1 |
2 |
3 |
2 |
|
M |
1 |
0 |
1 |
1 |
2 |
1 |
2 |
1 |
|
U |
1 |
1 |
0 |
2 |
1 |
1 |
2 |
2 |
|
H |
2 |
1 |
2 |
0 |
1 |
2 |
1 |
2 |
|
P |
1 |
2 |
1 |
1 |
0 |
2 |
2 |
1 |
|
S |
2 |
1 |
1 |
2 |
2 |
0 |
1 |
2 |
|
T |
3 |
2 |
2 |
1 |
2 |
1 |
0 |
1 |
|
R |
2 |
1 |
2 |
2 |
1 |
2 |
1 |
0 |
Радіуси верхівок.
|
D |
M |
U |
H |
P |
S |
T |
R |
|
3 |
2 |
2 |
2 |
2 |
2 |
3 |
2 |
Діаметр графу: 3.
Радіус графу: 2.
Хроматичне число графу.
Хроматичне число графу дорівнює 3.
Хроматичний клас графу.
Хроматичний клас графу дорівнює 5.
3. Алгоритм Флойду для графу.
Первинна матриця відстаней матриця шляху
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
10 |
7 |
∞ |
7 |
∞ |
∞ |
∞ |
|
M |
10 |
0 |
7 |
9 |
∞ |
2 |
∞ |
6 |
|
U |
7 |
7 |
0 |
∞ |
4 |
9 |
∞ |
∞ |
|
H |
∞ |
9 |
∞ |
0 |
5 |
∞ |
10 |
∞ |
|
P |
7 |
∞ |
4 |
5 |
0 |
∞ |
∞ |
3 |
|
S |
∞ |
2 |
9 |
∞ |
∞ |
0 |
8 |
∞ |
|
T |
∞ |
∞ |
∞ |
10 |
∞ |
8 |
0 |
5 |
|
R |
∞ |
6 |
∞ |
∞ |
3 |
∞ |
5 |
0 |
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
M |
U |
0 |
P |
0 |
0 |
0 |
|
M |
D |
0 |
U |
H |
0 |
S |
0 |
R |
|
U |
D |
M |
0 |
0 |
P |
S |
0 |
0 |
|
H |
0 |
M |
0 |
0 |
P |
0 |
T |
0 |
|
P |
D |
0 |
U |
H |
0 |
0 |
0 |
R |
|
S |
0 |
M |
U |
0 |
0 |
0 |
T |
0 |
|
T |
0 |
0 |
0 |
H |
0 |
S |
0 |
R |
|
R |
0 |
M |
0 |
0 |
P |
0 |
T |
0 |
Робота алгоритму.
Через верхівку D:
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
10 |
7 |
∞ |
7 |
∞ |
∞ |
∞ |
|
M |
10 |
0 |
7 |
9 |
17 |
2 |
∞ |
6 |
|
U |
7 |
7 |
0 |
∞ |
4 |
9 |
∞ |
∞ |
|
H |
∞ |
9 |
∞ |
0 |
5 |
∞ |
10 |
∞ |
|
P |
7 |
17 |
4 |
5 |
0 |
∞ |
∞ |
3 |
|
S |
∞ |
2 |
9 |
∞ |
∞ |
0 |
8 |
∞ |
|
T |
∞ |
∞ |
∞ |
10 |
∞ |
8 |
0 |
5 |
|
R |
∞ |
6 |
∞ |
∞ |
3 |
∞ |
5 |
0 |
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
M |
U |
0 |
P |
0 |
0 |
0 |
|
M |
D |
0 |
U |
H |
D |
S |
0 |
R |
|
U |
D |
M |
0 |
0 |
P |
S |
0 |
0 |
|
H |
0 |
M |
0 |
0 |
P |
0 |
T |
0 |
|
P |
D |
D |
U |
H |
0 |
0 |
0 |
R |
|
S |
0 |
M |
U |
0 |
0 |
0 |
T |
0 |
|
T |
0 |
0 |
0 |
H |
0 |
S |
0 |
R |
|
R |
0 |
M |
0 |
0 |
P |
0 |
T |
0 |
Через верхівку М:
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
10 |
7 |
19 |
7 |
12 |
∞ |
16 |
|
M |
10 |
0 |
7 |
9 |
17 |
2 |
∞ |
6 |
|
U |
7 |
7 |
0 |
16 |
4 |
9 |
∞ |
13 |
|
H |
19 |
9 |
16 |
0 |
5 |
11 |
10 |
15 |
|
P |
7 |
17 |
4 |
5 |
0 |
19 |
∞ |
3 |
|
S |
12 |
2 |
9 |
11 |
19 |
0 |
8 |
8 |
|
T |
∞ |
∞ |
∞ |
10 |
∞ |
8 |
0 |
5 |
|
R |
16 |
6 |
13 |
15 |
3 |
8 |
5 |
0 |
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
M |
U |
M |
P |
M |
0 |
M |
|
M |
D |
0 |
U |
H |
D |
S |
0 |
R |
|
U |
D |
M |
0 |
M |
P |
S |
0 |
M |
|
H |
M |
M |
M |
0 |
P |
M |
T |
M |
|
P |
D |
D |
U |
H |
0 |
M |
0 |
R |
|
S |
M |
M |
U |
M |
M |
0 |
T |
M |
|
T |
0 |
0 |
0 |
H |
0 |
S |
0 |
R |
|
R |
M |
M |
M |
M |
P |
M |
T |
0 |
Через верхівку U:
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
10 |
7 |
19 |
7 |
12 |
∞ |
16 |
|
M |
10 |
0 |
7 |
9 |
11 |
2 |
∞ |
6 |
|
U |
7 |
7 |
0 |
16 |
4 |
9 |
∞ |
13 |
|
H |
19 |
9 |
16 |
0 |
5 |
11 |
10 |
15 |
|
P |
7 |
11 |
4 |
5 |
0 |
13 |
∞ |
3 |
|
S |
12 |
2 |
9 |
11 |
13 |
0 |
8 |
8 |
|
T |
∞ |
∞ |
∞ |
10 |
∞ |
8 |
0 |
5 |
|
R |
16 |
6 |
13 |
15 |
3 |
8 |
5 |
0 |
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
M |
U |
M |
P |
M |
0 |
M |
|
M |
D |
0 |
U |
H |
U |
S |
0 |
R |
|
U |
D |
M |
0 |
M |
P |
S |
0 |
M |
|
H |
M |
M |
M |
0 |
P |
M |
T |
M |
|
P |
D |
U |
U |
H |
0 |
U |
0 |
R |
|
S |
M |
M |
U |
M |
U |
0 |
T |
M |
|
T |
0 |
0 |
0 |
H |
0 |
S |
0 |
R |
|
R |
M |
M |
M |
M |
P |
M |
T |
0 |
Через верхівку H:
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
10 |
7 |
19 |
7 |
12 |
29 |
16 |
|
M |
10 |
0 |
7 |
9 |
11 |
2 |
19 |
6 |
|
U |
7 |
7 |
0 |
16 |
4 |
9 |
26 |
13 |
|
H |
19 |
9 |
16 |
0 |
5 |
11 |
10 |
15 |
|
P |
7 |
11 |
4 |
5 |
0 |
13 |
15 |
3 |
|
S |
12 |
2 |
9 |
11 |
13 |
0 |
8 |
8 |
|
T |
29 |
19 |
26 |
10 |
15 |
8 |
0 |
5 |
|
R |
16 |
6 |
13 |
15 |
3 |
8 |
5 |
0 |
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
M |
U |
M |
P |
M |
M |
M |
|
M |
D |
0 |
U |
H |
U |
S |
H |
R |
|
U |
D |
M |
0 |
M |
P |
S |
M |
M |
|
H |
M |
M |
M |
0 |
P |
M |
T |
M |
|
P |
D |
U |
U |
H |
0 |
U |
H |
R |
|
S |
M |
M |
U |
M |
U |
0 |
T |
M |
|
T |
H |
H |
H |
H |
H |
S |
0 |
R |
|
R |
M |
M |
M |
M |
P |
M |
T |
0 |
Через верхівку P:
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
10 |
7 |
12 |
7 |
12 |
22 |
10 |
|
M |
10 |
0 |
7 |
9 |
11 |
2 |
19 |
6 |
|
U |
7 |
7 |
0 |
9 |
4 |
9 |
19 |
7 |
|
H |
12 |
9 |
9 |
0 |
5 |
11 |
10 |
8 |
|
P |
7 |
11 |
4 |
5 |
0 |
13 |
15 |
3 |
|
S |
12 |
2 |
9 |
11 |
13 |
0 |
8 |
8 |
|
T |
22 |
19 |
19 |
10 |
15 |
8 |
0 |
5 |
|
R |
10 |
6 |
7 |
8 |
3 |
8 |
5 |
0 |
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
M |
U |
P |
P |
M |
P |
P |
|
M |
D |
0 |
U |
H |
U |
S |
H |
R |
|
U |
D |
M |
0 |
P |
P |
S |
P |
P |
|
H |
P |
M |
P |
0 |
P |
M |
T |
P |
|
P |
D |
U |
U |
H |
0 |
U |
H |
R |
|
S |
M |
M |
U |
M |
U |
M |
T |
M |
|
T |
H |
H |
H |
H |
H |
S |
0 |
R |
|
R |
P |
M |
P |
P |
P |
M |
T |
0 |
Через верхівку S:
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
10 |
7 |
12 |
7 |
12 |
20 |
10 |
|
M |
10 |
0 |
7 |
9 |
11 |
2 |
10 |
6 |
|
U |
7 |
7 |
0 |
9 |
4 |
9 |
17 |
7 |
|
H |
12 |
9 |
9 |
0 |
5 |
11 |
10 |
8 |
|
P |
7 |
11 |
4 |
5 |
0 |
13 |
15 |
3 |
|
S |
12 |
2 |
9 |
11 |
13 |
0 |
8 |
8 |
|
T |
20 |
10 |
17 |
10 |
15 |
8 |
0 |
5 |
|
R |
10 |
6 |
7 |
8 |
3 |
8 |
5 |
0 |
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
M |
U |
P |
P |
M |
M |
P |
|
M |
D |
0 |
U |
H |
U |
S |
S |
R |
|
U |
D |
M |
0 |
P |
P |
S |
S |
P |
|
H |
P |
M |
P |
0 |
P |
M |
T |
P |
|
P |
D |
U |
U |
H |
0 |
U |
H |
R |
|
S |
M |
M |
U |
M |
U |
M |
T |
M |
|
T |
S |
S |
S |
H |
H |
S |
0 |
R |
|
R |
P |
M |
P |
P |
P |
M |
T |
0 |
Через верхівку T: - змін немає
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
10 |
7 |
12 |
7 |
12 |
20 |
10 |
|
M |
10 |
0 |
7 |
9 |
11 |
2 |
10 |
6 |
|
U |
7 |
7 |
0 |
9 |
4 |
9 |
17 |
7 |
|
H |
12 |
9 |
9 |
0 |
5 |
11 |
10 |
8 |
|
P |
7 |
11 |
4 |
5 |
0 |
13 |
15 |
3 |
|
S |
12 |
2 |
9 |
11 |
13 |
0 |
8 |
8 |
|
T |
20 |
10 |
17 |
10 |
15 |
8 |
0 |
5 |
|
R |
10 |
6 |
7 |
8 |
3 |
8 |
5 |
0 |
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
M |
U |
P |
P |
M |
M |
P |
|
M |
D |
0 |
U |
H |
U |
S |
S |
R |
|
U |
D |
M |
0 |
P |
P |
S |
S |
P |
|
H |
P |
M |
P |
0 |
P |
M |
T |
P |
|
P |
D |
U |
U |
H |
0 |
U |
H |
R |
|
S |
M |
M |
U |
M |
U |
M |
T |
M |
|
T |
S |
S |
S |
H |
H |
S |
0 |
R |
|
R |
P |
M |
P |
P |
P |
M |
T |
0 |
Через верхівку R Вихіднi таблицi.
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
10 |
7 |
12 |
7 |
12 |
15 |
10 |
|
M |
10 |
0 |
7 |
9 |
9 |
2 |
10 |
6 |
|
U |
7 |
7 |
0 |
9 |
4 |
9 |
12 |
7 |
|
H |
12 |
9 |
9 |
0 |
5 |
11 |
10 |
8 |
|
P |
7 |
9 |
4 |
5 |
0 |
11 |
8 |
3 |
|
S |
12 |
2 |
9 |
11 |
11 |
0 |
8 |
8 |
|
T |
15 |
10 |
12 |
10 |
8 |
8 |
0 |
5 |
|
R |
10 |
6 |
7 |
8 |
3 |
8 |
5 |
0 |
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
M |
U |
P |
P |
M |
P |
P |
|
M |
D |
0 |
U |
H |
R |
S |
S |
R |
|
U |
D |
M |
0 |
P |
P |
S |
P |
P |
|
H |
P |
M |
P |
0 |
P |
M |
T |
P |
|
P |
D |
R |
U |
H |
0 |
R |
R |
R |
|
S |
M |
M |
U |
M |
M |
M |
T |
M |
|
T |
R |
S |
R |
H |
R |
S |
0 |
R |
|
R |
P |
M |
P |
P |
P |
M |
T |
0 |
Матриця досяжності
Орієнтований граф:
|
D |
M |
U |
H |
P |
S |
T |
R |
|
|
D |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
M |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
U |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
H |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
|
P |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
S |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
T |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
R |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4. Пошук максимального потоку в мережі (метод Форда-Фалкерсона).
Етап насичення:
min=6
min=3
min=2
min=3;
Усі ребра, що входять до стоку заповнені. Тобто максимальний проток цієї мережі Ф=6+3+5=8+3+3=14.
5. Ейлерів ціпок та цикл.
В цьому графі наявні 6 верхівок з непарними ступенями, тому побудова ейлеревого ціпку та циклу неможлива.
6. Задача комівояжера. Гамільтоновий ціпок та цикл.
Показано початок побудови дерева рішення.
D
U
M
P
S
T
H
R
7
7
10
2
4
9
7
5
6
8
5
3
9
10
D
U
M
P
S
T
H
R
к
о
ж
з
г
о
з
ж
D
U
M
P
S
T
H
R
к
о
ж
з
г
з
ж
о
к
г
з
к
г
ж
D
U
M
P
S
T
H
R=Z
7
7
10
2
4
9
7
5
6
8
5
3
9
10
4(0)
5(0)
10(6)(8)
7(3)
9(3)
3(3)
D
U
M
P
S
T
H
R=Z
7
2 (2)
7(3)
6(6)
8(2)(5)
5(2)(5)
9(0)
10
4
1
2
R(32)
P(29)
H(24)
T(24)
S(16)
M(14)
D(0)
U(7)
P(7)
M(10)
P(11)
S(16)
U(11)
R(10)
H(12)
M(16)
T(15)
U(17)
S(12)
R(16)
H(19)
H(16)
R(14)
M(18)
S(20)
U(21)
T(20)
M(21)
T(22)
R(20)
H(23)
T(19)
M(20)
S(23)
M(25)
T(26)
S(18)
H(25)
R(22)
S(26)
P(21)
S(20)
H(27)
R(24)
T(26)
U(27)
H(36)
T(21)
H(29)
S(27)
T(29)
P(24)
U(23)
H(24)
P(19)
M(22)
T(28)
P(23)
T(25)
H(29)
S(22)
R(25)
H(30)
P(25)
R(24)
H(26)
H(28)
T(30)
H(31)
R(28)
M(34)
H(25)
U(32)
M(25)
R(27)
S(30)
U(28)
R(27)
S(23)
T(31)
U(32)
R(29)
P(32)
H(37)
S(46)
T(38)
S(40)
M(38)
H(38)
M(29)
M(18)
Т(24)
19
17
18
16
15
14
13
12
11
10
9
8
7
6
5
3