Читайте данную работу прямо на сайте или скачайте
Расчетная работ по дискретной математике
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
Кафедра №805
лМатематическая кибернетика
Вариант №19
Расчетная работ по дискретной математике
Студент:
Чумин Олег
Группа:
№18-101
Преподаватель: доцент Рыбин
Владимир
Васильевич.
- Е2001 гг.
-
Расчетная работ по дискретной математике
студента группы 18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
2
Элементы математической логики и теории булевых функций.
1.
б
в
г
полученными
д
схему
е
Формула
Решение
Придавая
{
подформуле
переменных
X, Y, Z, Y&Z,
X Y Z Y&Z
1
2
3
4
5
6
7
8
б
преобразований
1
&
тогда
V
тогда
~
тогда
⊃
тогда
2
3
4
одночленной
5
одночленной
Расчетная работ по дискретной математике
студента группы 18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
3
Находим
1-
отсутствуют
заменяем
A B A
И
И
Л
Л
т
A ~ B
A B
И
И
Л
Л
(
≡
2-
Вносим
сокращаем
≡
≡
3-
Так
конъюнкций
≡
≡
≡
6
7
8
9
10
11
местами
Расчетная работ по дискретной математике
студента группы 18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
4
≡
≡
≡
полученная
Используя
≡
≡
Находим
Для
предыдущем
≡
так
относительно
≡
≡
≡
≡
≡
& ((Z V X) V (
≡
& [(Z V X) V (
≡
& [((Z V X) V Y) & ((Z V X) V Z))] & [((Z V X) V
≡
& (Z V X V Y) & (Z V X V Z) & (Z V X V
≡
& (Z V X V Y) & (Z V X V Z) & (Z V X V
полученная
индемпотентности
≡
& (Z V X V Y) & (Z V X) & (Z V X V
теперь
≡
Находим
1-
12
13
14
15
16
17
Расчетная работ по дискретной математике
студента группы 18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
5
≡
2-
переменная
формуле
поглощения
3-
Этот
полученной
встречается
4-
относительно
≡
в
списка
≡
& X) V ((
≡
(X &
5-
переставляем
на
≡
(X &
6-
идемпотентности
≡
(X &
≡
≡
Получили
Определяем
V
1-
Используем
≡
18
Расчетная работ по дискретной математике
студента группы 18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
6
2-
3-
4-
≡
& ((Z V X) V
≡
5-
≡
6-
≡
Сокращать
полученная
в
Л
X Y Z Y&Z
1 1 1 1 1 0 0 1 0
2 1 1 0 0 1 1 1 1
3 1 0 1 0 1 0 1 1
4 0 1 1 1 0 0 1 0
5 1 0 0 0 1 1 1 1
6 0 0 1 0 1 0 1 1
7 0 1 0 0 1 1 0 0
8 0 0 0 0 1 1 0 0
г
СДНФ
Выберем
которых
X Y Z Y&Z
2 1 1 0 0 1 1 1 1
3 1 0 1 0 1 0 1 1
5 1 0 0 0 1 1 1 1
6 0 0 1 0 1 0 1 1
19
Расчетная работ по дискретной математике
студента группы 18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
7
Для
конъюнкции
<X, Y, Z>
<1, 1, 0>
<1, 0, 1>
<1, 0, 0>
<0, 0, 1>
Составляем
(X & Y &
полученная
СКНФ
Выберем
которых
X Y Z Y&Z
1 1 1 1 1 0 0 1 0
4 0 1 1 1 0 0 1 0
7 0 1 0 0 1 1 0 0
8 0 0 0 0 1 1 0 0
Для
дизъюнкции
<X, Y, Z>
<1, 1, 1>
<0, 1, 1>
<0, 1, 0>
<0, 0, 0>
Составляем
(
полученная
Сравниваем
СДНФ
(X &
преобразованиями
(X & Y &
видно
дизъюнкций
СКНФ
Расчетная работ по дискретной математике
студента группы 18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
8
(X V
преобразованиями
(
различны
д
Пользуемся
1-
Воспользуемся
списка
(X &
2-
Применяем
Записываем
(X & (
((X &
(X &
(X &
(X &
(
В
функцию
(X &
&
3-
≡
конъюнктивных
(X &
Получили
(
Дальнейшие
переменные
Определяем
(
20
Расчетная работ по дискретной математике
студента группы 18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
9
Выделим
простых
X Y Z
1 0 0 0 1 1 0 0 0 0
2 0 0 1 1 0 1 1 0 0
3 0 1 0 0 1 0 0 0 0
4 1 0 0 1 1 1 0 1 1
5 1 0 1 1 0 1 1 1 0
6 1 1 0 0 1 1 0 0 1
7 1 1 1 0 0 0 0 0 0
8 0 1 1 0 0 0 0 0 0
Из
и
импликантов
которых
столбцах
л
Определили
Строим
ДНФ
(
21
коньюнкция
простым
являющаяся
Простой
f
22
которой
Z
X
Расчетная работ по дискретной математике
студента группы 18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
10
е
1-
равносильности
(
2-
3-
≡ (
≡
4-
≡
Многочлен
YZ +
2.
Если я встречу своего приятеля
первое занятие
я пропущу первое занятие
институт
пропущу первое занятие только тогда
своим приятелем
Решение
утром
X
X
F = [(X
G = (X
H = (X
23
X
24
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
11
Составляем
X
И
И
И
И
Л
Л
Л
Л
Рассуждение
построенную
В
следующим
истинная
[(X
Но
правильность
Начальные понятия теории множеств.
3.
(A \ B) \ C = (A \ C) \ (B \ C).
25
И
л
И
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
12
Множества
помощью
Рис
A\B -
принадлежат
Рис
(A \ B) \ C -
которые
Рис
(A \ B) \ C
Рис
A \ C -
которые
Рис
B \ C -
принадлежат
A
C
B
U
A
C
B
U
A
C
B
U
A
C
B
U
U
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
13
Рис
(A \ C) \ (B \ C) Ц
которые
Рис
(A \ C) \ (B \ C)
Рис
Решение
x
x
x
x
Решение
(A \ C) \ (B \ C) A"C)B "C) A"C
" B #C) A"C
" B) A"C
"C) A"C
" B
=
= A \ B) \ C.
Решение
∉
∈
=
x A
x A
A
0,
1,
á A#B A B A"B á A B A B á A A á
= = ⋅ ⋅ = ⋅ A\B)\C A B C A B C A B C A A B C á á á á á á á á á á á á
( ); A A C A B A B C =
= = ⋅ A\C)\(B\C) A"C"B"C) A
C B#C
A C B C B"C
á á á á á
á á á á á
= ⋅ A C B C B C A C B C B C á á á á á
á á á á á á á
= A
A C B C C C B A A C B C C C B á á á á á á á á
á á á á á á á á
= − ⋅ ⋅ − + = − + ⋅ ⋅ − ⋅ + ⋅ ⋅ − ⋅ ⋅ ⋅ = A A C B C B A A B A B C A C A B C A B C C (
A A B A B C A C =
A
C
B
U
U
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
14
Решение
A# B→ XVY; A" B→ X
&Y; A→X
(A \ C) \ (B \ C) A"C) B "C)
(A \ B) \ C = A"C " B =
Составляем
X Y Z
И
И
И
Л
Л
Л
И
Л
У
высказываний
Отношения и функции.
4.
<3, 4>,
<4, 4>}
на
симметричным
Найти
Изобразите
Решение
Пользуясь
упорядоченных
-
D(
-
R(
Находим
-
= {<1, 1>,
<4, 1>, <2, 2>, <3, 2>, <4, 2>, <3, 3>, <4,
3>, <4, 4>}.
Для
ñ
26
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
15
<x, y>
<1, 1> <1,
1>
<1, 4>
<1, 1>
<1, 4>
<1, 4> <4,
4> <1, 4>
<2, 2> <2,
2>
<2, 3>
<2, 4>
<2, 2>
<2, 3>
<2, 4>
<2, 3> <3,
3>
<3, 4>
<2, 3>
<2, 4>
<2, 4> <4,
4> <2, 4>
<3, 3> <3,
3>
<3, 4>
<3, 3>
<3, 4>
<3, 4> <4,
4> <3, 4>
<4, 4> <4,
4> <4, 4>
ñïñ
Отношение
<1, 1>, <2, 2>, <3, 3>, <4, 4>,
множестве
= {<1, 1>, <2, 2>, <3, 3>, <4, 4>}
Условие
было
Отношение
например
ñ
<1, 4>, <2, 2>, <2, 3>, <2, 4>, <3, 3>, <3, 4>, <4, 4>}
но
Условие
отношения
!
Отношение
<x, y>
<1, 1>
<1, 4>
<1, 1>
<1, 4>
<1, 4>
<2, 2>
<2, 3>
<2, 4>
<2, 2>
<2, 3>
<2, 4>
<2, 3>
<3, 4>
<2, 3>
<2, 4>
<2, 4>
<3, 3>
<3, 4>
<3, 3>
<3, 4>
<3, 4>
<4, 4>
27
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
16
0
1
2
3
0 1 2 3 4 5
x
y
0
1
2
3
4
5
0 1 2 3 4 5
x
y
Действительно
ñïñ
= ñ =
необходимым
Отношение
x y y x
<1, 1>
<1, 4> <4, 1>
<2, 2>
<2, 3>
<2, 4>
<3, 3>
<3, 4>
<4, 4>
ñ
Изображаем
ñ =
5.
параллельны
(
вершины
на
эквивалентность
Решение
Докажем
ñ
ñ
ñ
28
29
30
Классы
[a]
[a]
4],
[a]
[a]
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
17
I
E
G H
B
D F
A
C
Специальные бинарные отношения.
6.
наибольший
Продолжите
Решение
наибольшего
наименьший
максимальные
Линейный
=
(, )
(, )
(, ) (, )
(, ) (, )
(, ) (, ) (, )
(, ) (, ) (, )
(, ) (, ) (, ) (, ) (, ) (, ) (,
)
(, ) (, ) (, ) (, )
(, ) (, ) (, ) (, ) (, ) (, ) (,
) (, ) (, )
I I I
H H H
G G G G I
F F F F H
E E E E G E
I
D D D D G D
I
C C C C D C
E C F C G C H C I
B B B B E B
G B I
A A A A B A
C A D A E A F A G A H A I
A B C D E F
G H I
ñ
31
Рефлексивное
множестве
32
соответствующие
Говорят
33
одно
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
18
Элементы теории графов и сетей.
7.
0 0 0 0
1 1 0 0
1 0 0 1
0 1 0 1
не
8.
ровно
Решение
34
-
-
-
-
V
V
V
V
V
V
V
V
1
2
3
4
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
19
9.
вершины
1 1 0 1 1 0 0
0 0 0 1 1 0 0
1 0 0 1 1 1 0
0 1 0 0 1 1 0
1 1 0 1 1 0 1
1 0 1 0 1 0 0
0 0 0 0 1 1 0
!
1 1 0 1 1 0 0
0 0 0 1 1 0 0
1 0 0 1 1 1 0
0 1 0 0 1 1 0
1 1 0 1 1 0 1
1 0 1 0 1 0 0
0 0 0 0 1 1 0
7
6
5
4
3
2
1
1 2 3 4 5 6 7
V
V
V
V
V
V
V
V
V V V V V V
Рисуем
вершины
путей
35 Подграфом графа
содержит
подграф
V
V
V
V
V
V
Минимальные
пути
V
!
V
!
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
20
10.
первой
заданного
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
8 11
5 1 5
6 3
2
7 4 2
4 5 3
6 2 6
7 1 2
Решение
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
8 11
5 1 5
6 3
2
7 4 2
4 5 3
6 2 6
7 1 2
8
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8
V
V
V
V
V
V
V
V
V V V V V V
V V
!
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
8 11
5 1 5
6 3
2
7 4 2
4 5 3
6 2 6
7 1 2
8
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8
j
j
j
j
j
j
j
j
i
i i i i i i i
c
c
c
c
c
c
c
c
c c c c c c
c c
10.1. k
)
i
ë
, k = 0, Е, n-1; i = 1, Е, n.
(n−
i
ë
, Vi
неV1.
(k
)
i
ë
-
) 0 (
1
i
ë i = 2, Е n; (v вv путем
приi = 2,.. n, k≥ 0 справедливо
ji
k
j
k
i
ë c , j
≤ n
i = 1, k≥ 0 справедливо
) ( ) 1 (
1 j
k
j
ë k + c , j
≤ n
36 v1x1v2x2v3x3Еxkvk+1, k
≥ 1, vi∈V, i = 1,
Е, k+1,
xj∈X, j =
1,
Е, k дугаxj
имеет(vj,
vj+1), v1 иvk+1.
Длиной
минимальнуюv
вw.
37 D = (V, X), V = {v1, v2, Е vn}, n ≥ 2 называютX определена
некотораяl: X! R, x ∈ X поставлено
некотороеl(x)
Ц
x.
38
∞ ∉
∈
=
, (, ).
(, ), (, ) ;
v v X
l v v v v X
c
i
j
i
j i j
ij
39 k
)
i
ë
- V1 вVi , k дуг
- i
= 1,
Е, n; k = 1,
2, Е
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
21
Вj ≤
k = 1
) 1(1
∞
∞
∞
8
5
7
4
6
1 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
!
∞
∞
∞
∞
∞
∞
∞
∞
ë
(1)
2
∞
∞
∞
∞
∞
∞
6
7
2 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
7
!
7
(1)
2
∞
∞
∞
∞
∞
∞
∞
ë
(1)
3
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
!
1
(1)
3
∞
∞
∞
∞
∞
∞
∞
ë
Расчетная работа по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
22
(1)
4
∞
∞
∞
∞
∞
∞
3
5
4 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
!
4
∞
∞
∞
∞
∞
∞
∞
∞
ë
(1)
5
∞
∞
∞
∞
∞
∞
1
4
5 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
!
5
∞
∞
∞
∞
∞
∞
∞
∞
ë
(1)
6
∞
∞
∞
∞
∞
11
3
2
6 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
2
!
2
(1)
6
∞
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
23
(1)
7
∞
∞
∞
∞
∞
∞
2
2
7 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
!
7
∞
∞
∞
∞
∞
∞
∞
∞
ë
(1)
8
∞
∞
∞
∞
∞
5
2
6
8 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
!
8
∞
∞
∞
∞
∞
∞
∞
∞
ë
k = 2
) 2 (
1
∞
∞
∞
8
5
7
4
6
1 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
5
13
!
5
13
min{ ; 0 min{
1
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
24
(2)
2
∞
∞
∞
∞
∞
∞
6
7
2 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
8
7
!
8
7
(2)
2
∞
∞
∞
∞
∞
∞
ë
(2)
3
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
!
1
(2)
3
∞
∞
∞
∞
∞
∞
∞
ë
(2)
4
∞
∞
∞
∞
∞
∞
3
5
4 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
5
6
!
5
6
(2)
4
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
25
(2)
5
∞
∞
∞
∞
∞
∞
1
4
5 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
!
5
∞
∞
∞
∞
∞
∞
∞
∞
ë
(2)
6
∞
∞
∞
∞
∞
11
3
2
6 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
4
2
!
4
2
(2)
6
∞
∞
∞
∞
∞
∞
ë
(2)
7
∞
∞
∞
∞
∞
∞
2
2
7 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
9
!
9
(1)
7
∞
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
26
(2)
8
∞
∞
∞
∞
∞
5
2
6
8 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
13
!
13
(2)
8
∞
∞
∞
∞
∞
∞
∞
ë
k = 3
) 3 (
1
∞
∞
∞
8
5
7
4
6
1 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
21
14
12
5
13
!
21
14
12
5
13
min{ ; 0 min{
1
∞
∞
∞
ë
(3)
2
∞
∞
∞
∞
∞
∞
6
7
2 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
8
7
!
8
7
(3)
2
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
27
(3)
3
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
!
1
(3)
3
∞
∞
∞
∞
∞
∞
∞
ë
(3)
4
∞
∞
∞
∞
∞
∞
3
5
4 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
5
6
!
5
6
(3)
4
∞
∞
∞
∞
∞
∞
ë
(3)
5
∞
∞
∞
∞
∞
∞
1
4
5 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
10
9
10
9
(3)
5
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
28
(3)
6
∞
∞
∞
∞
∞
11
3
2
6 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
24
4
2
!
24
4
2
(3)
6
∞
∞
∞
∞
∞
ë
(3)
7
∞
∞
∞
∞
∞
∞
2
2
7 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
7
9
!
7
9
(3)
7
∞
∞
∞
∞
∞
∞
ë
(3)
8
∞
∞
∞
∞
∞
5
2
6
8 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
14
13
!
14
13
(3)
8
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
29
k = 4
) 4 (
1
∞
∞
∞
8
5
7
4
6
1 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
21
12
12
5
13
!
21
12
12
5
13
min{ ; 0 min{
1
∞
∞
∞
ë
(4)
2
∞
∞
∞
∞
∞
∞
6
7
2 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
∞
8
7
!
8
7
(4)
2
∞
∞
∞
∞
∞
∞
ë
(4)
3
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
!
1
(4)
3
∞
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
30
(4)
4
∞
∞
∞
∞
∞
∞
3
5
4 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
∞
5
6
!
5
6
(4)
4
∞
∞
∞
∞
∞
∞
ë
(4)
5
∞
∞
∞
∞
∞
∞
1
4
5 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
∞
8
9
8
9
(4)
5
∞
∞
∞
∞
∞
∞
ë
(4)
6
∞
∞
∞
∞
∞
11
3
2
6 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
24
4
2
!
24
4
2
(4)
6
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
31
(4)
7
∞
∞
∞
∞
∞
∞
2
2
7 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
∞
7
9
!
7
9
(4)
7
∞
∞
∞
∞
∞
∞
ë
(4)
8
∞
∞
∞
∞
∞
5
2
6
8 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
12
11
13
!
12
11
13
(4)
8
∞
∞
∞
∞
∞
ë
k = 5
) 5 (
1
∞
∞
∞
8
5
7
4
6
1 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
19
12
12
5
13
!
19
12
12
5
13
min{ ; 0 min{
1
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
32
(5)
2
∞
∞
∞
∞
∞
∞
6
7
2 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
∞
8
7
!
8
7
(5)
2
∞
∞
∞
∞
∞
∞
ë
(5)
3
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
!
1
(5)
3
∞
∞
∞
∞
∞
∞
∞
ë
(5)
4
∞
∞
∞
∞
∞
∞
3
5
4 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
∞
5
6
!
5
6
(5)
4
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
33
(5)
5
∞
∞
∞
∞
∞
∞
1
4
5 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
∞
8
9
8
9
(5)
5
∞
∞
∞
∞
∞
∞
ë
(5)
6
∞
∞
∞
∞
∞
11
3
2
6 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
22
4
2
!
22
4
2
(5)
6
∞
∞
∞
∞
∞
ë
(5)
7
∞
∞
∞
∞
∞
∞
2
2
7 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
∞
7
9
!
7
9
(5)
7
∞
∞
∞
∞
∞
∞
ë
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
34
(5)
8 ë
∞
∞
∞
∞
∞
5
2
6
8 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
12
10
13
! }
12
10
13
(5) min{
8
∞
∞
∞
∞
∞
ë =
=
10;
k = 6
) 6 (
1ë
∞
∞
∞
8
5
7
4
6
1 V
+
10
7
2
8
5
1
7
0
(5)
j
ë
=
∞
∞
∞
21
14
12
5
13
! }}
21
14
12
5
13
min{ ; 0 min{ ) 6 (
1
∞
∞
∞
ë =
=
0;
(6)
2 ë
∞
∞
∞
∞
∞
∞
6
7
2 V
+
10
7
2
8
5
1
7
0
(5)
j
ë
=
∞
∞
∞
∞
∞
∞
8
7
! }
8
7
(6) min{
2
∞
∞
∞
∞
∞
∞
ë =
=
7;
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
35
(6)
3 ë
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
10
7
2
8
5
1
7
0
(5)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
! }
1
(6) min{
3
∞
∞
∞
∞
∞
∞
∞
ë =
=
1;
(6)
4 ë
∞
∞
∞
∞
∞
∞
3
5
4 V
+
10
7
2
8
5
1
7
0
(5)
j
ë
=
∞
∞
∞
∞
∞
∞
5
6
! }
5
6
(6) min{
4
∞
∞
∞
∞
∞
∞
ë =
=
5;
(6)
5 ë
∞
∞
∞
∞
∞
∞
1
4
5 V
+
10
7
2
8
5
1
7
0
(5)
j
ë
=
∞
∞
∞
∞
∞
∞
8
9 ! }
8
9
(6) min{
5
∞
∞
∞
∞
∞
∞
ë =
=
8;
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
36
(6)
6 ë
∞
∞
∞
∞
∞
11
3
2
6 V
+
10
7
2
8
5
1
7
0
(5)
j
ë
=
∞
∞
∞
∞
∞
21
4
2
! }
21
4
2
(6) min{
6
∞
∞
∞
∞
∞
ë =
=
2;
(6)
7 ë
∞
∞
∞
∞
∞
∞
2
2
7 V
+
10
7
2
8
5
1
7
0
(5)
j
ë
=
∞
∞
∞
∞
∞
∞
7
9
! }
7
9
(6) min{
7
∞
∞
∞
∞
∞
∞
ë =
=
7;
(6)
8 ë
∞
∞
∞
∞
∞
5
2
6
8 V
+
10
7
2
8
5
1
7
0
(5)
j
ë
=
∞
∞
∞
∞
∞
12
10
13
! }
12
10
13
(6) min{
8
∞
∞
∞
∞
∞
ë =
=
10;
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
37
k = 7
) 7 (
1ë
∞
∞
∞
8
5
7
4
6
1 V
+
10
7
2
8
5
1
7
0
(6)
j
ë
=
∞
∞
∞
18
12
12
5
13
! }}
18
12
12
5
13
min{ ; 0 min{ ) 7 (
1
∞
∞
∞
ë =
=
0;
(7)
2 ë
∞
∞
∞
∞
∞
∞
6
7
2 V
+
10
7
2
8
5
1
7
0
(6)
j
ë
=
∞
∞
∞
∞
∞
∞
8
7
! }
8
7
(7) min{
2
∞
∞
∞
∞
∞
∞
ë =
=
7;
(7)
3 ë
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
10
7
2
8
5
1
7
0
(6)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
! }
1
(7) min{
3
∞
∞
∞
∞
∞
∞
∞
ë =
=
1;
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
38
(7)
4 ë
∞
∞
∞
∞
∞
∞
3
5
4 V
+
10
7
2
8
5
1
7
0
(6)
j
ë
=
∞
∞
∞
∞
∞
∞
5
6
! }
5
6
(7) min{
4
∞
∞
∞
∞
∞
∞
ë =
=
5;
(7)
5 ë
∞
∞
∞
∞
∞
∞
1
4
5 V
+
10
7
2
8
5
1
7
0
(6)
j
ë
=
∞
∞
∞
∞
∞
∞
8
9 ! }
8
9
(7) min{
5
∞
∞
∞
∞
∞
∞
ë =
=
8;
(7)
6 ë
∞
∞
∞
∞
∞
11
3
2
6 V
+
10
7
2
8
5
1
7
0
(6)
j
ë
=
∞
∞
∞
∞
∞
21
4
2
! }
21
4
2
(7) min{
6
∞
∞
∞
∞
∞
ë =
=
2;
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
39
(7)
7 ë
∞
∞
∞
∞
∞
∞
2
2
7 V
+
10
7
2
8
5
1
7
0
(6)
j
ë
=
∞
∞
∞
∞
∞
∞
7
9
! }
7
9
(7) min{
7
∞
∞
∞
∞
∞
∞
ë =
=
7;
(7)
8 ë
∞
∞
∞
∞
∞
5
2
6
8 V
+
10
7
2
8
5
1
7
0
(6)
j
ë
=
∞
∞
∞
∞
∞
12
10
13
! }
12
10
13
(7) min{
8
∞
∞
∞
∞
∞
ë =
=
10;
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
40
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
8 11
5 1 5
6 3
2
7 4 2
4 5 3
6 2 6
7 1 2
!
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
8 11
5 1 5
6 3
2
7 4 2
4 5 3
6 2 6
7 1 2
8
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8
j
j
j
j
j
j
j
j
i
i i i i i i i
c
c
c
c
c
c
c
c
c c c c c c
c c
= ∞ ∞
= ∞ ∞
= ∞
= ∞ ∞ ∞
= ∞ ∞
= ∞
= ∞
=
8 13 13 11 10 10 10
7 9 7 7 7 7 7
6 2 2 2 2 2 2 2
5 9 8 8 8 8
4 5 5 5 5 5 5
3 1 1 1 1 1 1 1
2 7 7 7 7 7 7 7
1 0 0 0 0 0 0 0 0
(0) (1) (2) (3) (4)
(5) (6) (7)
i
i
i
i
i
i
i
i
i
i i i i i i i ë
ë ë ë ë ë ë ë
На
матрице минимальных путей указан V1V6V4V7V5V8 Ц искомый
минимальный путь из
V1 в
V8.
Определяем искомые минимальные пути:
V1!V2, величина 7
2
ë(n−1) = ë
i
=
7 выражает длину минимального пути из V1 в
V2.
Определяем минимальное число k1≥1, при котором выполняется равенство
(7)
2
(1)
2
( )
2
ë k1 = ë = ë ! k1= 1, т.е.
минимальное число дуг, соединяющих V1 и
V2
равно 1. Определяем последовательность номеров i1, i2 где i1 = 2:
Тогда i1, i2 = 2, 1!V1V2 Ц искомый минимальный путь.
V1!V3, величина 7
3 ë = 1 выражает длину минимального пути из V1 в
V3.
Определяем минимальное число k1≥1, при котором выполняется равенство
(7)
3
(1)
3
( )
3
ë k1 = ë = ë ! k1= 1, т.е.
минимальное число дуг, соединяющих V1 и
V3
равно 1. Определяем последовательность номеров i1, i2 где i1 = 3:
Тогда i1, i2 = 3, 1!V1V6 Ц искомый минимальный путь.
V1!V4, величина 7
4 ë = 5 выражает длину минимального пути из V1 в
V4.
Определяем минимальное число k1≥1, при котором выполняется равенство
(7)
4
(2)
4
( )
4
ë k1 = ë = ë ! k1= 2, т.е.
минимальное число дуг, соединяющих V1 и
V4
равно 2. Определяем последовательность номеров i1, i2, i3 где i1 = 4:
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
41
64
(1)
6
4
(1)
4
( 1) (1) }
5
6
} min{
3
5
2
1
7
0
min{ } min{
2 2
2 1 2 2
1
2 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
∞
+
∞
∞
∞
− +
= + = ∞ ë
ë
ë ë =2 + 3 = 5 = (2)
4 ë = 5 !
i2 = 6;
16
) 0 (
1
6
(0)
6
(0) (0) }
2
} min{
11
3
0 2
min{ } min{
3 3
3 3 2 5 5 c
c
c c
i
i
i
i
i i i = +
∞
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
+
∞
∞
∞
∞
∞
∞
∞
+ = + = ë
ë
ë ë = 0 + 2 = 2 = (1)
6 ë = 2 !
i3 = 1;
Тогда i1, i2, i3 = 4, 6, 1!V1V6V4 Ц искомый минимальный путь.
V1!V5, величина 7
5 ë = 8 выражает длину минимального пути из V1 в
V5.
Определяем минимальное число k1≥1, при котором выполняется равенство
(7)
5
(4)
5
( )
5
ë k1 = ë = ë ! k1= 4, т.е.
минимальное число дуг, соединяющих V1 и
V7
равно 4. Определяем последовательность номеров i1, i2, i3, i4, i5 где i1 = 5:
75
(3)
7
5
(3)
5
( 1) (3) }
8
} min{9
1
4
13
7
2
9
5
1
7
0
min{ } min{
2 2
2 1 2 2
1
2 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
∞
− +
= + = + ë
ë
ë ë =7 + 1 = 8 = (4)
5 ë = 8 !
i2 = 7;
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
42
47
(1)
4
7
(2)
7
( 2) (2)
3 }
5
7
9
2 } min{
2
13
9
2
5
1
7
0
min{ } min{
3 3
3 2 3 3
1 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
∞
+
∞
− +
= + = ë
ë
ë ë = 5 + 2 = 7 = (3)
7 ë = 7 !
i3 = 4;
64
(1)
6
4
(1)
4
( 4) (1) }
5
6
} min{
3
5
2
1
7
0
min{ } min{
4 4
4 3 4 4
1
4 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
∞
+
∞
∞
∞
− +
= + = ∞ ë
ë
ë ë = 2 + 3 = 5 = (2)
4 ë = 5 !
i4 = 6;
16
) 0 (
1
6
(0)
6
(0) (0) }
2
} min{
11
3
0 2
min{ } min{
5 5
5 5 4 5 5 c
c
c c
i
i
i
i
i i i = +
∞
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
+
∞
∞
∞
∞
∞
∞
∞
+ = + = ë
ë
ë ë = 0 + 2 = 2 = (1)
6 ë = 2 !
i5 = 1;
Тогда i1, i2, i3, i4, i5 = 5, 7, 4, 6, 1!V1V6V4V7V5 Ц искомый минимальный путь.
V1!V6, величина 7
6 ë = 2 выражает длину минимального пути из V1 в
V6.
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
43
Определяем минимальное число k1≥1, при котором выполняется равенство
(7)
6
(1)
6
( )
6
ë k1 = ë = ë ! k1= 1, т.е.
минимальное число дуг, соединяющих V1 и
V6
равно 1. Определяем последовательность номеров i1, i2 где i1 = 6:
Тогда i1, i2 = 6, 1!V1V6 Ц искомый минимальный путь.
V1!V7, величина 7
7 ë = 7 выражает длину минимального пути из V1 в
V7.
Определяем минимальное число k1≥1, при котором выполняется равенство
(7)
7
(3)
7
( )
7
ë k1 = ë = ë ! k1= 3, т.е.
минимальное число дуг, соединяющих V1 и
V7
равно 3. Определяем последовательность номеров i1, i2, i3, i4 где i1 = 7:
47
(2)
4
7
(2)
7
( 1) (2) 7}
9
2 } min{
2
13
9
2
8
5
1
7
0
min{ } min{
2 2
2 1 2 2
1
2 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
∞
− +
= + = + ë
ë
ë ë =5 + 2 = 7 = (3)
7 ë = 7 !
i2 = 4;
64
(1)
6
4
(1)
4
( 2) (1)
3 }
5
6
} min{
3
5
2
1
7
0
min{ } min{
3 3
3 2 3 3
1 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
∞
+
∞
∞
∞
− +
= + = ∞ ë
ë
ë ë = 2 + 3 = 5 = (2)
4 ë = 5 !
i3 = 6;
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
44
16
) 0 (
1
6
(0)
6
(0) (0) }
2
} min{
11
3
0 2
min{ } min{
4 4
4 4 3 4 4 c
c
c c
i
i
i
i i i i = +
∞
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
+
∞
∞
∞
∞
∞
∞
∞
+ = + = ë
ë
ë ë = 0 + 2 = 2 = (1)
6 ë = 2 !
i4 = 1;
Тогда i1, i2, i3, i4 = 7, 4, 6, 1!V1V6V4V7 Ц искомый минимальный путь.
V1!V8, величина 78
ë = 10 выражает длину минимального пути из V1 в
V8.
Определяем минимальное число k1≥1, при котором выполняется равенство
(7)
8
(5)
8
( )
8
ë k1 = ë = ë ! k1= 5, т.е.
минимальное число дуг, соединяющих V1 и
V8
равно 5. Определяем последовательность номеров i1, i2, i3, i4, i5, i6 где i1 = 8:
58
(4)
5
8
(4)
8
( 1) (4) }
12
10
13
} min{
5
2
6
10
7
2
8
5
1
7
0
min{ } min{
2 2
2 1 2 2
1
2 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
− +
= + = + ë
ë
ë ë =8 + 2 = 10 = (5)
8 ë = 10 !
i2 = 5;
75
(3)
7
5
(3)
5
( 2) (3)
3 }
8
} min{9
1
4
13
7
2
9
5
1
7
0
min{ } min{
2 2
3 2 3 3
1 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
∞
− +
= + = + ë
ë
ë ë = 7 + 1 = 8 = (4)
5 ë = 8 !
i3 = 7;
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
45
47
(3)
4
7
(2)
7
( 3) (2) 7}
9
2 } min{
2
13
9
2
5
1
7
0
min{ } min{
4 4
4 3 4 4
1
4 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
∞
+
∞
− +
= + = ë
ë
ë ë = 5 + 2 = 7 = (3)
7 ë = 7 !
i4 = 4;
64
(1)
6
4
(1)
4
( 4) (2) }
5
6
} min{
3
5
2
1
7
0
min{ } min{
5 5
5 4 5 5
1
5 c
c
c c
i
i
i
i i i
k
i
= +
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
∞
+
∞
∞
∞
− +
= + = ∞ ë
ë
ë ë = 2 + 3 = 5 = (2)
4 ë = 5 !
i5 = 6;
16
) 0 (
1
6
(0)
6
(0) (0) }
2
} min{
11
3
0 2
min{ } min{
6 6
6 6 5 6 6 c
c
c c
i
i
i
i i i i = +
∞
∞
∞
∞
∞
∞
∞
=
∞
∞
∞
∞
∞
+
∞
∞
∞
∞
∞
∞
∞
+ = + = ë
ë
ë ë = 0 + 2 = 2 = (1)
6 ë = 2 !
i6 = 1;
Тогда i1, i2, i3, i4, i5, i6 = 8, 5, 7, 4, 6, 1!V1V6V4V7V5V8 Ц искомый минимальный
путь.
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
46
11. Найти остовное дерево40
с минимальной суммой длин входящих в него
ребер.
Если длины ребер с 14 по
17
= 5, а остальные - с
1
по 13 = 6, 5, 3, 4, 2,
11, 8, 1, 5, 4, 6,
2, 3 соответственно.
Используя алгоритм для получения МОД41, решаем задачу:
12. Пусть каждому ребру неориентированного графа соответствует некоторый
элемент электрической цепи . Составить линейно-независимую систему
уравнений Кирхгофа для токов и
напряжений.
40 Остовным деревом графа G называют его
подграф D ∈ G, содержащий все
вершины графа G и являющийся
деревом.
Дерево Ц связный неориентированный граф,
не имеющий циклов.
41 МОД
Ц
минимальное остовное дерево.
1
2 3
5
4
9
7 8
6
q10
q15
q13
q12
q6
q7
q8
q3
q1
q2
q14
q16
q17
q9
q11
q4
q5
4
5
3
2
11 8
1
3
6
5
5
5
5
5
6
4
2
10 11
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
47
Решение:
Введем ориентацию:
Найдем остовное дерево:
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
2 3
2 3
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
48
Определяем базис цикла:
n = 11-6+1=6.
1, 2, 3, 4, 5, 6,
7, 8, 9,10,11
c(ì1) = (1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0);
c(ì2) = (0, 1, 1, 1, 0,-1, 0, 0, 0, 0,-1);
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
2 3
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
2 3
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
49
c(ì3) = (1, 1, 1, 1, 0, 0, 0, 0, 0, 1,-1);
c(ì4) = (1, 1, 0, 0, 0, 0,-1, 0, 0, 0, 0);
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
2 3
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
2 3
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
50
c(ì5) = (0, 0, 1, 1, 0, 0, 0,-1, 0, 0, 0);
c(ì6) = (1, 1, 1, 0, 0, 0, 0, 0, -1, 1, 0);
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
2 3
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
2 3
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
51
Находим цикломатическую матрицу:
G =
−
−
−
−
− −
1 1 1 0 0 0 0 0 1 1 0
0 0 1 1 0 0 0 1 0 0 0
1 1 0 0 0 0 1 0 0 0 0
1 1 1 1 0 0 0 0 0 1 1
0 1 1 1 0 1 0 0 0 0 1
1 1 1 1 1 0 0 0 0 0 0
Уравнения Кирхгофа для напряжений:
−
−
−
−
− −
1 1 1 0 0 0 0 0 1 1 0
0 0 1 1 0 0 0 1 0 0 0
1 1 0 0 0 0 1 0 0 0 0
1 1 1 1 0 0 0 0 0 1 1
0 1 1 1 0 1 0 0 0 0 1
1 1 1 1 1 0 0 0 0 0 0
x
11
10
9
8
7
6
5
4
3
2
1
U
U
U
U
U
U
U
U
U
U
U
=
+ + − + =
+ + =
+ − =
+ + + + − =
+ + − − =
+ + + + =
0
0
0
0
0
0
1 2 3 9 10
4 9 11
3 4 8
1 2 3 4 10 11
2 3 4 6 11
1 2 3 4 5
U U U U U
U U U
U U U
U U U U U U
U U U U U
U U U U U
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
52
Уравнения Кирхгофа для токов.
Составляем матрицу инцидентности:
B =
−
− − −
− −
− −
−
− −
0 0 0 0 0 1 0 0 1 1 1
0 0 0 1 1 0 0 1 0 0 1
0 0 1 1 0 0 0 0 1 0 0
0 1 1 0 0 0 1 1 0 0 0
1 1 0 0 0 1 0 0 0 0 0
1 0 0 0 1 0 1 0 0 1 0
B x
11
10
9
8
7
6
5
4
3
2
1
I
I
I
I
I
I
I
I
I
I
I
=
− + + + =
− + + − =
− + − =
− + − + =
− + + =
− + − =
0
0
0
0
0
0
6 9 10 4
4 5 8 11
3 4 9
2 3 7 8
1 2 6
1 5 7 10
I I I I
I I I I
I I I
I I I I
I I I
I I I I
1
5
4
9
7 8
6
V1
10 11
V6
V2 V3 V4
V5
2 3
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
53
13. Используя алгоритм Форда-Фалкерсона построить максимальный поток в
транспортной сети42.
Значения a, b, c, d, e, f, g = 3, 4, 5, 8, 6, 9,
5.
Решение:
42 Транспортной сетью называется орграф D = (V, X), в
котором выделены две вершины:
источник (из
него дуги
только исходят) и
сток (в
него дуги только заходят).
e
b
b
a
a
d+e
d
e+1
g
c
f+g+1
f
f
c+1
d+1
g+1
(6)
(4)
(4)
(3)
(3)
(14)
(8)
(7)
(5)
(5)
(15)
(9)
(9)
(6)
(9)
(6)
V3
V2
V1
V5
V7
V6
V8
V9
V4
Расчетная работа по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
54
Этап.
1. Построение полного потока43.
Полагаем ϕ
(x) =
0 для любого x ∈ X.
43 Поток ϕ
называется полным,
если любой путь из источника в сток содержит хотя бы одну насыщенную дугу,
т.е.
дугу x, для
которой ϕ (x) =
c(x) , где c(x) - пропускная способность дуги.
(6)
(4)
(4)
(3)
(3)
(14)
(8)
(7)
(5)
(5)
(15)
(9)
(9)
(6)
(9)
(6)
V2
V1
V5
V7
V6
V8
V9
V4
V3
c(x)=6, ϕ(x) = 0
c(x)=4, ϕ(x) = 0
c(x)=4, ϕ(x) = 0
c(x)=3, ϕ(x) = 0
c(x)=3, ϕ(x) = 0
c(x)=14, ϕ(x) = 0
c(x)=8, ϕ(x) = 0
c(x)=7, ϕ(x) = 0
c(x)=5, ϕ(x) = 0
c(x)=5, ϕ(x) = 0
c(x)=15, ϕ(x) = 0
c(x)=9, ϕ(x) = 0
c(x)=9, ϕ(x) = 0
c(x)=6, ϕ(x) = 0
c(x)=9, ϕ(x) = 0
c(x)=6, ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
Расчетная работа по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
55
Находим простую цепь ç1 из V1(источник)
в V9(сток):
например V1V2V3V4V9.
a = min(c(x) −ϕ (x)) > 0,
x∈ç ,! a = min(3 - 0, 3 Ц
0, 8-0, 14-0) = 3.
Увеличиваем поток по
дугам (V1, V2), (V2, V3), (V3, V4), (V4, V9) на
величину
a = 3.
Удаляем насыщенные дуги (на рисунке помечены л ).
D, ϕ=ϕ1
Находим ç2, например,
V1V3V4V9. a = min(9-0, 8-3,
14-3) = min(9, 5, 11) = 5.
(6), ϕ(x) = 0
(4), ϕ(x) = 0
(4), ϕ(x) = 0
(3), ϕ(x) = 0 + 3 = 3
(3), ϕ(x) = 0 + 3 = 3
(14), ϕ(x) = 0 + 3 = 3
(8), ϕ(x) = 0 + 3 = 3
(7), ϕ(x) = 0
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 0
(9), ϕ(x) = 0
(9), ϕ(x) = 0
(6), ϕ(x) = 0
(9), ϕ(x) = 0
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(6), ϕ(x) = 0
(4), ϕ(x) = 0
(4), ϕ(x) = 0
(14), ϕ(x) = 3
(8), ϕ(x) = 3
(7), ϕ(x) = 0
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 0
(9), ϕ(x) = 0
(9), ϕ(x) = 0
(6), ϕ(x) = 0
(9), ϕ(x) = 0
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
56
Увеличиваем поток на
a
= 5. Удаляем насыщенную дугу V3V4.
DТ, ϕ=ϕ2.
Находим ç3, например,
V1V5V6V9. a = min(4-0, 4-0,
9-0, 15-0) = 4.
Увеличиваем поток на
a
= 4. Удаляем насыщенные дуги (V1,V3) и
(V1,V3).
(6), ϕ(x) = 0
(4), ϕ(x) = 0
(4), ϕ(x) = 0
(14), ϕ(x) = 3 + 5 = 8
(8), ϕ(x) = 3 + 5 = 8
(7), ϕ(x) = 0
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 0
(9), ϕ(x) = 0
(9), ϕ(x) = 0
(6), ϕ(x) = 0
(9), ϕ(x) = 0 + 5 = 5
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(6), ϕ(x) = 0
(4), ϕ(x) = 0
(4), ϕ(x) = 0
(7), ϕ(x) = 0 (14), ϕ(x) = 8
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 0
(9), ϕ(x) = 0
(9), ϕ(x) = 0
(6), ϕ(x) = 0
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(9), ϕ(x) == 5
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
57
DТ, ϕ=ϕ3.
Находим ç4, например,
V1V6V8V9. a = min(9-0, 9-4,
15-4) = min(9, 5, 11) = 5.
Увеличиваем поток на
a
= 5. Удаляем насыщенную дугу V6V8.
(6), ϕ(x) = 0
(4), ϕ(x) = 0 + 4 = 4
(4), ϕ(x) = 0 + 4 = 4
(7), ϕ(x) = 0 (14), ϕ(x) = 8
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 0 + 4 = 4
(9), ϕ(x) = 0 + 4 = 4
(9), ϕ(x) = 0
(6), ϕ(x) = 0
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(6), ϕ(x) = 0 (14), ϕ(x) = 8
(8), ϕ(x) = 8
(7), ϕ(x) = 0
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 4
(9), ϕ(x) = 4
(9), ϕ(x) = 0
(6), ϕ(x) = 0
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(9), ϕ(x) = 5
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
58
DТ, ϕ=ϕ4.
Находим ç5, например,
V1V7V4V9. a = min(6-0, 7-0,
14-8) = min(6, 7, 6) = 6.
Увеличиваем поток на
a
= 6. Удаляем насыщенную дуги V4V9 и
V1V7.
DТ, ϕ=ϕ5. Простой цепи из V1 в
V9 не
существует, следовательно поток ϕ5
является полным. Его величина равна ϕ5 = 0+9=9.
(6), ϕ(x) = 0 (14), ϕ(x) = 8
(8), ϕ(x) = 8
(7), ϕ(x) = 0
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 4 + 5 = 9
(9), ϕ(x) = 4 + 5 = 9
(9), ϕ(x) = 0 + 5 = 5
(6), ϕ(x) = 0
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(6), ϕ(x) = 0
(14), ϕ(x) = 8 + 6 = 14
(7), ϕ(x) = 0 + 6 = 6
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 9
(9), ϕ(x) = 5
(6), ϕ(x) = 0 + 6 = 6
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(9), ϕ(x) = 5
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
59
Этап 2. Увеличение полного потока до
максимального44. Строим орграф
приращений:
I(D, ϕ5):
Находим простую цепь ç6, например,
V1V3V2V7V9.
a = min[min(9-5,
6-0, 5-0), min(3)] = 3.
44 Поток в транспортной сети D является максимальным тогда и только тогда, когда в I(D, ϕ) сток не
достижим
из
источника. I(D, ϕ) - орграф приращений.
(6), ϕ(x) = 0 (7), ϕ(x) = 6
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 9
(9), ϕ(x) = 5
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(9), ϕ(x) = 5
(6), ϕ(x) = 0 (7), ϕ(x) = 6
(5), ϕ(x) = 0
(5), ϕ(x) = 0
(15), ϕ(x) = 9
(9), ϕ(x) = 5
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(9), ϕ(x) = 5
(3), ϕ(x) = 3
(8), ϕ(x) = 8
(4), ϕ(x) = 4
(9), ϕ(x) = 9
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
60
Строим орграф приращений:
I(D, ϕ6):
(6), ϕ(x) = 0 + 3 = 3
(7), ϕ(x) = 6
(5), ϕ(x) = 0
(5), ϕ(x) = 0 + 3 = 3
(15), ϕ(x) = 9
(9), ϕ(x) = 5
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(9), ϕ(x) = 5 + 3 = 8
(3), ϕ(x) = 3 Ц3 = 0
(8), ϕ(x) = 8
(4), ϕ(x) = 4
(9), ϕ(x) = 9
(6), ϕ(x) = 3
(7), ϕ(x) = 6
(5), ϕ(x) = 0
(5), ϕ(x) = 3
(15), ϕ(x) = 9
(9), ϕ(x) = 5
(6), ϕ(x) = 0
V2
V1
V5
V7
V6
V8
V9
V4
V3
(9), ϕ(x) = 8
(3), ϕ(x) = 0
(8), ϕ(x) = 8
(4), ϕ(x) = 4
(9), ϕ(x) = 9
Расчетная работа по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
61
Находим простую цепь ç6, например,
V1V6V5V7V9.
a = min[min(9-5,
6-0, 5-3), min(4)] = 2. Увеличиваем поток на 2. Удаляем
насыщенную дугу V7V9.
Строим орграф приращений:
I(D, ϕ7):
(6), ϕ(x) = 3
(7), ϕ(x) = 6
(5), ϕ(x) = 0
(5), ϕ(x) = 3 + 2 = 5
(15), ϕ(x) = 9
(9), ϕ(x) = 5 + 2 = 7
(6), ϕ(x) = 0 + 2 = 2
V2
V1
V5
V7
V6
V8
V9
V4
V3
(9), ϕ(x) = 8
(3), ϕ(x) = 0
(8), ϕ(x) = 8
(4), ϕ(x) = 4 - 4 = 0
(9), ϕ(x) = 9
(6), ϕ(x) = 3
(7), ϕ(x) = 6
(5), ϕ(x) = 0 (15), ϕ(x) = 9
(9), ϕ(x) = 7
(6), ϕ(x) = 2
V2
V1
V5
V7
V6
V8
V9
(9), ϕ(x) = 8 V4
(3), ϕ(x) = 0
(8), ϕ(x) = 8
(4), ϕ(x) = 0
(9), ϕ(x) = 9
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
62
Полученный поток является максимальным, так как сток не
достижим из источника (насыщенные дуги выделены).
Сумма потоков из
источника: 3+4+6+8+7 = 28,
сумма потоков в
сток: 14+5+9 = 28!
ϕ(x) = 3
ϕ(x) = 0
ϕ(x) = 4
ϕ(x) = 3
ϕ(x) = 0
ϕ(x) = 14
ϕ(x) = 8
ϕ(x) = 6
ϕ(x) = 0
ϕ(x) = 5
ϕ(x) = 9
ϕ(x) = 9
ϕ(x) = 7
ϕ(x) = 6
ϕ(x) = 8
ϕ(x) = 2
V2
V1
V5
V7
V6
V8
V9
V4
V3
(6)
(4)
(4)
(3)
(3)
(14)
(8)
(7)
(5)
(5)
(15)
(9)
(9)
(6)
(9)
(6)
V2
V1
V5
V7
V6
V8
V9
V4
Расчетная работ по дискретной математике
студента группы
18-101 Чумина Олега .chuminoleg.boom.ru
Вариант №19.
63
Литература:
1. Нефедов В.Н.,
Осипова В.А.
Курс дискретной математики.
Ц М.:
Издательство МАИ,
1992.
2. Методические указания по
выполнению расчетных работ по
дискретной математике. Под. Ред. Осиповой.__