База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

курсовые,контрольные,дипломы,рефераты

Расчетная работа по дискретной математике — Математика

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Кафедра №805

«Математическая кибернетика»

Вариант №19

Расчетная работа по дискретной математике

Студент: Чумин Олег

Группа: №18-101

Преподаватель: доцент Рыбин

Владимир

Васильевич.

- 2000…2001 гг. -

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

2

Элементы математической логики и теории булевых функций.

1. Определить для заданной формулы логики высказываний:

а.) Определить таблицу истинности.

б.) ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований.

в.) Задать табличным способом соответствующую булеву функцию.

г.) Найти СДНФ и СКНФ табличным способом (сравнить со СДНФ, СКНФ,

полученными в пункте «б»).

д.) Указать минимальную ДНФ и соответствующую ей переключательную

схему.

е.) Построить многочлен Жегалкина.

Формула - (Y&Z) ~ (Z⊃X).1

Решение:

а) Определяем таблицу истинности.

Придавая каждой переменной формулы одно из истинностных значений

{И, Л}2 и учитывая, что каждое вхождение знака  относится к наикратчайшей

подформуле, следующей за ним. Список переменных формулы содержит три 3

переменных – ! ∃23 = 8 – оценок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 VB – первый закон де Моргана, (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) VX)] &

& [((Z V X) V Y) & ((Z V X) V Z))] & [((Z V X) V Z) & ((Z V X) VX)] ≡

≡ (Y V Z V Y) & (Y V Z V Z) & (Y V Z V Z) & (Y V Z VX) &

& (Z V X V Y) & (Z V X V Z) & (Z V X V Z) & (Z V X VX) ≡

≡ (Y V Z V Y) & (Y V Z V Z) & (Y V Z V Z) & (Y V Z VX) &

& (Z V X V Y) & (Z V X V Z) & (Z V X V Z) & (Z V X VX) ≡

полученная формула находится в КНФ, воспользовавшись законом

индемпотентности V16, получаем следующий сокращенный вид формулы:

≡ (Y V Z V Y) & (Y V Z V Z) & (Y V Z) & (Y V Z VX) &

& (Z V X V Y) & (Z V X) & (Z V X V Z) & (Z V X VX) ≡

теперь применяем 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)&(AVB) – 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 VY V Z) & (X VY V Z) & (X V Y V Z) & (X V Y V Z) ≡

6-й этап.

≡ (X VY V Z) & (X VY 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 VZ)

<0, 1, 1> !(X VY V Z)

<0, 1, 0> !(X VY V Z)

<0, 0, 0> !(X V Y V Z)

Составляем конъюнкцию, полученных элементарных дизъюнкций:

(X V Y VZ) & (X VY V Z) & (X VY 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 VY V Z) & (X VY V Z) & (X V Y V Z) & (X V Y V Z) тождественными

преобразованиями,

(X V Y VZ) & (X VY V Z) & (X VY 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# BXVY; A" BX &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, ! ∈ ñ} = {1, 2, 3, 4};26

- область ___________значений заданного отношения ñ

R(ñ) = {y ∈ X | ∃ x ∈ X, ! ∈ ñ} = {1, 2, 3, 4}.

Находим обратное отношение ñ-1 к заданному ñ:

- ñ-1 = { | ∈ ñ} =

= {<1, 1>, <4, 1>, <2, 2>, <3, 2>, <4, 2>, <3, 3>, <4, 3>, <4, 4>}.

Для нахождения композиции ñïñ составляем таблицу:

ñ2 = ñïñ = { | y ∈ X, ! ∈ ñ и ∈ ñ}

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 = { | x∈X } =

= {<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, k0 справедливо равенство ( 1) min{ ( ) }

ji

k

j

k

i ë + = ë + c , 1 ≤ j n

а при i = 1, k0 справедливо равенство min{0;min{ }} 1

) ( ) 1 (

1 j

k

j

ë k + = ë + c , 1 ≤ j n

36 Путь – последовательность вершин и дуг в орграфе v1x1v2x2v3x3…xkvk+1, где k 1, viV, i = 1, … , k+1, xjX, 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 (

          

          

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 (

          

          

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 (

          

          

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 (

          

          

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

ë(n1) = ë

i = 7 выражает длину минимального пути из V1 в V2.

Определяем минимальное число k11, при котором выполняется равенство

(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.

Определяем минимальное число k11, при котором выполняется равенство

(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.

Определяем минимальное число k11, при котором выполняется равенство

(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.

Определяем минимальное число k11, при котором выполняется равенство

(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

Определяем минимальное число k11, при котором выполняется равенство

(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.

Определяем минимальное число k11, при котором выполняется равенство

(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.

Определяем минимальное число k11, при котором выполняется равенство

(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. Методические указания по выполнению расчетных работ по

дискретной математике. Под. Ред. Осиповой.__

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) Кафедра №805 «Математическая кибернетика» Вариант №19 Расчетная работа по дискретной математике Студент: Чумин Олег Группа: №18-101 Преподаватель: д

 

 

 

Внимание! Представленная Работа находится в открытом доступе в сети Интернет, и уже неоднократно сдавалась, возможно, даже в твоем учебном заведении.
Советуем не рисковать. Узнай, сколько стоит абсолютно уникальная Работа по твоей теме:

Новости образования и науки

Заказать уникальную работу

Похожие работы:

Формулы по алгебре
Статистика (шпаргалка 2002г.)
Комплексные числа и действия с ними
Треугольник РЕЛО (Трикутник Рьоло)
Задача коммивояжера
Программа государственного экзамена по математике для студентов математического факультета Московского городского педагогического университета
Теорема Безу
Дискретная математика (Конспекты 15 лекций)
Разбиения выпуклого многоугольника
Построение решения задачи Гурса для телеграфного уравнения методом Римана

Свои сданные студенческие работы

присылайте нам на e-mail

Client@Stud-Baza.ru