Расчетная работа по дискретной математике
| Загрузить архив: | |
| Файл: ref-7301.zip (1333kb [zip], Скачиваний: 95) скачать |
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ)
Кафедра №805
«Математическая
кибернетика»
Вариант №19
Расчетная работа по дискретной математике
Студент:
Чумин Олег
Группа:
№18-101
Преподаватель: доцент
Рыбин
Владимир
Васильевич.
- 2000…2001 гг.
-
Расчетная работа по дискретной математике
студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
2
Элементы математической логики и теории булевых функций.
1. Определитьдля
заданнойформулылогики
высказываний:
а.) Определитьтаблицу
истинности.
б.) ДНФ, КНФ,
СДНФ,
СКНФметодомравносильныхпреобразований.
в.) Задатьтабличным
способомсоответствующуюбулеву
функцию.
г.) НайтиСДНФ
иСКНФтабличным
способом(сравнить
соСДНФ, СКНФ,
полученнымивпункте
«б»).
д.) УказатьминимальнуюДНФи
соответствующуюей
переключательную
схему.
е.) Построитьмногочлен
Жегалкина.
Формула
- (Y&Z) ~
(Z⊃X).1
Решение:
а) Определяемтаблицу
истинности.
Придавая
каждойпеременнойформулы
одноизистинностныхзначений
{И,
Л}2 иучитывая, чтокаждое
вхождениезнака
относитсякнаикратчайшей
подформуле, следующейза
ним.
Списокпеременныхформулы
содержиттри3
переменных–
X, Y, Z, Y&Z, (Y&Z), Z,
Z⊃X, (Y&Z) ~ (Z⊃X)
X Y Z Y&Z (Y&Z) Z
Z⊃X (Y&Z) ~ (Z⊃X)
1 ИИ
ИИЛ
ЛИЛ
2 ИИ
ЛЛИ
ИИИ
3 ИЛ
ИЛИ
ЛИИ
4 ЛИ
ИИЛ
ЛИЛ
5 ИЛ
ЛЛИ
ИИИ
6 ЛЛ
ИЛИ
ЛИИ
7 ЛИ
ЛЛИ
ИЛЛ
8 ЛЛ
ЛЛИ
ИЛЛ
б.) ОпределяемДНФ4,
КНФ5, СДНФ6, СКНФ7 методомравносильных
преобразований.
1 символотрицания
«неA»
& символ
коньюнкциидвухвысказыванийA&B «A иB», естьвысказываниеистинноетогда
итолько
тогда, когдаистинны
обавысказыванияA иB;
V символдизьюнкциидвухвысказыванийAVB «A илиB», естьвысказываниеложноетогда
итолько
тогда, когдаоба
высказыванияложны
~ символэквиваленциидвухвысказыванийA~B «A эквивалентноB», естьвысказываениеистинное
тогда
итолькотогда, когдаистинны
A иB;
⊃
символимпликациидвух
высказыванийA
⊃ B «A влечетB», естьвысказываниеложноетогда
итолько
тогда, когдаA истинно, аB ложно.
2 И– истина, Л- ложь
3 сопоставлениекаждой
переменнойсписканекоторогоистинностногозначения
4 Формуланаходится
вдизьюнктивнойнормальнойформе(ДНФ),
еслионаявляется
дизьюнкцией(быть
может
одночленной) элементарныхконьюнкций
5 Формуланаходится
вконьюктивнойнормальнойформе(КНФ),
еслионаявляется
коньюнкцией(возможно
одночленной) элементарныхдизьюнкций
Расчетная работа по дискретной математике
студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
3
Находим
ДНФ,
пользуясьалгоритмомнахожденияДНФ:
1-йэтап. Преобразуемисходную
формулувравносильную, вкоторой
отсутствуютоперацииэквиваленции« ~ » иимпликации« ⊃ ». Дляэтого
заменяем
любыеподформулывида
A ⊃ B наA V B, таккак
A B A ⊃ B
A A V B
И
ИИЛ
И
И
ЛЛЛ
Л
Л
ИИИ
И
Л
ЛИИ
И
т.е. A ⊃B ≡ A V B.
A ~ B ≡(A & B) V (A &B)
A B A B A & B A &B (A & B) V
(A &B) A ~ B
И
ИЛЛ
ИЛИ
И
И
ЛЛИ
ЛЛЛ
Л
Л
ИИЛ
ЛЛЛ
Л
Л
ЛИИ
ЛИИ
И
(Y&Z) ~
(Z ⊃X) ≡ (Y&Z) ~ (Z
V X) ≡ (Y V Z)
~ (Z V X) ≡
≡
((Y V Z)
& (Z V X)) V ((Y V Z)
& (Z V X)) ≡
2-йэтап.
Вносим
знакотрицания«»
подскобки, пользуясьзаконами
деМоргана8, и
сокращаем
«»позакону
снятиядвойногоотрицания9.
≡
((Y V Z)
& (Z V X)) V ((Y
& Z) & (Z &X))
≡
≡
((Y V Z)
& (Z V X)) V ((Y & Z) & (Z &X))
≡
3-йэтап.
Так
какполученнаяформула
ненаходитсяв
ДНФ(V
неэлементарных
конъюнкций), топрименяем
законыдистрибутивности& относительноV10.
≡
[(Y V Z)
& (Z V X)] V [(Y & Z) & (Z &X)]
≡
≡
[(Y V Z)
& (Z V X)] V (Y & Z &Z &X)11 ≡
≡
[((Y V Z)
& Z) V ((Y
V Z) & X)] V (Y & Z &Z &X)
≡
6 СДНФ– совершеннаядизьюнктивнаянормальнаяформа
7 СКНФ– совершеннаяконьюктивнаянормальнаяформа
8 (A&B)≡A VB
– первыйзаконде
Моргана,
(A V B)≡A &B
– второйзаконде
Моргана
9 A
≡ A – законснятия
двойногоотрицания
10 A&(B V C) ≡
(A&B) V (A&C) – закон
дистрибутивности& относительноV
11 скобкиможно
убратьпользуясьзаконом
коммутативностипо
&: A&B≡B&A ипо
этомужезакону
меняем
местами
подформулы
Расчетная работа по дискретной математике
студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
4
≡
[(Z & (Y V Z))
V (X & (Y V Z))] V (Y & Z &Z &X)
≡
≡
[((Z &Y) V (Z &Z)) V ((X &Y) V (X & Z))]12 V
(Y & Z &Z
&X) ≡
≡
(Z &Y) V (Z &Z) V (X &Y) V (X & Z) V (Y & Z &Z &X)
≡
полученнаяформуланаходится
вДНФ
Используя
законпоглощения13 сокращаемполученнуюформулудо
вида:
≡
(Z &Y) V (X &Y) V (X & Z) V (Z &Z) V ((Z &Z) &(Y &X) ≡
≡
(Z &Y) V (X &Y) V (X & Z).
Находим
КНФ(Y&Z) ~
(Z⊃X) пользуясьалгоритмом.
Для
этоговоспользуемсяформулой
с«тесными» отрицаниями, полученнойв
предыдущемпункту14 (2-йэтап) принахожденииДНФ:
≡
((Y V Z)
& (Z V X)) V ((Y & Z) & (Z &X))
≡
так
какформулане
находитсявКНФ
топрименяемзакон
дистрибутивностиV
относительно&15
≡
((Y V Z)
& (Z V X)) V (Y & Z & Z &X)
≡
≡
(Y & Z & Z &X)
V ((Y V Z) & (Z V X)) ≡
≡
[(Y & Z & Z &X)
V (Y V Z)] & [(Y & Z & Z &X)
V (Z V X)] ≡
≡
[(Y V Z)
V ((Y & Z) & (Z
&X))] & [(Z V X) V ((Y & Z)
& (Z &X))] ≡
≡
[((Y V Z)
V (Y & Z)) & ((Y
V Z) V (Z &X))]
& [((Z V X) V (Y & Z)) &
& ((Z V X) V (Z &X))]
≡
≡
[(Y V Z)
V (Y & Z)] & [(Y
V Z) V (Z &X)]
& [(Z V X) V (Y & Z)] &
& [(Z V X) V (Z &X)]
≡
≡
[((Y V Z)
V Y) & ((Y
V Z) V Z)] & [((Y V Z)
V Z) & ((Y V Z)
VX)] &
& [((Z V X) V Y) & ((Z V X) V Z))] & [((Z V X) V
Z) & ((Z V X) VX)] ≡
≡
(Y V Z
V Y) & (Y V Z V Z) & (Y V Z
V Z) & (Y V Z
VX) &
& (Z V X V Y) & (Z V X V Z) & (Z V X V Z) & (Z V X VX) ≡
≡
(Y V Z
V Y) & (Y V Z V Z) & (Y V Z
V Z) & (Y V Z
VX) &
& (Z V X V Y) & (Z V X V Z) & (Z V X V Z) & (Z V X VX) ≡
полученнаяформуланаходится
вКНФ, воспользовавшисьзаконом
индемпотентностиV16, получаемследующий
сокращенныйвидформулы:
≡
(Y V Z
V Y) & (Y V Z V Z) & (Y V Z)
& (Y V Z VX)
&
& (Z V X V Y) & (Z V X) & (Z V X V Z) & (Z V X VX) ≡
теперь
применяем1-й
законпоглощения17:
≡
(Y V Z)
& (Z V X).
Находим
СДНФпоалгоритму:
1-йэтап. ВоспользовавшисьполученнойДНФ
12 скобкиубираем, пользуясьзаконом
коммутативностипо
V: AVB≡BVA
13 2-йзакон
поглощенияAV(A&B)
≡ A
14 можнотакже
воспользоватьсяследующей
равносильностьюA ~ B ≡ (A V B) & ( A V B)
15 A V (B & C) ≡
(A V B) & (A V C) – закон
дистрибутивностиV относительно&
16 AVA≡A – законидемпотентностиV
17 A&(AVB)≡A – 1-йзакон
поглощения
Расчетная работа по дискретной математике
студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
5
≡
(Z &Y) V (X &Y) V (X & Z) ≡
2-йэтап. Вычеркиваемвсе
элементарные&,
вкоторыевходит
одновременно
переменнаяиее
отрицание–
этотожеуже
проделано,
таккакв
полученной
формуле, находящейсяв
ДНФмыпровели
сокращение,
пользуясьзаконами
поглощения.
3-йэтап
Этот
этаптожевыполнен, таккак
вкаждойэлементарнойконъюнкции
полученнойтождественнойформулы
любаяпеременнаяили
ееотрицание
встречаетсятолькоодин
раз.
4-йэтап
относительновсегосписка
переменных
≡
(Z &Y) V (X &Y) V (X & Z) ≡ (X
&Y) V (Y & Z)V (X & Z) ≡
в
каждойизэлементарныхконъюнкцийотсутствуетоднаиз
переменных
списка. Применяем2-юформулу
расщепления18:
≡
(X &Y) V (Y
& Z)V (X & Z)
≡ [((X &Y) & Z)V((X &Y) & Z)]
V [((Y & Z)
& X) V ((Y & Z)&X)] V [((X & Z) & Y) V ((X & Z) & Y)]
≡
≡
(X &Y & Z) V (X &Y&Z)
V (Y & Z & X) V (Y & Z&X) V (X & Z & Y) V
(X & Z
& Y) ≡
5-йэтап. Вкаждой
элементарнойконъюнкцииполученнойформулы
переставляемконъюнктивныечлены, так, чтобыдля
каждогоi
= (1, 2, 3, … n)
на
i-мместе
стоялXi илиXi.
≡
(X &Y & Z) V (X &Y&Z)
V (X &Y & Z) V (X & Y
& Z) V (X & Y &Z)
V
(X &Y
& Z) ≡
6-йэтап. Повторяющиесяэлементарныеконъюнкциипо
закону
идемпотентностисокращаем:
≡
(X &Y & Z) V (X &Y&Z)
V (X &Y & Z) V (X & Y
& Z) V (X & Y &Z)
V
(X &Y
& Z) ≡
≡
(X &Y & Z) V (X &Y&Z)
V (X & Y & Z) V (X & Y &Z) V (X&Y&Z) ≡
≡
(X &Y & Z) V (X &Y&Z)
V (X & Y & Z) V (X & Y &Z).
Получили
тождественнуюформулу, находящуюсяв
СДНФ.
ОпределяемСКНФпо
такомужеалгоритму, чтои
СДНФ,
носзаменой
знаков
V на& и& наV:
1-йэтап.
Используемформулу, полученнуюпри
нахожденииКНФ.
≡
(Y V Z)
& (Z V X) ≡
18 формулырасщепления: A ≡ (A&B)V(A&B) - 1-я, A ≡ (AVB)&(AVB) – 2-я
Расчетная работа по дискретной математике
студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
6
2-йэтап. Пройденпри
нахожденииКНФ.
3-йэтап. Пройденпри
нахожденииКНФ.
4-йэтап.
≡
(Y V Z)
& (Z V X) ≡ [((Y V Z)
V X) & ((Y
V Z) V X)] & [((Z V X) V Y)
& ((Z V X) V Y)] ≡
≡
(Y V Z
V X) & (Y V Z V X)
& (Z V X V Y) & (Z V X V Y) ≡
5-йэтап.
≡
(X VY V Z)
& (X VY V Z)
& (X V Y V Z) & (X V Y
V Z) ≡
6-йэтап.
≡
(X VY V Z)
& (X VY V Z)
& (X V Y V Z) & (X V Y
V Z).
Сокращать
нечего,
всеэлементарныедизъюнкциипопарноразличны,
полученнаятождественнаяформула
находитсявСКНФ.
в.) Задаемтабличным
способомсоответствующуюбулеву19 функцию{И= 1,
Л
= 0}.
X Y Z Y&Z (Y&Z) Z
Z⊃X (Y&Z) ~ (Z⊃X)
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
г.) ОпределяемСДНФ
иСКНФтабличным
способом:
СДНФ
Выберем
втаблицесоответствующейбулевойфункции
всетестроки, в
которых
fA
= (Y&Z) ~
(Z⊃X)= 1:
X Y Z Y&Z (Y&Z) Z
Z⊃X (Y&Z) ~ (Z⊃X)
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 произвольнаяn-местнаяфункция
измножества{0,
1}
Расчетная работа по дискретной математике
студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
7
Для
каждойизэтих
строкстроимассоциированныесними
элементарные
конъюнкции:
<1, 1, 0> !(X & Y &Z)
<1, 0, 1> !(X &Y
& Z)
<1, 0, 0> !(X &Y
&Z)
<0, 0, 1> !(X
&Y & Z)
Составляемдизъюнкцию, полученныхэлементарныхконъюнкций:
(X & Y &Z) V (X &Y & Z) V (X &Y &Z)
V (X &Y & Z),
полученнаятождественнаяформула
находитсявСДНФ
дляисходной.
СКНФ
Выберем
втаблицесоответствующейбулевойфункции
всетестроки, в
которых
fA
= (Y&Z) ~
(Z⊃X)≠ 1:
X Y Z Y&Z (Y&Z) Z
Z⊃X (Y&Z) ~ (Z⊃X)
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
Для
каждойизэтих
строкстроимассоциированныесними
элементарные
дизъюнкции:
<1, 1, 1> !(X
V Y VZ)
<0, 1, 1> !(X VY
V Z)
<0, 1, 0> !(X VY
V Z)
<0, 0, 0> !(X V Y V Z)
Составляемконъюнкцию, полученныхэлементарныхдизъюнкций:
(X
V Y VZ) & (X VY V Z)
& (X VY V Z) & (X V Y V Z)
полученнаятождественнаяформула
находитсявСКНФ
дляисходной.
СравниваемсоСДНФ
иСКНФ, полученнымив
пункте«б».
СДНФ
(X &Y
& Z) V (X &Y&Z) V (X
& Y & Z) V (X & Y &Z) тождественными
преобразованиями,
(X & Y &Z) V (X &Y & Z) V (X &Y &Z)
V (X &Y & Z) " по
таблице,
видно, чтополученныеСКНФразличны
толькорасположениемэлементарных
дизъюнкций.
СКНФ
Расчетная работа по дискретной математике
студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
8
(X VY
V Z) & (X VY
V Z) & (X V Y V Z) & (X V Y V Z) тождественными
преобразованиями,
(X
V Y VZ) & (X VY V Z)
& (X VY V Z) & (X V Y V Z) " потаблице,
различны
толькорасположениемэлементарныхконъюнкций.
д.) ОпределениеминимальнойДНФ.
ПользуемсяметодомБлейка
определяемсокращеннуюДНФ.
1-йэтап.
Воспользуемсяполученнойформулой, находящейсяв
СДНФотносительно
списка
переменных
(X &Y
& Z) V (X &Y&Z) V (X
& Y & Z) V (X & Y &Z).
2-йэтап.
Применяем
правилообобщенногосклеивания20:
Записываемвсевозможные
склеиванияэлементарныхконъюнкций.
(X & (Y
& Z)) V (X
& (Y & Z)) ≡
(X &Y & Z) V (X & Y
& Z) V (Y & Z),
((X &Y)
& Z) V ((X &Y)
&Z) ≡ (X &Y
& Z) V (X &Y
&Z) V (X &Y),
(X &Y
& Z) V (X & Y &Z)
no,
(X &Y&Z) V (X & Y &Z) ≡ (X
&Y&Z) V (X & Y &Z) V (X & Z),
(X &Y&Z) V (X
& Y & Z) no,
(X
& Y & Z) V (X & Y &Z) no.
В
результатеполучаемформулу, находящуюсяв
ДНФивыражающую
функцию
fA:
(X &Y
& Z) V (X & Y & Z) V (Y & Z) V (X &Y & Z) V (X &Y &Z)
V (X
&Y)
V (X &Y&Z) V (X & Y &Z) V (X & Z) ≡
3-йэтап. Применяемзаконы
идемпотентностии
поглощения:
≡
(Y & Z) V (X &Y) V (X & Z), котораяотличаетсятолькорасположением
конъюнктивныхчленовот
полученнойформулыв
ДНФ≡ (Z &Y)
V (X &Y) V
(X & Z).
Получили
сокращеннуюформулу, находящуюсяв
ДНФ:
(Y
& Z) V (X &Y)
V (X & Z)
Дальнейшиесклеиванияневозможны, таккак
вэлементарныхконъюнкциях
переменныеразноименные.
ОпределяемминимальнуюДНФ
сиспользованиеядровых
импликантов.
(Y
& Z) V (X &Y)
V (X & Z)
20 (A & B) V (A & B) ≡ (A
& B) V (A & B) V B – правило______обобщенного склеивания.
Расчетная работа по дискретной математике
студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
9
Выделим
ядровыеимпликанты,21 дляэтого
составимтаблицузначений
для
простых
импликантовбулевойфункции
fA(X, Y, Z)
X Y Z Y
Z fA(X, Y, Z) Y
& Z X &Y
X & 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
Из
таблицывидно, чтооценка
<1, 0, 0> являетсясобственной22 оценкойдля
Y & Z, аоценка
<0, 0, 1> - дляX & Z,
т.е. этиимпликантыявляютсяядровыми
и
войдутвминимальнуюДНФ.
РассмотримV
найденныхядровых
импликантов: (Y & Z) V (X & Z). Вкаждой
изстрокс
номерами2,
4,5,6 в
которых
fA
принимаетзначение1, содержится, покрайней
мере,
однаединицав
столбцах
соответствующихX & Z
иY & Z, т.е.
указанныеимпликанты
«покрывают» булевуфункцию
fA.
ОпределилиминимальнуюДНФ: (Y & Z) V (X & Z).
Строим
переключательнуюсхему, соответствующуюнайденной
минимальной
ДНФ
(Y & Z) V (X & Z):
(Y
& Z) V (X & Z)
21 Допустимойконьюнкциейилиимликантомбулевойфункции
fA
(X1, X2,
… Xn)
называетсяэлементарная
коньюнкцияC ≠ 0 сосписком
переменных<
X1,
X2,
… Xn >
такая,
чтоC
V fA ≡ fA.
Импликантназывается
простым, еслипосле
отбрасываниялюбойпеременнойизC получаетсяэлементарнаяконьюнкция, не
являющаясяимпликантом.
Простой
импликантбулевойфункции
fA
называетсяядровым, еслиудаление
егоизсокращеннойДНФфункции
fA приводитк
ДНФ,
котораянеравносильнаисходнойДНФ.
22 Простойимпликант
являетсяядровымтогда
итолькотогда, когдасуществуетоценка
спискапеременных, на
которой
онимеетзначение
1 аостальные
простыеимпликантыпринимают
значение0.
Z
X Z
Y
Расчетная работа по дискретной математике
студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
10
е.) Строиммногочлен
Жегалкина23.
1-йэтап. : (Y&Z) ~
(Z ⊃ X), избавляемсяот
знаков~,
⊃V используя
равносильностиA ⊃ B ≡ (A
& B), A~B ≡ A+B+124,
AVB ≡ (A &B)
–
(Y&Z) ~
(Z ⊃ X) ≡ (Y&Z) + (Z
⊃ X) + 1 ≡ (Y&Z) +
(Z & X) + 1 ≡
2-йэтап. & Заменяемна
« ! »,
A наA+1.
3-йэтап. Раскрываемскобки.
≡
(YZ) + ((Æ + 1)(X + 1)) + 1 ≡ YZ + 1 + (ÆX + X + Z + 1) + 1 ≡
≡
YZ + 1 + ÆX + X + Z + 1 + 1 + 1 ≡
4-йэтап. Полученныймногочлен
упрощаем.
≡
YZ + ÆX+ X + Z.
Многочлен
Жегалкинадлязаданной
формулыимеетследующий
вид:
YZ + ÆX+ X + Z.
2. Проверить
правильностьрассуждений.
Если я встречу своего
приятеля,
то мы с ним пропустим
первое занятие. Либо я рано утром
поеду в институт,
либо
я пропущу первое
занятие.
Если я поеду рано
утром в
институт, то встречу своего
приятеля.
Следовательно, я
пропущу первое занятие
только тогда,
когда встречусь со
своим приятелем.
Решение:
встречусвоегоприятеля
–
X1; пропустим
первоезанятие– X2; я
рано
утром
поедувинститут
–
X3;
X1⊃X2, X3~X2, X3⊃X1
X1⊃X2
F = [(X1⊃X2)&(X3~X2)&(X3⊃X1)]⊃(X1⊃X2);
G = (X1⊃X2)&(X3~X2)
H = (X1⊃X2)&(X3~X2)&(X3⊃X1);
23 Многочлен
Жегалкина- МногочленЖегалкина
представляетсобойсумму
попарноразличныхчленов
вида
Xi1 Xi2 … Xik (0 < i1 < i2 < … < ik < n+1), а
такжесвободногочлена
d,
гдеd ∈{0, 1}.
24Логическоесложение– X+Y и
X&Y.
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
11
Составляемтаблицуистинности(23 = 8 строк):
X1 X2 X3 X1⊃X2 X3~X2 X3⊃X1 G H F
И
ИИИ
ИИИ
ИИ
И
ИЛИ
ЛИЛ
ЛИ
И
ЛИЛ
ЛИЛ
ЛИ
И
ЛЛЛ
ИИЛ
ЛИ
Л
ИИИ
ИЛИ
ЛИ
Л
ИЛИ
ЛИЛ
ЛИ
Л
ЛИИ
ЛЛЛ
ЛИ
Л
ЛЛИ
ИИИ
ИИ
Рассуждениеправильно, так
какформулатождественноистинная(см.
построеннуювышетаблицу).
В
случаебольшегочисла
высказывательныхпеременным(>3)
можнопроверить
следующим
образом(доказательствоот
противного): ПустьF не
тождественно
истинная
формула, тогдав
силусвойствконьюнкцииполучаем, что:
[(X1⊃X2) & (X3~X2) & (X3⊃X1)] ⊃ [X1⊃X2]
Но
таккакX1⊃X2 = И, то
приходимкпротиворечию,
чтоидоказывает
правильностьрассужденийи
истинностьформулы.
Начальные понятия
теории множеств.
3. Доказать
тождество.
(A B) C = (A
C) (B C). 25
25 AB – Относительноедополнениемножества
B
домножестваA
ИИИл
л
И
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
12
Множества,
стоящиевлевой
иправойчастях
равенстваизображаемс
помощью
диаграммЭйлера– Венна:
Рис.
1
AB – все
элементыA, которыене
принадлежатB.
Рис.
2
(A B) C - все
элементыA B,
которые
непринадлежатC
Рис.
3
(A B) C
Рис.
4
A C - все
элементыA,
которые
непринадлежатC.
Рис.
5
B C – все
элементыB, которыене
принадлежатC.
A
C
B
U
A
C
B
U
A
C
B
U
A
C
B
U
U
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
13
Рис.
6
(A C) (B C) –
всеэлементыA C,
которые
непринадлежатB C.
Рис.
7
(A C) (B C)
Рис.
3 и7 иллюстрируютравенство
множеств(A B) C и(A C) (B C).
Решение-2
(попринадлежностиэлемента):
Пустьx∈(AB)C ⇒ x∈AB x∉C ⇒
x∉C и(x∈A иx∉B)
x∈A, x∉B, x∉C ⇒ x∈AC иx∉BC ⇒x∈(AC)(BC)
x∈(AC)(BC) ⇒ x∈AC и
x∉BC ⇒ x∈A, x∉C и
x∉BC
x∈A, x∉B, x ∉C ⇒ x∈(AB)C.
Решение-3
(методтождественныхпреобразований)
(A C) (B C) = (A"C)"
(B "C) = A"C
" (B #C) = (A"C
" B) #(A"C
"C) = A"C
" B
=
= (A B) C.
Решение-4
(методхарактеристическойфункции)
∉
∈
=
x A
x A
A
0,
1,
á ;
A#B A B A"B á =á +á −á ;
A
B A B á =á
⋅á "
1 . A
A á = −á
= = ⋅ ⋅ = ⋅ (1−
) ⋅ (1− )
= (
− ⋅ ) ⋅
(1− )
= ( AB)C
A B C A B C A B C A A B C á
á á á á á á á á
á á á "
"
( ); A A C A B A
B C = á
−á ⋅á −á ⋅á +á ⋅á ⋅á
= = ⋅ (1− )
⋅ = ⋅ (1−
) ⋅ (
+ − )
= ( AC)(BC) A"C"(B"C) A
C B#C
A C B C B"C
á á á á á
á á á á á
= ⋅ (1− )
⋅ (
+ − ⋅ ) = ⋅
(1− )
⋅ (1− + − (1−
) ⋅ )
= A C B C B C A C B C B C á á á á á
á á á á á á á
= (
− ⋅ ) ⋅
(1− + − ( −
)) = (
− ⋅ ) ⋅
(1− + − + ) = 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 (á á á )
(1 á á á ) á á á á á á á á
á á á á á á á
A
A B A B C A C =á −á á +á ⋅á ⋅á −á ⋅á
A
C
B
U
U
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
14
Решение-5
(логическийметод)
A# B→ XVY; A" B→ X
&Y; A→ X
(A C) (B C) = (A"C) "(B "C) =(X&Z)&(Y&Z)=X&Z&(YVZ) = G;
(A B) C = A"C
" B
=X&Z&Y = I;
Составляемтаблицуистинности(23=8 строк):
X Y Z Y Z
YVZ X&Z G I
И
ИИЛ
ЛИЛ
ЛЛ
И
ИЛЛ
ИЛИ
ЛЛ
И
ЛИИ
ЛИЛ
ЛЛ
Л
ИИЛ
ЛИЛ
ЛЛ
Л
ЛИИ
ЛИЛ
ЛЛ
Л
ИЛЛ
ИЛЛ
ЛЛ
И
ЛЛИ
ИИИ
ИИ
Л
ЛЛИ
ИИЛ
ЛЛ
У
правойилевой
частейдоказываемоготождества
формулылогики
высказываний,
соответствующиеэтим
частямравносильны.
Отношения и
функции.
4. Задано
бинарноеотношениеñ = {<1, 1>, <1, 4>, <2,
2>, <2, 3>, <2, 4>, <3, 3>,
<3, 4>,
<4, 4>}
на
множествеX = {1, 2, 3, 4}. Являетсяли
онорефлексивным,
симметричным,
антисимметричным, транзитивным?
Найти
D(ñ), R(ñ), ñ−1, ñ2 или(ñ ï ñ).
Изобразитеуказанноебинарное
отношениенакоординатнойплоскости.
Решение:
Пользуясь
определениемирассматриваяпервыеи
вторыекомпоненты
упорядоченныхпар, находимсоответственно:
- область
определениязаданногоотношения
ñ
D(ñ) = {x ∈X | ∃ y ∈X, !
- область
___________значенийзаданногоотношения
ñ
R(ñ) = {y ∈
X
| ∃ x ∈
X,
!
Находим
обратноеотношениеñ-1 кзаданному
ñ:
- ñ-1 = {
= {<1, 1>,
<4, 1>, <2, 2>, <3, 2>, <4, 2>, <3, 3>, <4,
3>, <4, 4>}.
Для
нахождениякомпозицииñïñ составляемтаблицу:
ñ2 = ñïñ = {
26 “!” - следует
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
15
<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>,
<1, 4>, <2, 2>, <2, 3>, <2, 4>, <3, 3>, <3,
4>, <4, 4>}.
Отношение
ñ рефлексивно, так
какx ñ x
для∀x ∈ X:
<1, 1>,
<2, 2>, <3, 3>, <4, 4>, кромеэтого
отношениеравенстваIX на
множестве
X
таково, чтоIX = {
= {<1, 1>,
<2, 2>, <3, 3>, <4, 4>} ⊆
ñ. 27
Условие
IX ⊆ ñ являетсянеобходимыми
достаточнымдлятого,
чтобыñ
было
рефлексивно.
Отношение
ñ несимметрично, так
какx ñ y
не! y ñ x
для∀x, y∈X:
например
<1,
4> ∈ ñ,
но<4, 1> ∉ ñ.
Кромеэтого, ñ-1 ⊄ñ, таккак
ñ-1 = {<1, 1>, <4, 1>, <2,
2>, <3, 2>, <4, 2>, <3, 3>, <4, 3>, <4, 4>} ⊄ñ = {<1,
1>,
<1, 4>,
<2, 2>, <2, 3>, <2, 4>, <3, 3>, <3, 4>, <4,
4>} !
напримеруже<4, 1>∈ñ-1,
но
<4,
1>∉ñ.
Условие
ñ-1 ⊆ñ являетсянеобходимыми
достаточнымдлясимметричности
отношения
ñ, но
ононевыполняется,
такжекакне
выполняютсяусловияñ⊆ñ-1
! ñ-1=ñ.
Отношение
ñ транзитивно, так
какx ñ y
иy ñ z
! x ñ z для∀x, y, z ∈X:
<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>
27 ⊆ - символотношения
включенияодногомножества
вдругое
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.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
Действительно,
ñïñ ⊆ñ,
болеетогоñïñ = ñ:
ñïñ = {<1, 1>,
<1, 4>, <2, 2>, <2, 3>, <2, 4>, <3, 3>, <3,
4>, <4, 4>}=
= ñ = {<1, 1>, <1, 4>, <2,
2>, <2, 3>, <2, 4>, <3, 3>, <3, 4>, <4, 4>}, что
является
необходимымидостаточнымусловиемтранзитивностиñ.
Отношение
ñ антисимметрично, так
какx ñ y
иy ñ x
! x = y для∀x, y∈X:
x y y x
<1, 1> и
<1,
1> !
1
= 1,
<1, 4> <4,
1> ∉ ñ,
<2, 2> и
<2,
2> !
2
= 2,
<2, 3> и
<3,
2> ∉ñ,
<2, 4> и
<4,
2> ∉ñ,
<3, 3> и
<3,
3> !
3
= 3,
<3, 4> и
<4,
3> ∉ ñ,
<4, 4> и
<4,
4> !
4
= 4.
ñ"
ñ-1 ⊆IX 28 : чтовыполняется–
ñ" ñ-1
=
{<1, 1>, <2, 2>, <3, 3>, <4, 4>} = IX.
Изображаемнакоординатнойплоскостизаданное
бинарноеотношение:
ñ = {<1, 1>, <1, 4>, <2,
2>, <2, 3>, <2, 4>, <3, 3>, <3, 4>, <4, 4>}
5. График
функцииf(x) представляетсобой
ломаную, звеньякоторой
параллельныкоординатнойоси
x,
либобиссектрисамкоординатныхуглов
(угловые
коэффициентызвеньевравны
±1 или0). Координатыкаждой
вершины
ломанойявляютсяцелыми
числами. f(x) определяетотношение
ñf
на
множествеX = [0..5 : x1ñfx2 ⇔29 f(x1) = f(x2)]. Докажите
ñf
эквивалентностьнаX. Перечислитевсеклассы
эквивалентности30.
Решение:
Докажем
эквивалентностьзаданного
отношенияñf
наX:
ñf – рефлексивно, так
какf(x) = f(x),
ñf – симметрично, так
какf(x1) = f(x2) ! f(x2) = f(x1),
ñf – транзитивно, так
какf(x1) = f(x2) иf(x2) = f(x3) ! f(x1) = f(x3)
28 " - символпересечениямножеств(A" B = {x | x∈A иx∈B})
29 ⇔- тогдаи
толькотогда, когда
выполняетсяусловие…
30 Классом
эквивалентности, порожденнымэлементом
a,
называетсяподмножество[a]ñ={t∈A|
añt}
Классы
эквивалентности:
[a]ñ ∈[0; 1) {a, 5 - a},
[a]ñ ∈
[1],
[3, 4] {1} # [3,
4],
[a]ñ ∈
(1,
2) {a, 4 – a},
[a]ñ ∈
[2]
{2}
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
17
I
E
G H
B
D F
A
C
Специальные
бинарные отношения.
6. В
частичноупорядоченноммножестве31, заданном
диаграммой32, найдите
наибольший,
наименьший, минимальный, максимальныйэлементы.
Продолжитезаданноеотношение
частичногопорядкадо
линейного33.
Решение:
наибольшегоэлементанет.
наименьшийэлемент, он
минимальный– A,
максимальныеэлементыI и
H,
Линейный
порядокможетбыть
напримерследующимE, D, F, C, I, G,
B, A, H.
=
( , )
( , )
( , ) ( , )
( , ) ( , )
( , ) ( , ) ( , )
( , ) ( , ) ( , )
( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( ,
)
( , ) ( , ) ( , ) ( , )
( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( ,
) ( , ) ( , )
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 Частично
упорядоченноемножество
–
этомножествос
заданнымнанем
частичным(линейным) порядком.
Рефлексивное,
антисимметричноеи
транзитивноеотношениеназываетсяотношениемчастичногопорядкана
множестве
X
иобозначаетсясимволом
«$ ».
32 НазываетсядиаграммойХассе:
схема, гдекаждый
элементизображаетсяточкой,
иеслиy покрывает
x,
то
соответствующиеточкисоединяют
линией, иx располагаютнижеy.
Говорят,
чтоэлементy покрывает
элементx, еслине
существуеттакогоэлемента
u,
чтоx $ u$ y.
33 Отношение
линейногопорядка–если
длялюбогоэлемента
частичноупорядоченногомножества
выполняется
одно
изусловийx≤ y илиy≤ x, томножество
называетсялинейноупорядоченным.
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
18
Элементы
теории графов и сетей.
7. Матрица
смежностиданногоорграфа
имеетвид
0 0 0 0
1 1 0 0
1 0 0 1
0 1 0 1
не
решать.
8. Используя
алгоритмТери34 определитьзамкнутыймаршрут,
проходящий
ровно
подвараза,
поразув
каждомнаправлении, через
каждоеребрографа.
Решение:
V1!V5!V4!V3!V2!V1!V2!V5!V2!V3!V4!V5!V1.
34 Алгоритм
Тери:
- отмечаем
прохождениеребрав
некоторомнаправлении
- второй
развэтом
направлениинедвижемся
- особо
отмечаемребро, по
которомузаходимв
вершинупервыйраз
- по
особоотмеченномуребру
вобратномнаправлениидвижемся, если
толькодругихвозможностейнет.
V4
V3
V2
V1 V5
V4
V3
V2
V1 V5
1
2
3
4
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
19
9. Используя
алгоритмфронтаволны,
найтивсеминимальныепутииз
1-й
вершины
впоследнюювершину
орграфазаданногоматрицей
смежности.
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 заданногоориентированногографа, где
указанывсе
вершины,
достижимыеизV1: минимальныйпуть= 5, число
минимальных
путей
–
2.
35 Подграфом графа
называетсяграф, являющийсяподмодельюисходного
графа. Иначеговоря,
подграф
содержит
некоторыевершиныисходного
графаинекоторые
рёбра(толькоте,
обаконцакоторых
входятв
подграф).
V1
V6 V5
V4
V2
V3
V7
Минимальные
пути:
V1!V5!V4!V2
!V3!V7 или
V1!V6!V4!V2
!V3!V7
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
20
10. Используя
алгоритмФорда-Белмана
найтивсеминимальныепути36 из
первой
вершинывовсе
достижимыевершинынагруженного37
орграфа,
заданного
матрицейдлиндуг38.
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
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.39 При
этом, если
(n−1) =
∞
i
ë
, то
вершинаVi
недостижимаиз
V1.
(k
)
i
ë
- определяетсяследующимобразом:
) 0 (
1ë = 0, ) 0 (
i
ë = ∞, i = 2, … n;
(считаем
любойпутьиз
v
вv путем
нулевойдлины)
при
i
= 2, .. n, k≥
0
справедливоравенство( 1) min{ ( ) }
ji
k
j
k
i
ë + = ë + c , 1 ≤
j
≤ n
а
приi = 1, k≥ 0
справедливоравенствоmin{0;min{ }} 1
) ( ) 1 (
1 j
k
j
ë k + = ë + c , 1 ≤
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 называетсяминимальным,
еслионимеет
минимальнуюдлинупо
сравнениюсовсеми
путямиизv
вw.
37 Орграф
D
= (V, X), V = {v1,
v2,
… vn},
n ≥ 2
называютнагруженным, если
намножестведуг
X
определена
некоторая
функцияl: X! R, называемуювесовой, т.е.
длякаждойдуги
x
∈ X
поставленовсоответствие
некоторое
действительноечисло
l(x)
–
длинадугиx.
38 Матрица
длиндуг– квадратнаяматрица, порядка
n:
∞ ∉
∈
=
, ( , ) .
( , ), ( , ) ;
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 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
21
В
данномслучае1 ≤
j
≤ 8
:
k = 1
) 1(1ë
∞
∞
∞
8
5
7
4
6
1 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
! }} min{ ; 0 min{ ) 1(1
∞
∞
∞
∞
∞
∞
∞
∞
ë = = 0;
(1)
2 ë
∞
∞
∞
∞
∞
∞
6
7
2 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
7
! }
7
(1) min{
2
∞
∞
∞
∞
∞
∞
∞
ë = = 7;
(1)
3 ë
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
! }
1
(1) min{
3
∞
∞
∞
∞
∞
∞
∞
ë = = 1;
Расчетная работа
по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
22
(1)
4 ë
∞
∞
∞
∞
∞
∞
3
5
4 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
! (1) min{ }
4
∞
∞
∞
∞
∞
∞
∞
∞
ë = = ∞;
(1)
5 ë
∞
∞
∞
∞
∞
∞
1
4
5 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
! (1) min{ }
5
∞
∞
∞
∞
∞
∞
∞
∞
ë = = ∞;
(1)
6 ë
∞
∞
∞
∞
∞
11
3
2
6 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
2
! }
2
(1) min{
6
∞
∞
∞
∞
∞
∞
∞
ë = = 2;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
23
(1)
7 ë
∞
∞
∞
∞
∞
∞
2
2
7 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
! (1) min{ }
7
∞
∞
∞
∞
∞
∞
∞
∞
ë = = ∞;
(1)
8 ë
∞
∞
∞
∞
∞
5
2
6
8 V
+
∞
∞
∞
∞
∞
∞
∞
0
(0)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
! (1) min{ }
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{ ) 2 (
1
∞
∞
∞
∞
∞
∞
ë = = 0;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
24
(2)
2 ë
∞
∞
∞
∞
∞
∞
6
7
2 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
8
7
! }
8
7
(2) min{
2
∞
∞
∞
∞
∞
∞
ë = = 7;
(2)
3 ë
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
! }
1
(2) min{
3
∞
∞
∞
∞
∞
∞
∞
ë = = 1;
(2)
4 ë
∞
∞
∞
∞
∞
∞
3
5
4 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
5
6
! }
5
6
(2) min{
4
∞
∞
∞
∞
∞
∞
ë = = 5;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
25
(2)
5 ë
∞
∞
∞
∞
∞
∞
1
4
5 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
∞
! (2) min{ }
5
∞
∞
∞
∞
∞
∞
∞
∞
ë = = ∞;
(2)
6 ë
∞
∞
∞
∞
∞
11
3
2
6 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
4
2
! }
4
2
(2) min{
6
∞
∞
∞
∞
∞
∞
ë = = 2;
(2)
7 ë
∞
∞
∞
∞
∞
∞
2
2
7 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
9
! }
9
(1) min{
7
∞
∞
∞
∞
∞
∞
∞
ë = = 9;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
26
(2)
8 ë
∞
∞
∞
∞
∞
5
2
6
8 V
+
∞
∞
∞
∞
2
1
7
0
(1)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
13
! }
13
(2) min{
8
∞
∞
∞
∞
∞
∞
∞
ë = = 13;
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{ ) 3 (
1
∞
∞
∞
ë = = 0;
(3)
2 ë
∞
∞
∞
∞
∞
∞
6
7
2 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
8
7
! }
8
7
(3) min{
2
∞
∞
∞
∞
∞
∞
ë = = 7;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
27
(3)
3 ë
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
! }
1
(3) min{
3
∞
∞
∞
∞
∞
∞
∞
ë = = 1;
(3)
4 ë
∞
∞
∞
∞
∞
∞
3
5
4 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
5
6
! }
5
6
(3) min{
4
∞
∞
∞
∞
∞
∞
ë = = 5;
(3)
5 ë
∞
∞
∞
∞
∞
∞
1
4
5 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
10
9 ! }
10
9
(3) min{
5
∞
∞
∞
∞
∞
∞
ë = = 9;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.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) min{
6
∞
∞
∞
∞
∞
ë = = 2;
(3)
7 ë
∞
∞
∞
∞
∞
∞
2
2
7 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
7
9
! }
7
9
(3) min{
7
∞
∞
∞
∞
∞
∞
ë = = 7;
(3)
8 ë
∞
∞
∞
∞
∞
5
2
6
8 V
+
∞
13
9
2
5
1
7
0
(2)
j
ë
=
∞
∞
∞
∞
∞
∞
14
13
! }
14
13
(3) min{
8
∞
∞
∞
∞
∞
∞
ë = = 13;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.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{ ) 4 (
1
∞
∞
∞
ë = = 0;
(4)
2 ë
∞
∞
∞
∞
∞
∞
6
7
2 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
∞
8
7
! }
8
7
(4) min{
2
∞
∞
∞
∞
∞
∞
ë = = 7;
(4)
3 ë
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
! }
1
(4) min{
3
∞
∞
∞
∞
∞
∞
∞
ë = = 1;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.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) min{
4
∞
∞
∞
∞
∞
∞
ë = = 5;
(4)
5 ë
∞
∞
∞
∞
∞
∞
1
4
5 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
∞
8
9 ! }
8
9
(4) min{
5
∞
∞
∞
∞
∞
∞
ë = = 8;
(4)
6 ë
∞
∞
∞
∞
∞
11
3
2
6 V
+
13
7
2
9
5
1
7
0
(3)
j
ë
=
∞
∞
∞
∞
∞
24
4
2
! }
24
4
2
(4) min{
6
∞
∞
∞
∞
∞
ë = = 2;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.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) min{
7
∞
∞
∞
∞
∞
∞
ë = = 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) min{
8
∞
∞
∞
∞
∞
ë = = 11;
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{ ) 5 (
1
∞
∞
∞
ë = = 0;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.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) min{
2
∞
∞
∞
∞
∞
∞
ë = = 7;
(5)
3 ë
∞
∞
∞
∞
∞
∞
∞
1
3 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
∞
∞
1
! }
1
(5) min{
3
∞
∞
∞
∞
∞
∞
∞
ë = = 1;
(5)
4 ë
∞
∞
∞
∞
∞
∞
3
5
4 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
∞
5
6
! }
5
6
(5) min{
4
∞
∞
∞
∞
∞
∞
ë = = 5;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.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) min{
5
∞
∞
∞
∞
∞
∞
ë = = 8;
(5)
6 ë
∞
∞
∞
∞
∞
11
3
2
6 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
22
4
2
! }
22
4
2
(5) min{
6
∞
∞
∞
∞
∞
ë = = 2;
(5)
7 ë
∞
∞
∞
∞
∞
∞
2
2
7 V
+
11
7
2
8
5
1
7
0
(4)
j
ë
=
∞
∞
∞
∞
∞
∞
7
9
! }
7
9
(5) min{
7
∞
∞
∞
∞
∞
∞
ë = = 7;
Расчетная
работа по дискретной математике
студента группы
18-101 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.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 Чумина Олега www.chuminoleg.boom.ru
Вариант №19.
63
Литература:
1. НефедовВ.Н.,
ОсиповаВ.А.
Курсдискретнойматематики.
– М.:
Издательство
МАИ,
1992.
2. Методическиеуказанияпо
выполнениюрасчетныхработпо
дискретнойматематике. Под. Ред. Осиповой.__