авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 |
-- [ Страница 1 ] --

Министерство образования Республики Беларусь УДК 681.3.06+519.6(075.8)

ББК 32.973я73

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

Р32

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

ИМЕНИ ЯНКИ КУПАЛЫ»

Рецензенты: кандидат физико-математических наук, доцент кафед-

ры технической механики и материаловедения ГГАУ А.А.Денисковец;

кандидат физико-математических наук, доцент кафед ры дифференциальных уравнений и оптимального управления ГрГУ им. Я.Купалы З.М.Наркун.

Рекомендовано советом Института последипломного образования ГрГУ им. Я.Купалы.

Ревчук, И.Н.

И.Н. РЕВЧУК, В.К. ПЧЕЛЬНИК Прикладная математика : пособие / И.Н.Ревчук, ПРИКЛАДНАЯ МАТЕМАТИКА Р32 В.К.Пчельник. – Гродно : ГрГУ им. Я.Купалы, 2007. — 128 с.

Пособие для студентов специальности ISBN 978-985-417-911- 1-40 01 01– ПОИТ В пособии содержатся теоретический материал, примеры и задания по следующим разделам курса «Дискретная математика»: теория множеств, логика высказываний, нахождение минимального дерева-остова, построение кратчайших путей в графе, нахождение максимального потока в сети, решение задачи комми вояжера. Показаны возможности использования электронных таблиц MS EXCEL и надстройки «Поиск решения» для решения указанных типов задач.

УДК 681.3.06+519.6(075.8) ББК 32.973я Гродно © Ревчук И.Н., Пчельник В.К., ISBN 978-985-417-911- © ГрГУ им. Я.Купалы, 1) А = А;

1. Множества 2) для любых множеств А, В, С, если А = В и В = С, то А = С;

3) для любых множеств А и В если А = В, то В = А.

Понятие множества является одним из основных понятий Если А В, то возможны два случая:

современной математики. Это понятие принимается в качестве 1. Существует хотя бы один элемент множества В, не при первоначального и поэтому не определяется через другие.

надлежащий множеству А. В таком случае говорят, что А – Георг Кантор выразил понятие множества следующим собственное подмножество множества В (строгое включение:

образом: «Множество есть многое, мыслимое как единое це А В).

лое».

2. Не существует ни одного элемента множества B, не при Множество можно задать непосредственным перечисле надлежащего A. Этот случай равносилен отношению А = В.

нием всех входящих в него элементов (в произвольном поряд ке). Но такой способ пригоден лишь для множеств с неболь- Определение. Объединени шим количеством элементов. Так, например, множество всех ем А В множеств А и В на цифр десятичной системы счисления можно представить так: зывается множество, состоящее {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Универсальным способом задания из всех тех и только тех эле множества является способ задания характеристических ментов, которые принадлежат свойств элементов этого множества: M [P (x)] – множество множеству А или множеству В.

x Математически это можно за всех таких х, что х обладает свойством Р. писать так:

Множество, не содержащее ни одного элемента, называ A B = M [x A или x B ], ется пустым и обозначается. Df x Пусть Р означает свойство «быть остатком от деления на = турального числа на 5». Тогда Р(х) – «остаток от деления нату где Df читается: «равно по определению».

рального числа на 5», а M [P( x)] = {0,1,2,3,4}.

x Определение. Пересе Два множества могут находиться в различных отно чением А В множеств А шениях.

и В называется множество, Определение. Множество А включается в множество В, состоящее из всех тех и если каждый элемент множества А является также и элемен только тех элементов, кото том множества В.

рые принадлежат как мно Отношение включения обозначается символом.

жеству А, так и множеству Свойства включения:

В. Математически это мож 1) А А;

но записать так:

2) для любых множеств А, В, С, если А В и В С, A B = M [x A x B ].

то А С;

3) А для всякого множества А. Df x Частным случаем включения является равенство.

Определение. Два множества А и В называются равными, если А В и В А (А = В).

Свойства равенства:

3 Определение. Разностью 1. Коммутативность:

между множеством А и 1.1. A B = B A ;

множеством В называется 1.2. A B = B A.

множество, состоящее из 2. Ассоциативность:

всех тех и только тех эле 2.1. A ( B C ) = ( A B) C ;

ментов множества А, кото рые не принадлежат множе- 2.2. A ( B C ) = ( A B) C.

ству В. Математически это 3. Дистрибутивность:

можно записать так:

3.1. A ( B C ) = ( A B) ( A C ) ;

A \ B = M [x A и x B ].

3.2. A ( B C ) = ( A B) ( A C ) ;

Df x 4. Идемпотентность:

Если А М, то разность М \ А называется дополнением 4.1. A A = A ;

множества А до множества М. Если М – универсальное мно 4.2. A A = A.

жество, то под A, B, C понимают дополнения множеств А, В и 5. Поглощение:

С до универсального:

5.1. A ( A B) = A ;

A = M [x A]. 5.2. A ( A B) = A.

Df x 6. Законы де Моргана:

Определение. Произведением А В множества А на 6.1. = ;

множество В называется множество всевозможных пар, пер вые элементы которых принадлежат А, а вторые – В:

6.2. =.

A B = M [x A и y B ].

7. Закон двойного отрицания: =.

Df ( x, y ) 8. Закон включения: если, то.

Пусть А={a, b, c}, B={n, p}. Тогда 9. Свойства нуля и единицы (нуль – пустое множество, еди А В ={(a, n), (a, p), (b, n), (b, p), (c, n), (c, p)}, В А ={(n, a), (n, b), (n, c), (p, a), (p, b), (p, c)}. ница – универсальное множество М):

9.1. A = A ;

Произведение двух множеств допускает распространение 9.2. A = ;

на большее число множеств:

9.3. A M = M ;

A1 A2... An = 9.4. A M = A.

Df [x1 A1, x2 A2,..., xn An ].

= 10. Выражение для разности:

M ( x1, x 2,..., x n ) \ B = A B.

Приведем основные свойства операций объединения, пе ресечения и дополнения.

5 Мощностью конечного множества А (обозначается А) б). Пусть n = 3, A, B и С – три пересекающихся множества.

В этом случае справедливо следующее соотношение:

называется число элементов этого множества. Например, мощность множества А = {1, 2} равна 2 (А= 2).

A B C = A + B + C A B AC B C + Пусть множество А содержит n элементов. Тогда мно- (2) жество всех подмножеств этого множества P(A) состоит из 2n + A B C.

элементов. Таким образом, P(A) = 2n.

Из рис. 2 видно, что Задача 1. 1. Определить мощности объединения конеч ных множеств для n = 2 и n = 3.

Решение. а). Пусть A и B – два пересекающихся множе ства. Докажем с помощью диаграммы Эйлера-Венна следую щее соотношение:

A B = A + B A B. (1) Из рис. 1 видно, что A B = n1 + n2 + n3, A = n1 + n2, B = n2 + n3, A B = n2.

Очевидно, что n1 + n2 + n3 = (n1 + n2 ) + (n2 + n3 ) n2, что и доказывает формулу (1).

Формула (1) справедлива и для случая, если множества Рисунок A и B не пересекаются. В этом случае A B = A + B.

A B C = n1 + n2 + n3 + n4 + n5 + n6 + n7, A = n1 + n2 + n4 + n5, B = n2 + n3 + n5 + n6, C = n4 + n5 + n6 + n7, A B = n2 + n5, A C = n4 + n5, B C = n5 + n6, A B C = n5.

Очевидно, что Рисунок 7 Найдем решение этой же задачи, используя надстройку n1 + n2 + n3 + n4 + n5 + n6 + n7 = (n1 + n2 + n4 + n5 ) + «Поиск решения» MS EXCEL. Для этого представим данные + ( n 2 + n3 + n 5 + n 6 ) + ( n 4 + n 5 + n 6 + n 7 ) на рабочем листе так, как на рис. 3.

(n2 + n5 ) (n4 + n5 ) (n5 + n6 ) + n5, что и доказывает формулу (2).

Формула (2) справедлива и для случая, если множества A, B и С попарно не пересекаются. В этом случае A B C = A + B + C.

Формулы вида (1) и (2) распространяются на случай n множеств. Если 1, 2, …, n — некоторые множества и 1, 2, …, n — мощности этих множеств соответственно, то A1 A2... An = A1 + A2 +... + An ( A1 A2 + A1 A3 +... A1 An +... + An 1 An ) + + ( A1 A2 A3 + A1 A2 A4 +... + An 2 An 1 An ) + +... + ( 1) n A1 A2... An.

= n1 + n2 + n3 + n4 + n5 + n6 + n7, Задача 1. 2. В группе спортсменов 30 человек. Из них 20 занимаются плаванием, 18 – легкой атлетикой и 10 – лыжа- = n1 + n2 + n4 + n5, ми. Плаванием и легкой атлетикой занимаются 11 человек, = n2 + n3 + n5 + n6, плаванием и лыжами – 8, легкой атлетикой и лыжами – 6 чело век. Сколько спортсменов занимаются всеми тремя видами = n4 + n5 + n6 + n7, спорта?

= n2 + n5, Решение. Исходя из условия, получаем, что = n4 + n5, = 30, = 20, = 18, = 10, = 11, = n5 + n6, = 8, = 6.

= n5.

Следовательно, 30 = 20 + 18 + 10 11 8 6 +, то есть 30 23 =, = 7.

9 Рисунок Целевую функцию разместим в ячейке В4 и установим равной 100-A2-B2-C2+D2+E2+F2-G2. Окна диалога надстрой ки и ее параметров при этом должны принять вид как на рис. 45.

Рисунок На рис. 6 приведено полученное решение.

Рисунок Рисунок Задача 1. 3. Найти количество целых положительных чи сел, не превосходящих 1000 и не делящихся нацело ни на одно из чисел 3, 5, и 7.

Решение. Пусть А, В, С — множества целых положи тельных чисел, не превосходящих 1000, делящихся нацело на 11 2. Предположим, что для некоторого элемента x имеет 3, 5, и 7 соответственно. Тогда АВ, АС, ВС, АВС — место соотношение x (AB) (AC). Докажем, что множества целых положительных чисел, не превосходящих x A (BC).

1000, делящихся нацело на15 = 35, 35 = 57, 21 = 37 и Действительно, пусть x (AB) (AC). Тогда xAB 105 = 357 соответственно. Тогда и одновременно x AC.

A BC = A + B + C A B AC BC + Пусть x A. Тогда x A (BC) (это верно для любых множеств В и С), и утверждение доказано.

1000 1000 1000 1000 1000 Если x A, то x B и x C, то есть, x BC. Но тогда + A BC = + + 3 5 7 35 3 7 x A (BC), что доказывает наше утверждение.

Доказательство тождеств можно проиллюстрировать с 1000 + = 333 + 200 + 142 66 47 28 + 9 = 543. помощью диаграмм Эйлера-Венна. На рис. 7 и 8 изображено 5 7 3 5 7 формирование левой части равенства A (BC). На рис. 9, 10 и 11 правой части (AB) (AC).

Следовательно, количество целых положительных чисел, не превосходящих 1000 и не делящихся нацело ни на одно из чи сел 3, 5, и 7, равно 1000 – 543 = 457.

Задача 1. 4. Доказать, что для любых множеств A, B и C выполняется соотношение A ( B C ) = ( A B) ( A C ).

Решение. Чтобы доказать некоторое тождество вида A = B, нужно доказать, что:

1) если xА, то xВ;

Рисунок Рисунок 2) если xВ, то x А.

Докажем свойство дистрибутивности для объединения, то есть, что A ( B C ) = ( A B) ( A C ).

1. Предположим, что для некоторого элемента x имеет место соотношение x A (BC). Докажем, что x принадле жит и правой части, т.е. x(AB) (AC).

Действительно, пусть x A (BC). Тогда либо xA, либо xBC. Рассмотрим каждую из этих возможностей.

а). Пусть xA. Тогда x A B и x A C (это верно для любых множеств B и C). Следовательно, x(AB) (AC).

б). Пусть x BC. Но тогда согласно определению пе Рисунок 9 Рисунок ресечения xB и xC). Поэтому xAB и x AC (это верно для любого множества А). Следовательно, x(AB) (AC).

13 2. В студенческой группе 20 человек. Из них 10 имеют оценку «девять» по английскому языку, 8 – по математике, 7 – по физике, 4 – по английскому языку и по математике, 5 – по английскому языку и по физике, 4 – по математике и по физи ке, 3 – по английскому языку, по математике и по физике.

Сколько студентов в группе не имеют оценок «девять»?

3. В классе 20 человек. На экзаменах по истории, математи ке и литературе 10 учеников не получили ни одной оценки «9», 6 учеников получили «9» по истории, 5 – по математике и 4 – по литературе, 2 – по истории и математике, 2 – по истории и литературе, 1 – по математике и литературе. Сколько учени ков получили «9» по всем предметам?

Рисунок 4. В спортивном лагере 100 человек, занимающихся плава Задача 1. 5. Доказать, что A \ ( A \ B) = A B. нием, легкой атлетикой и лыжами. Из них 10 занимаются и Решение. Преобразуем левую часть равенства, учитывая, плаванием, и легкой атлетикой, и лыжами, 18 – плаванием и легкой атлетикой, 15 – плаванием и лыжами, 21 – легкой атле что тикой и лыжами. Число спортсменов, занимающихся плавани A\ B = A B:

ем, равно числу спортсменов, занимающихся легкой атлети A \ ( A \ B) = A \ ( A B) = A A B = A ( A B) = кой, и равно числу спортсменов, занимающихся лыжами. Най ти это число.

= A ( A B) = ( A A) ( A B) = ( A B) = A B. 5. Группе студентов предложены спецкурсы по мультиме диа, искусственному интеллекту и имитационному моделиро Задача 1. 6. Пусть А={xN| 2x6}, B={xN| 1x4}, ванию. 22 студента записались на спецкурс по мультимедиа, C={xN| x2-4=0}. Найти (АВ) ВС, СВ, ВС. 18 – на спецкурс по искусственному интеллекту, 10 – на спец курс по имитационному моделированию, 8 – на спецкурсы по Решение. А={3, 4, 5, 6}, B={2, 3}, C={2}. Тогда AB={3}, мультимедиа и искусственному интеллекту, 15 – на спецкурсы ВС={2, 3}, (АВ) ВС={2, 3}. по мультимедиа и имитационному моделированию, 7 – на СВ={(2, 2), (2, 3)}, BC={(2, 2), (3, 2)}. спецкурсы по искусственному интеллекту и имитационному моделированию. 5 студентов записались на все три спецкурса.

Задачи для самостоятельного решения Сколько студентов в группе?

6. Во время сессии 24 студента группы должны сдать три 1. У фирмы есть 100 предприятий, причем каждое предпри зачета: по физике, математике и программированию. 20 сту ятие выпускает хотя бы одну продукцию вида А, В или С.

дентов сдали зачет по физике, 10 – по математике, 5 – по про Продукцию всех трех видов выпускают 10 предприятий, про граммированию, 7 – по физике и математике, 3 – по физике и дукцию вида А и В – 18 предприятий, продукцию вида А и С – программированию, 2 – по математике и программированию.

15 предприятий, продукцию вида В и С – 21 предприятие.

Сколько студентов сдали все три зачета?

Число предприятий, выпускающих продукцию вида А, равно 7. В группе переводчиков 15 человек владеют английским числу предприятий, выпускающих продукцию вида В, и равно языком, 19 – французским, 8 – немецким. 9 переводчиков вла числу предприятий, выпускающих продукцию вида С. Найти деют английским и французским языками, 7 – английским и число предприятий, выпускающих только продукцию вида А.

15 немецким, 6 – французским и немецким. 4 переводчика владе- 14. В одной студенческой группе программистов 10 человек ют всеми тремя языками. Сколько переводчиков в группе? могут писать программы на Delphi, 10 – на Паскале, 6 – на Си.

8. Опрос группы студентов показал, что 70 % из них любят По два языка знают: 6 человек – Delphi и Паскаль, 4 – Паскаль ходить в кино, 60 % – в театр, 30 % – на концерты. В кино и и Си, 3 – Delphi и Си. Один человек знает все три языка.

театр ходят 40 % студентов, в кино и на концерты – 20 %, в Сколько студентов в группе?

театр и на концерты – 10 %. Сколько студентов (в %) ходят в 15. В день авиации на аэродроме всех желающих катали на кино, театр и на концерты? самолете, планере и вертолете. На самолете прокатились 9. В группе 20 студентов. После медицинского осмотра 14 человек, на планере – 20, на вертолете – 15. И на самолете, и на студентов были направлены на дополнительное обследование планере каталось 10 человек, на самолете и вертолете – 12, на к терапевту, 6 – к окулисту, 5 – к ортопеду. К терапевту и планере и вертолете – 5. Два человека прокатились и на само окулисту были направлены 3 студента, к терапевту и ортопеду лете, и на планере, и на вертолете. Сколько было желающих – 3, к окулисту и ортопеду – 2. Сколько студентов было прокатиться?

направлено к терапевту, окулисту и ортопеду? 16. Эквивалентны ли следующие множества:

{ } 16.1. A = x : x 2 8 x + 15 = 0 и B = {2, 3} ;

10. При обследовании рынка спроса инспектор указал в оп { } { } росном листе следующие данные. Из 1000 опрошенных 16.2. A = x : x 3 1 = 0 и B = x : x 2 3 x + 2 = 0 ;

покупают жевательную резинку «Dirol», 752 – «Orbit», 418 – A = {x : x } «Stimorol», 570 – «Dirol» и «Orbit», 356 – «Dirol» и «Stimorol», 3x + 2 = 0 и B = {2, 3} ;

16.3.

348 – «Orbit» и «Stimorol», 297 – все виды жевательной резин ки. Не ошибся ли инспектор? 16.4. A = { 2n, n = 1, 2, …} и B = {n2, n = 1, 2, …};

11. Всем участникам автопробега не повезло. 12 из них увяз 16.5. A = {y: y = 3x, 0x } и B = {y: y = 3n, n = 1, 2, …}?

ли в песке – пришлось толкать машину, 8 понадобилась замена колеса, у шестерых перегрелся мотор, пятеро толкали машину 17. Нарисовать диаграммы Эйлера-Венна для следующих и меняли колесо, четверо толкали машину и остужали мотор, множеств:

трое меняли колесо и остужали мотор. Одному пришлось ис 17.1. A B ;

пытать все виды неполадок. Сколько всего было участников 17.2. A (B C ) ;

автопробега?

12. В цеху имеется 25 станков, которые могут выполнять 17.3. ( A \ B ) C ;

три вида операций: А, В и С. Из них 10 станков выполняют 17.4. ( A \ B ) C ;

операцию А, 15 – В, 12 – С. Операции А и В могут быть вы ( ) полнены на 6 станках, А и С – на 5, В и С – на 3 станках.

17.5. A B \ ( A B ) ;

Сколько станков могут выполнять все три операции?

17.6. ( A B ) (C \ ( A B )) ;

13. В студенческой группе 25 человек. Чтобы получить до 17.7. A (B C ) ;

пуск на экзамен по данному курсу необходимо защитить кур совую работу, выполнить лабораторную работу и сдать зачет.

17.8. A B A B ;

15 студентов защитили курсовую работу, 20 — выполнили ла бораторную работу, 17 — сдали зачет. Защитили курсовую ра- 17.9. C \ A B ;

боту и выполнили лабораторную работу 12 человек. Защитили 17.10. A B C ;

курсовую работу и сдали зачет 13 человек. Выполнили лабора 17.11. A \ B C ;

торную работу и сдали зачет 16 человек. Сколько студентов допущено к экзамену?

17 Эквиваленцией двух высказываний А и B называется вы 17.12. A B C.

сказывание А B, истинное тогда и только тогда, когда оба 18. Имеют ли место равенства:

высказывания А и B одновременно истинны или ложны.

18.1. ( A \ B ) ( A B ) = A ;

Приведем индуктивное определение формулы логики вы 18.2. ( A B ) \ ( A B ) = A B A B ;

сказываний.

1. Любая высказывательная переменная, а также констан 18.3. C \ A B = A \ B C ;

ты И (истина), Л (ложь) есть формула.

18.4. A \ ( B C ) = ( A \ B) C ;

2. Если A и B – формулы, то A, A B, A B, A B, A B, есть формулы.

18.5. A \ ( B C ) = ( A \ B) C ;

3. Ничто, кроме указанного в пунктах 1 – 2, не есть формула.

A B C = A B C ;

18.6. Две формулы называются равносильными, если на всех C \ A B = A \ B C ;

одинаковых наборах переменных значения этих формул сов 18.7.

падают. Равносильность формул A и B обозначают A B.

A B C = A B C ;

18.8.

Для того, чтобы установить равносильность формул, A \ ( B C ) = ( A \ B) C ;

18.9.

можно составить таблицы значений (таблицы истинности) для 18.10. A B C = C \ (C ( A B)) ;

каждой формулы и сравнить их. Для равносильных формул эти 18.11. A B ( A B ) = B ? таблицы совпадают. Другой способ установления равносиль ности формул заключается в использовании некоторых уста новленных равносильностей формул логики высказываний.

2. Логика высказываний Для любых формул A, B и C справедливы следующие равносильности:

Высказыванием называется повествовательное языковое предложение, относительно которого можно сказать истинно 1) коммутативность:

оно или ложно. 1.1. A B B A ( AB BA) ;

Отрицанием высказывания А называется высказывание 1.2. A B B A ;

A, которое истинно тогда и только тогда, когда высказывание 2) ассоциативность:

А ложно. 2.1. A( BC ) ( AB)C ;

Конъюнкцией двух высказываний А и B называется выска 2.2. A ( B C ) ( A B ) C ;

зывание АB, истинное тогда и только тогда, когда истинны 3) дистрибутивность:

оба высказывания А и B. При записи соотношений логики вы 3.1. A( B C ) AB AC ;

сказываний знак конъюнкции иногда опускают, то есть вместо 3.2. A BC ( A B)( A C ) ;

записи АB используют запись АВ.

Дизъюнкцией двух высказываний А и B называется выска- 4) законы де Моргана:

зывание АB, ложное тогда и только тогда, когда ложны оба 4.1. AB A B ;

высказывания А и B.

4.2. A B A B ;

Импликацией двух высказываний А и B называется выска 5) идемпотентность:

зывание А B, ложное тогда и только тогда, когда А истинно, 5.1. AA A ;

а B ложно. 5.2. A A A ;

6) поглощение:

19 6.1. A( A B ) A ;

любых наборов переменных она принимает значение Л.

Элементарной конъюнкцией называется конъюнкция не 6.2. A AB A ;

скольких переменных, взятых с отрицанием или без отрица 7) ( A B )( A B ) A ;

ния, причём среди переменных могут быть одинаковые.

8) двойное отрицание: Элементарной дизъюнкцией называется дизъюнкция не 9) A A ;

скольких переменных, взятых с отрицанием или без отрица ния, причём среди переменных могут быть одинаковые.

10) свойства констант:

10.1. A A ;

Всякую дизъюнкцию элементарных конъюнкций назы 10.2. A ;

вают дизъюнктивной нормальной формой, то есть ДНФ. Вся кую конъюнкцию элементарных дизъюнкций называют конъ 10.3. A ;

юнктивной нормальной формой, то есть КНФ.

10.4. A A ;

Совершенной ДНФ (СДНФ) называется ДНФ, в которой 10.5. ;

нет равных элементарных конъюнкций, и все они содержат 10.6. ;

одни и те же переменные, причём каждую переменную только 11) закон противоречия: один раз (возможно с отрицанием).

AA. Совершенной КНФ (СКНФ) называется КНФ, в которой 12) закон «исключенного третьего»: нет равных элементарных дизъюнкций, и все они содержат од A A ;

ни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием).

13) замена операций импликации и эквиваленции:

Приведем алгоритм получения СДНФ и СКНФ по табли 13.1. A B A B ;

це истинности. Формулы можно получить, выполнив четыре 13.2. A B ( A B )( B A).

пункта алгоритма.

Каждая из перечисленных равносильностей может быть СДНФ СКНФ доказана с помощью таблиц значений функций, составленных 1. Конструирование СДНФ и СКНФ начинается с таблицы для выражений, стоящих слева и справа от символа «».

истинности.

Справедливы также обобщенные законы дистрибутивно 2. Отметим те строки таблицы, выходы которых равны сти и обобщенные законы де Моргана:

1 14) ( A1 A2... An )(B1 B2... Bm ) 3. Выписываем для каждой отмеченной строки комбинацию A1 B1 A1 B2... A1 Bm... An B1 An B2 An Bm ;

переменных через знак ( A1 A2... An ) (B1 B2...Bm ) 15) конъюнкции () дизъюнкции () ( A1 B1 )( A1 B2 )...( A1 Bm )...( An B1 )( An B2 )...( An Bm );

Знаки операции отрицания расставим следующим образом:

16) если переменная равна 1, то если переменная равна 0, то A1 A2... An A1 A2... An ;

( ) запишем саму эту перемен- запишем саму эту перемен 17) A1 A2... An A1 A2... An A1 A2... An. ную, если же она равна 0, то ную, если же она равна 1, то запишем ее отрицание. запишем ее отрицание.

Формула называется тождественно-истинной, если для 4. Все полученные выражения связываем операцией любых наборов переменных она принимает значение И.

Формула называется тождественно-ложной, если для дизъюнкции конъюнкции 21 Ч – «сосуд изготовлен в IV веке»;

Можно получить СДНФ и СКНФ путем равносильных П – «сосуд изготовлен в V веке».

преобразований.

Приведем один из способов перехода от ДНФ к КНФ. Тогда высказывание «Это греческий сосуд, изготовлен Ставим над ДНФ два отрицания и с помощью правил де Мор- ный в V веке» можно записать так: ГП. Из слов преподавателя гана (не трогая верхнее отрицание) приводим отрицание ДНФ следует, что это высказывание ложно (ГП=0). Так как Алексей снова к ДНФ. При этом приходится раскрывать скобки с ис- прав только в чем-то одном, то или Г=1, или П=1. Следова пользованием равносильных преобразований. Отрицание тельно, истинным будет высказывание = 1.

(верхнее) полученной ДНФ (по правилу де Моргана) сразу да- Аналогично, из слов Бориса и преподавателя следует, что ет КНФ. Второй способ перехода от ДНФ к КНФ — использо = 1, а из слов Григория и преподавателя, что вание дистрибутивного закона.

= 1, то есть = 1. Кроме того, ясно, что Переход от КНФ к ДНФ осуществляется простым рас сосуд может быть изготовлен только в одном из веков и только крытием скобок.

в одной из стран. Эти условия можно записать так:

Приведем способ перехода от ДНФ к СДНФ. Если в ка кой-то простой конъюнкции не хватает переменной, например, = 1 и = 1.

z, вставляем в нее выражение z z = 1, после чего раскрываем Таким образом, получено пять тождественно истинных скобки (при этом повторяющиеся дизъюнктные слагаемые не высказываний. Если их логически перемножить, то результат пишем).

должен быть также тождественно истинным высказыванием:

Переход от КНФ к СКНФ осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не ( )( )( )( )( ) = 1.

хватает какой-то переменной (например, z), то добавляем в нее выражение z z = 0 (это не меняет самой дизъюнкции), после Упростим левую часть полученной формулы, выполнив чего раскрываем скобки с использованием распределительного логическое умножение первого и второго сомножителей, а закона.

также третьего и четвертого соответственно:

Задача 2. 1. Во время археологической практики Алек ( )( ) = ( )= сей, Борис и Григорий нашли в земле сосуд. Рассматривая на ходку, каждый высказал по два предположения:

= ;

Алексей: «Это греческий сосуд, изготовленный в V веке».

( )( ) = ( ) = Борис: «Это финикийский сосуд, изготовленный в III веке».

Григорий: «Это не греческий сосуд, изготовленный в IV веке». = ;

Руководитель практики сказал студентам, что каждый из них ( )( ) =.

прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?

Выполним логическое умножение полученного резуль Решение. Примем следующие обозначения для высказы- тата и пятого множителя:

ваний студентов:

Г – «это греческий сосуд»;

Ф – «это финикийский сосуд»;

Т – «сосуд изготовлен в III веке»;

23 ( )( ) а затем распространить их на оставшийся диапазон С2:G5.

= ( ) Задача 2. 3. Проверить равносильность выражений = (xy) (zy) и (xz)y двумя способами: построив таблицу ( ) =. истинности и упростив выражения.

Решение. а) Для построения таблицы истинности вос = 1, = 1, Иначе говоря, = 1. То есть, = 1, пользуемся электронными таблицами. Для этого представим исходные данные так, как на рис. 13. В ячейки D2, E2, F2, G2, = 1, = 1. Следовательно, сосуд финикийский и изготовлен H2 введем формулы:

в V веке. =(B2=A2)*1, Задача 2. 2. Реализовать конъюнкцию, дизъюнкцию, =(B2=C2)*1, отрицание, импликацию и эквиваленцию в электронных таб =D2*E2, лицах MS EXCEL.

=(A2+C2=1)*1, Решение. Приведем один из вариантов такой реализа ции без использования функций MS EXCEL. На рис. 12 приве- =(B2=G2)* дены таблицы истинности указанных функций согласно опре и распространим их затем на весь оставшийся диапазон D3:H9.

делениям этих операций.

В результате получится таблица, приведенная на рис. 14.

Рисунок Такая же таблица получится, если в ячейки С2, D2, E2, F2 и G2 ввести соответственно формулы Рисунок =(A2+B2=1)*1, =A2*B2, =(B2=A2)*1, =1-A2, =(B2=A2)*(A2=B2), 25 x y z x x y z x y x x y z 1 y x y z.

Замечание. Приведем еще один способ получения КНФ из ДНФ:

x y z x x y z x x y ( z x) x yz xxy x yz x y z.

Рисунок Полученное выражение является также и СКНФ.

Из таблицы видно, что для функций (xy)(zy) и Чтобы получить СДНФ из формулы (*), выполним равно (xz)y значения на всех наборах переменных совпадают.

сильные преобразования:

б) Преобразуем (xy)(zy): x y z x x( y y )( z z ) y ( x x )( z z ) z x ( y y ).

( x y )( z y ) ( x y )( z y ) x z y x z y Раскрыв скобки, упрощаем выражение:

x z y. x( y y )( z z ) y ( x x )( z z ) z x ( y y ) Задача 2. 4. Для булевой функции x ( y ( z x)) : xyz x y z xy z x y z x y z x y z x y z.

а) найти ДНФ, КНФ, СДНФ и СКНФ методом равносиль- б). Воспользуемся таблицей истинности для функции ных преобразований;

x ( y ( z x)).

б) найти СДНФ и СКНФ табличным способом, а затем сравнить с СДНФ и СКНФ, полученными в пункте «а».

Решение. а). Заменяем операции и :

x y ( z x )( x z ) x y ( z x)( x z ) (*) x y z x xz x y z x.

Это и есть ДНФ. Чтобы получить КНФ, воспользуемся дист рибутивным законом:

Отсюда видно, что для получения СДНФ следует исполь зовать строки с 1 в предпоследнем столбце:

xyz xy z x y z x y z x y z x y z x y z.

27 p (q r ) pq r ;

Для получения СКНФ следует воспользоваться строкой с 2.8.

0 в предпоследнем столбце таблицы истинности: yx xz;

2.9.

x y z. x y x y.

2.10.

3. Являются ли приведенные ниже формулы тождественно Задачи для самостоятельного решения истинными? Проверку выполнить двумя способами: построив 1. Определить, имеют ли место следующие равносильности таблицу истинности и упростив выражения. Таблицу истинно двумя способами: построив таблицу истинности и упростив сти реализовать в MS EXCEL:

выражения. Таблицу истинности реализовать в MS 3.1. ( p q )(r q ) ( p r q );

EXCEL:

3.2. ( p q )(r q ) ( p qr );

1.1. B C A C AB = C A C B ;

( )( ) 3.3. ( p q ) p q );

1.2. BC ABC AC AB C AC = A;

1.3. (AB A BC A BC )(ABC ABC ABC ) = ABC;

3.4. ( p q )q p;

1.4. ABC ABC ABC ABC = C ;

3.5. pq r p r q;

1.5. AB A BC A BC AC = A;

3.6. ( p q ) p q ;

1.6. X (Y Z ) = ( X Y ) ( X Z );

3.7. ( p q )(q r ) ( p r ).

1.7. A B( A C ) B A C = AB ;

4. В одном королевстве были незамужние принцессы, голод ( )( ) 1.8. AB ABC BC C C AC ABC = B AC ;

ные тигры и приговоренный к казни узник. Всякому узнику, осужденному на смерть, король давал последний шанс. Узнику 1.9. B C A C AB = C A C B. предлагалось угадать, в какой из двух комнат находится тигр, а в какой принцесса. Хотя вполне могло быть, что король в обе 2. Для приведенных ниже формул булевых функций а) най их комнатах разместил принцесс или тигров. Выбор надо было ти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобра сделать на основании табличек на дверях комнаты. Известно, зований;

б) найти СДНФ, СКНФ табличным способом (срав что утверждения на табличках были либо оба истинными, либо нить с СДНФ, СКНФ, полученными в пункте а)).

оба ложными. Надписи гласили:

( x y z ) xyz ;

2.1.

1 комната 2 комната x( y x z ) ;

2.2.

По крайней мере, в Тигр сидит в первой x z ( y x);

2.3. одной из этих комнат комнате x y x z;

находится принцесса 2.4.

x y y z ;

2.5.

Какую дверь должен выбрать узник?

xy xz z;

2.6. 5. На соревнованиях по легкой атлетике Андрей, Борис, Сер гей и Володя заняли первые четыре места. Но когда однокурс x y ( x z) y ;

2.7.

ницы стали вспоминать, как эти места распределились между 29 победителями, то мнения разошлись. Даша сказала: «Андрей X = {x1, x2, x3, x4}, был первым, а Володя – вторым». Галя утверждала: «Андрей A = {a1 = (x1, x2 ), a2 = был вторым, а Борис – третьим». Лена считала: «Борис был четвертым, а Сергей – вторым». Ася, которая была судьей на (x1, x3 ), a3 = (x3, x4 ), этих соревнованиях и хорошо помнила, как распределились a4 = (x3, x2 )}.

места, сказала, что каждая из девушек сделала одно правиль ное и одно неправильное заявление. Кто из студентов занял Рисунок первое, второе и третье место?

Если сопоставить каждому ребру число из множества С, 6. Студент делает следующие высказывания: А. Если я тогда граф называют взвешенным.

люблю физику, то люблю и математический анализ. Б. Если Граф можно задать матрицами смежности и инцидент высказывание A истинно, то я люблю физику. Следует ли из ности. Элементы матрицы смежности S графа задаются как:

этих высказываний, что студент любит физику?

1, вершины х и x ;

ребро (дуга), соединяющее если существует 7. Юра условился с родителями, что всегда будет говорить sij = им только правду. Однажды он получил 2 по физике и очень не i j 0 в противном случае.

хотел говорить об этом дома. На прямой вопрос, что он полу чил по физике, Юра ответил… Что же ответил Юра так, чтобы (i, j=1, 2,…, n).

не сказать о двойке, и в то же время сказать совершеннейшую Элементы матрицы инцидентности U = uij для гра истину? m n фа G, состоящего из n вершин и m дуг, определяются как:

3. Основные понятия теории графов если вершина хi начало дуги aj;

1, Графом G = (X, А) называется пара объектов X = {x1, x2, uij = 1, если вершина хi конец дуги aj;

…, xn} и А = {a1, a2, …, am}, где X – множество вершин, а A – 0, множество ребер графа. Если ребра из множества A ориенти если вершина хi не инцидентна дуге aj.

рованы, то они называются дугами, а граф называют ориенти (i=1, 2,…,n;

j=1, 2,…, m).

рованным. Если ребра не имеют ориентации, то граф называют неориентированным. В противном случае граф является сме- Для графа, приведенного на рис. 17, матрица смежности шанным. На рис. 15–16 приведены неориентированный и ори приведена на рис. 18, а матрица инцидентности — на рис. 19.

ентированный графы соответственно.

X = {x1, x2, x3, x4}, A = {a1, a2, a3, a4}.

Рисунок 31 Рисунок Если граф содержит петли, то есть дуги вида (хi, xi) то гда элементы матрицы инцидентности, соответствующие ду гам, образующим петли, одновременно равны 1 и –1, что при водит к неоднозначности матрицы инцидентности.

Пусть G – неориентированный граф. Маршрутом в гра Рисунок фе G называется такая последовательность (конечная или бес конечная) ребер a1, a2,... an..., что каждые два соседних ребра ai и ai+1 имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конеч ном маршруте (a1, a2,... an) имеется первое ребро a1 и послед нее ребро an. Вершина x1, инцидентная ребру a1, но не инци дентная ребру a2, называется началом маршрута, а вершина xn, инцидентная ребру an, но не инцидентная ребру an-1, называет ся концом маршрута.

Длиной маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько Рисунок оно входит в данный маршрут.

Замкнутый маршрут называется циклом.

Маршрут (цикл), в которой все ребра различны, называ ется простой цепью (циклом). Маршрут (цикл), в которой все вершины (кроме первой и последней) различны, называется элементарной цепью (циклом).

На рис. 20 изображены два маршрута из вершины x1 в вершину x4: M1 = (a1, a2, a4) и M2 = (a1, a2, a5, a6). Длина мар шрута M1 равна 3, а длина маршрута M2 равна 4.

33 (a1,a2,a4,a3) – цепь, ко торая является про стой, но не элемен тарной, так как все ребра различны, но вершина x2 встречает ся дважды.

(a1,a2,a2) – маршрут длины 3, не являю щийся ни простой, ни элементарной цепью, т.к. ребро a2 и верши на x2 встречаются Рисунок дважды.

(a1,a3,a4) – простая Понятия пути и контура в ориентированном графе ана элементарная цепь логичны понятиям маршрута и цикла в неориентированном длины 3, так как все графе.

ребра и вершины по Путем в ориентированном графе называется последова парно различны.

тельность дуг, в которой конечная вершина всякой дуги, от личной от последней, является начальной вершиной следую щей дуги.

Число дуг пути называется длиной пути.

Путь называется контуром, если его начальная вершина (a2,a4,a3) – простой совпадает с конечной вершиной.

элементарный цикл, Путь (контур), в котором все дуги различны, называется так как это замкнутый простым.

маршрут, у которого Путь (контур), в котором все вершины, кроме первой и все ребра и вершины, последней, различны, называется элементарным.

кроме первой и по Понятиям ребра, маршрута, цепи, цикла в неориентиро следней, различны.

ванном графе соответствуют понятия дуги, пути, ориентиро ванной цепи, контура в ориентированном графе.

35 4. Нахождение минимального дерева Ориентированный граф Неориентированный граф дуга остова ребро путь маршрут Пусть G – связный нагруженный граф. Задача построе контур цикл ния минимального остовного дерева заключается в том, чтобы из множества остовных деревьев найти такое, у которого сум Граф называется связным, если каждая пара различных ма длин ребер минимальна.

вершин может быть соединена, по крайней мере, одной це Приведем типичные случаи, когда возникает необходи пью.

мость построения минимального остовного дерева графа.

Ориентированный граф называется нагруженным, ес а). Необходимо соединить n городов железнодорожными ли дугам этого графа поставлены в соответствие веса, так что линиями (автомобильными дорогами, линиями электропере дуге (xi,xj) сопоставлено некоторое число c(xi, xj) = cij, назы дач, сетью трубопроводов и т.д.) так, чтобы суммарная длина ваемое длиной (или весом, или стоимостью дуги). Длиной линий или стоимость была бы минимальной.

(или весом или стоимостью) пути s, состоящего из некоторой б). Требуется построить схему электрической сети, в ко последовательности дуг (xi, xj), называется число l(s), равное торой клеммы должны быть соединены с помощью проводов сумме длин дуг, входящих в этот путь, т.е. наименьшей общей длины.

Задачу построения минимального дерева-остова можно c, l(s) = решить с помощью алгоритма Краскала. Приведем описание ij алгоритма по шагам.

Шаг 1. Отсортируем ребра графа по неубыванию весов.

причем суммирование ведется по всем дугам (xi, xj) s.

Шаг 2. Полагаем, что каждая вершина относится к сво Матрица C = (cij) называется матрицей длин дуг или ей компоненте связности.

матрицей весов.

Шаг 3. Проходим ребра в «отсортированном» порядке.

Подграфом неориентированного графа G называется Для каждого ребра выполняем следующую проверку:

граф, все вершины и ребра которого содержатся среди вершин а) если вершины, соединяемые данным ребром, лежат в и ребер графа G. Подграф называется собственным, если он разных компонентах связности, то объединяем эти компонен отличен от самого графа. Аналогично определяется подграф ты в одну, а рассматриваемое ребро добавляем к минимально ориентированного графа. му дереву-остову;

б) если вершины, соединяемые данным ребром, лежат в Компонентой связности неориентированного графа на одной компоненте связности, то исключаем ребро из рассмот зывается его связный подграф, не являющийся собственным рения, так как при включении данного ребра образуется цикл.

подграфом никакого другого связного подграфа данного Шаг 4. Если есть еще нерассмотренные ребра и не все графа.

компоненты связности объединены в одну, то переходим к ша Неориентированным деревом (или просто деревом) на гу 3, иначе алгоритм завершает работу:

зывается связный граф без циклов. а) если при этом просмотрены все ребра, но не все ком Остовным деревом (деревом-остовом, покрывающим поненты связности объединены в одну, то для исходного графа деревом, скелетным деревом) связного графа G называется невозможно построить покрывающее дерево;

любой его подграф, содержащий все вершины графа G и яв- б) если просмотрены все ребра, и все компоненты связ ности объединены в одну, то для исходного графа построено ляющийся деревом.

минимальное покрывающее дерево.

37 Задача 3. 1. Граф G содержит 5 вершин. Расстояния 3. Добавление ребра (1, 2) приведет к образованию цикла между вершинами заданы таблицей 1. Найти его минимальное (рис. 23). Поэтому не включаем это ребро в дерево-остов.

дерево-остов (минимальное покрывающее дерево). 4. Следующим кандидатом на включение в дерево-остов является ребро (2, 5). Его включение не создает цикла, поэтому Таблица V={1, 2, 4, 5} (рис. 24).

1 2 3 4 5. Добавление ребра (1, 5) приведет к образованию цикла 1 0 5 8 2 (рис. 25). Поэтому не включаем это ребро в дерево-остов.

2 5 0 9 2 6. Следующим кандидатом на включение в дерево-остов 3 8 9 0 10 является ребро (4, 5). Однако его добавление приведет к обра 4 2 2 10 0 зованию цикла. Поэтому не включаем это ребро в дерево 5 7 5 10 7 остов.

7. Включение ребра (1, 3) не создает цикла, поэтому V={1, Решение. Так как матрица симметрична, можно рас 2, 3, 4, 5} (рис. 26).

сматривать, например, только элементы, расположенные выше 8. Так как все вершины графа вошли в дерево, то получено или ниже главной диагонали:

покрывающее дерево с минимальным весом, равным 17.

Исходные Упорядоченные по длине ребра данные Рисунок 21 Рисунок Рисунок 23 Рисунок 1. Включаем в дерево-остов ребро (1, 4). Множество вер шин, включенных в дерево-остов V={1, 4} (рис. 21).

2. Следующим кандидатом на включение в дерево-остов является ребро (2, 4). Добавление вершины 2 к множеству V и ребра (2, 4) к дереву не создает цикла, так как вершина 2 не входит в множество V. После добавления ребра (2, 4) к дереву множество вершин, включенных в дерево-остов V={1, 2, 4} (рис. 22). Рисунок 25 Рисунок 39 Решение задачи о нахождении минимального дерева- являются 10 переменных x12, x13, x14, x15, x 23, x 24, x 25, остова с использованием надстройки MS EXCEL x34, x35, x 45.

«Поиск решения»

Приведем математическую модель задачи. Пусть пере менная хij означает наличие ребра вида (i, j) в покрывающем дереве, а аij интерпретируется как длина указанного ребра.

Тогда математическая модель задачи имеет вид как на рис. 27 [12].

Здесь (1) – целевая функция, ограничения (2) – (4) тре буют отсутствия в покрывающем дереве изолированных вер шин, ограничение (5) – наличие в покрывающем дереве ровно n-1 ребра. Ограничение (6) требует, чтобы все переменные принимали только двоичные (булевы) значения.

n 1 n a x min, (1) ij ij x i =1 j = i + n x1 j 1;

(2) Рисунок i =1 Математическая постановка такой индивидуальной зада k 1 n x1 j + x1 j 1 (k {2,..., n 1});

(3) чи приведена ниже.

j =2 5 x12 + 8 x13 + 2 x14 + 7 x15 + 9 x23 + 2 x24 + 5 x25 + 10 x34 + j = k + n (4) + 10 x35 + 7 x45 min.

x1 j 1;

x i = n 1 n Множество ограничений выглядит так:

xij = n 1;

(5) x12 + x13 + x14 + x15 1;

i =1 j = i +1 x + x + x + x 1;

x {0,1}. (6) 23 24 ij x13 + x23 + x34 + x35 1;

x14 + x24 + x34 + x45 1;

x + x + x + x 1;

Рисунок 15 25 35 Задача 3. 2. Найти минимальное дерево-остов для графа, x12 + x13 + x14 + x15 + x23 + x24 + x25 + x34 + x35 + x45 = 4;

приведенного на рис. 28. x12, x13, x14, x15, x23, x24, x25, x34, x35, x45 {0, 1}.

Решение. В заданном графе 5 вершин и 10 ребер. Следо вательно, переменными математической модели этой индиви Воспользуемся надстройкой «Поиск решения», входящей дуальной задачи о построении минимального дерева-остова в состав MS EXCEL. Расположим исходные данные на рабо 41 чем листе так, как на рис. 29. На рис. 30–31 приведены окна надстройки и ее параметров.

На рис. 32 показано состояние рабочего листа после вы полнения решения с использованием надстройки. На рис. изображено минимальное дерево-остов для данного графа. За метим, что вес этого дерева в точности соответствует получен ному по алгоритму Краскала весу (задача 3. 1).

Рисунок Рисунок Рисунок Рисунок 43 12 345678 9 2.

1 04 4 5 4 8 2 10 2 2 40 1 2 8 10 3 1 3 41 076382 4 52 7 0 9 10 10 2 5 48 6 9 0 6 10 5 6 8 10 3 10 6 0 3 7 7 23 8 10 10 3 0 8 8 10 1 225780 9 28 354424 10 10 2 493994 3. 1 2 3 4 5 6 7 8 9 1 0 2 9 5 2 5 4 4 4 2 2 0 7 1 8 10 1 2 6 3 9 7 0 3 1 3 9 1 6 Рисунок 4 5 1 3 0 7 4 9 7 2 5 2 8 1 7 0 8 9 8 6 Задачи для самостоятельного решения 6 5 10 3 4 8 0 3 5 10 7 4 1 9 9 9 3 0 5 3 Неориентированный граф G содержит 10 вершин. Рас 8 4 2 1 7 8 5 5 0 10 стояния между вершинами заданы таблицей. Найти его мини 9 4 6 6 2 6 10 3 10 0 мальное дерево-остов (минимальное покрывающее дерево):

10 4 8 9 1 3 6 6 1 7 1 2 3 4567 8 9 1.

10 6 9 1 10 6 10 9 39 123 4 5 6 78 9 4.

26 0 6 7264 9 81 1 0 10 7 4 1 4 34 9 39 6 0 3854 6 27 2 10 0 6 2 7 6 24 7 41 7 3 0888 1 99 3760 8 4 6 5 10 8 5 10 2 8 8076 7 65 4428 0 7 8 74 7 66 6 5 8 7 0 10 3 62 5174 7 0 2 83 3 7 10 4 4 8 6 10 0 2 92 6466 8 2 0 73 9 89 9 6 1732 0 72 7325 7 8 7 08 3 93 8 2 9669 7 03 8 4 4 10 4 3 3 80 1 10 9 1 7 9522 2 30 9978 7 3 9 31 0 10 10 8 5 7 6 5 77 2 45 1 23 4 567 89 10 1 2 3456 7 89 5. 8.

1 0 48 6 962 59 2 10 6 6641 6 78 2 4 09 9 365 42 1 26 0 9943 7 31 3 8 90 3 5 10 9 26 6 36 9 0616 6 16 4 6 93 0 291 15 5 46 9 6 0 10 3 1 49 5 9 35 2 016 83 1 54 4 1 10 0 1 8 73 6 6 6 10 9 1 0 10 47 6 61 3 6310 6 7 10 7 2 59 1 6 10 0 4 10 4 76 7 6186 0 17 8 5 42 1 844 04 7 87 3 1477 1 06 9 9 26 5 3 7 10 40 4 98 1 6 9 3 10 7 60 10 2 16 5 164 74 0 10 10 1 2276 6 54 123 45 6 7 8 9 10 1234 5 6 7 8 9 6. 9.

1085 97 3 10 2 10 10 10383 1 10 1 8 8 2 8 0 10 96 1 10 6 9 7 23056 4 9 10 7 5 3 5 10 0 62 44486 38506 3 2 10 10 6 4996 07 57771 43660 8 3 6 1 10 5762 70 2 8 10 8 2 51438 6314 52 02868 6 10 9 2 3 7 10 10 4 78 2 0 10 6 8 7 1 10 10 6 8264 7 10 8 10 0 8 9 8 8 7 10 1 9 10 9 8 78 66809 9 8 5 6 10 10 10 7 6 12 88990 10 7 2 4 4 1 2 3456789 10 1 2 3 45 67 8 9 7. 10.

1 0 5 8147366 8 1 0 1 6 77 75 7 2 5 0 3375167 9 2 1 0 8 11 37 6 3 8 3 0324776 9 3 6 8 0 21 68 5 4 1 3 3 0 5 8 10 10 6 5 4 7 1 2 0 10 41 9 5 4 7 2502751 10 5 7 1 1 10 0 3 10 1 6 7 5 4 8 2 0 9 7 10 9 6 7 3 6 43 05 4 7 3 1 7 10 7 9 0 2 1 4 7 5 7 8 1 10 50 3 8 6 6 7 10 5 7 2 0 6 10 8 7 6 5 91 43 0 9 6 7 6 6 1 10 1 6 0 3 9 4 7 7 68 25 2 10 8 9 9 5 10 9 4 10 3 0 10 4 4 9 35 56 9 47 Решение. Матрица смежности для данного графа имеет 1 23 4567 8 9 11.

вид как на рис. 34 справа.

1 0 67 2246 8 7 2 6 04 8837 6 8 3 7 40 6586 8 1 10 0 1 1 4 2 86 0794 9 5 1 0 1 5 2 85 7 0 10 9 5 2 4 S = 1 0 6 4 38 9 10 0 8 3 9 1 0 1 7 6 76 4980 6 3 8 8 68 9536 0 9 9 7 81 5293 9 0 Рисунок 10 8 2 10 4 4 10 10 9 3 Тогда S 2 и S 3 выглядят так, как на рис. 35.

1234 5678 9 12.

4 5 5 3 1 2 1 0962 9431 28 2 1 2 3 5 2 5 2 9096 2 1 3 10 4, S = S = 4 1 3 3 6 9 0 10 1 5 3 10 42 4 2 6 10 0 9 10 1 4 93 5 2 5 1 2 1 2 5 9219 0881 6 4 1 5 10 8011 38 Рисунок Значение s = 4 означает, что из вершины 1 в вершину 7 3331 8 1 0 10 32 8 1 10 10 4 1 1 10 0 31 существует 4 пути длины 3, s12 = 5 — из вершины 1 в вершину 9 2449 1333 03 2 — 5 путей длины 3 и т.д.

8 10 2 3 2821 10 Чтобы выявить эти пути, следует обозначить дуги, на пример, так, как на рис. 36. Вместо матрицы смежности введем 5. Задачи о поиске путей в рассмотрение матрицу, элементами которой являются дуги вида ur, r = 1, 2, …, 10 (рис. 37).

Поиск путей с заданным количеством дуг Пусть G = (Х, А) — связный граф. Для определения ко личества путей, состоящих из k дуг, необходимо возвести в k 0 u u1 u k ю степень матрицу смежности. Тогда ее элемент sij даст ко u 0 u4 S1 = личество путей длины k из вершины xi в вершину x j.

u u u3 6 u Задача 5.1. Для графа, приведенного на рис. 34 слева, 0 u 9 найти все пути длины 3 (то есть, найти все пути, содержащие ровно три дуги).

Рисунок 36 Рисунок 49 Продолжение таблицы Выполняем символьное умножение матриц:

0 u7 0 u u1 u5 u1 u u 0 u4 0 u2 0 u4 0 2 столбец S = 2 = u10 u 6 u u u3 0 u3 6 u 0 u9 0 u8 0 u 9 u1u2 + u5u6 + u7u9 u1u4 + u7u8 u5u u5u 3столбец u2u1 + u4u3 u2u7 + u4u u4u6 u2u = u3u2 + u10u9 u6u5 + u3u4 + u10u u6u1 u6u u9u7 + u8u u9u1 + u8u u8u6 u9u 4 столбец u1u2 + u5u6 + u7u9 u1u4 + u7u8 u5u u5u u2u1 + u4u3 u2u7 + u4u u4u6 u2u S = u3u2 + u10u9 u6u5 + u3u4 + u10u u6u1 u6u u9u7 + u8u10 Заметим, что число слагаемых в каждом элементе полученной u9u1 + u8u u8u6 u9u матрицы равно числу элементов матрицы S 3 :

0 u u1 u 5 Рассмотрим, например, сумму 4 5 u 0 u4 5 2 5 2..

u10 S =. Она соответствует четырем путям u u3 6 5 5 4 u 0 из вершины 1 в вершину 1:

0 u 9 5 2 В таблице 2 приведена матрица S 3 по столбцам.

1- u5 -3- u3 -2- u2 -1, 1- u1 -2- u4 -3- u6 -1, 1- u7 -4- u8 -3- u6 -1, Таблица 1- u5 -3- u10 -4- u9 -1.

Алгоритм Дейкстры для поиска кратчайшего пути между заданной парой вершин 1 столбец Пусть G = (Х, А) — связный граф, каждой дуге которого приписано некоторое число а(x, y) 0. Задача построения кратчайшего пути между заданной парой вершин sХ и tХ заключается в том, чтобы из множества путей, соединяющих 51 указанные вершины, найти такой, суммарная длина дуг кото рого минимальна.

Для решения задачи можно воспользоваться алгоритмом Дейкстры [13]. Приведем его описание по шагам.

Шаг 1. Перед началом выполнения алгоритма все вер шины не окрашены. Каждой вершине хХ в ходе выполнения алгоритма присваивается число d(x), равное длине кратчайше го пути из s в х, включающего только окрашенные вершины.

Положить d(s)=0, d(x)= для всех х, отличных от s. Ок расить вершину s и положить y=s (y – последняя из окрашен ных вершин).

Шаг 2. Для каждой неокрашенной вершины х следую щим образом пересчитать величину d(x):

Рисунок d(x)=min {d(x), d(x)+a(y, x)}.

Если d(x)= для всех неокрашенных вершин х, закон чить процедуру алгоритма: в заданном графе отсутствуют пути между указанной парой вершин. В противном случае окрасить ту из вершин x, для которой величина d(x) является наимень шей. Положить y=x.


Шаг 3. Если y=t, закончить процедуру: кратчайший путь из вершины s в вершину t найден. В противном случае перейти Рисунок 39 Рисунок к шагу 2. d(3)=min{d(3), d(2)+с(2, 3)}=min {, 5+4}=9;

Задача 5. 2. В заданном графе G (рис. 38) найти крат- d(5)= min{d(5), d(2)+с(2, 5)}=min {6, 5+}=6;

чайший путь между вершинами 1 и 10.

d(4)= min{d(4), d(2)+с(2, 4)}=min {, 5+9}=14;

Решение. Перед началом выполнения алгоритма полагаем d(x)= для всех х1, 2, 3, 4, 5.

d(1)=0, d(x)= для всех х1;

вершина 1 – последняя из окра Так как минимум выпал на вершину 5, то y=5 – последняя шенных вершин.

из окрашенных вершин (рис. 40).

d(2)=min{d(2), d(1)+с(1, 2)}=min {, 0+5}=5;

d(3)=min{d(3), d(5)+с(5, 3)}=min {9, 5+}=9;

d(5)= min{d(5), d(1)+с(1, 5)}=min {, 0+6}=6;

d(4)= min{d(4), d(5)+с(5, 4)}=min {14, 6+4}=10;

d(x)= для всех х1, 2, 5.

d(7)= min{d(7), d(5)+с(5, 7)}=min {, 6+5}=11;

Так как минимум выпал на вершину 2, то y=2 – последняя из d(x)= для всех х1, 2, 3, 4, 5, 7.

окрашенных вершин (рис. 39).

53 Так как минимум выпал на вершину 3, то y=3 – последняя из окрашенных вершин (рис. 41).

Рисунок Рисунок 41 d(6)=min{d(6), d(4)+с(4, 6)}=min {, 10+3}=13;

d(7)= min{d(7), d(4)+с(4, 7)}=min {11, 10+}=11;

d(4)=min{d(4), d(3)+с(3, 4)}=min {10, 9+3}=10;

d(x)= для всех х1, 2, 3, 4, 5, 6, 7.

d(5)=min{d(5), d(3)+с(3, 5)}=min {6, 9+2}= Так как минимум выпал на вершину 7, то y=7 – последняя из (оценка не уменьшилась, то есть лучший путь не найден);

окрашенных вершин (рис. 43).

d(7)= min{d(7), d(3)+с(3, 7)}=min {11, 9+}=11;

d(6)=min{d(6), d(7)+с(7, 6)}=min {13,11+}=13;

d(x)= для всех х1, 2, 3, 4, 5, 7.

d(8)=min{d(8), d(7)+с(7, 8)}=min(,11+2}=13;

Так как минимум выпал на вершину 4 (из неокрашенных), то d(10)=min{d(10), d(7)+с(7, 10)}=min {,11+8}=19;

y=4 – последняя из окрашенных вершин (рис. 42).

d(x)= для х=9.

Так как минимум выпал на вершину 6, то y=6 – последняя из окрашенных вершин (рис. 44).

d(7)= min{d(7), d(6)+с(6, 7)}=min {11,13+5}= (оценка не уменьшилась, то есть лучший путь не найден);

d(8)=min{d(8), d(6)+с(6, 8)}=min {13,13+}=13;

d(9)=min{d(9), d(6)+с(6, 9)}=min {,13+7}=20;

d(10)=min{d(10), d(6)+с(6,10)}=min {19,13+6}=19.

Рисунок 55 Так как минимум выпал на вершину 8 (из неокрашенных), то Так как минимум выпал на вершину 10, то y=10, и на этом ал y=8 – последняя из окрашенных вершин (рис. 45). горитм заканчивает работу (рис. 46).

Рисунок Рисунок Таким образом, кратчайший путь из вершины 1 в верши ну 10 проходит через промежуточные вершины 5 и 7 (рис. 47).

Длина этого пути равна 19.

Рисунок d(9)=min{d(9), d(8)+с(8, 9)}=min {20,13+}=20;

d(10)=min{d(10), d(8)+с(8,10)}=min {19,13+7}=19.

Рисунок 57 Решение задачи о поиске кратчайшего пути с использованием надстройки MS EXCEL «Поиск решения»

Для получения математической модели задачи введем булевы переменные xij, которые интерпретируются следую щим образом: xij=1, если дуга (i, j) входит в маршрут;

xij=0, ес ли дуга (i, j) не входит в маршрут. Тогда математическая мо дель может иметь, например, такой вид, как на рис. 48 [12].

Ограничение (2) требует, чтобы искомый путь начинался в вершине s. Ограничение (3) требует, чтобы искомый путь заканчивался в вершине t. Ограничение (4) требует, чтобы ис комый путь был связным, то есть проходил через вершины графа G. Ограничение (5) требует, чтобы все переменные мо дели были булевыми.

n n c x min, (1) ij ij x i =1 j = n Рисунок n xsj xis = 1;

(2) Математическая постановка такой индивидуальной зада j =1 i = чи имеет следующий вид:

n n (3) xtj xit = 1;

5 x12 + 6 x15 + 4 x 23 + 9 x 24 + 3x 34 + 2 x 35 + 3x 46 + 4 x 54 + 5 x57 + 7 x 69 + j =1 i = n n xij x ji = 0 (i {, 2,..., n}, i s, i t );

(4) + 6 x 6,10 + 5 x 67 + 2 x 78 + 8 x 7,10 + 7 x8,10 + 10 x 9,10 min, i =1 x i = x {0,1} (i, j {, 2,..., n}).

1 где множество ограничений выглядит так, как на рис. 50.

(5) ij Воспользуемся надстройкой «Поиск решения», входящей Рисунок в состав MS EXCEL. Расположим исходные данные на рабо Задача 5.3. Используя приведенный на рис. 49 граф, най чем листе, например, так, как на рис. 51. В ячейках показаны ти кратчайший путь между вершинами 1 и 10 с использовани ем надстройки «Поиск решения». формулы, связывающие переменные модели. Целевая функция Решение. В заданном графе 10 вершин и 16 дуг. Следо- находится в ячейке Е19. На рис. 52 приведено окно диалога вательно, переменными математической модели этой индиви- надстройки перед запуском на выполнение. На рис. 53 показан дуальной задачи о построении кратчайшего пути являются 16 результат работы надстройки, а на рис. 54 – путь из вершины переменных: в вершину 10 минимальной длины. Это значение совпадает с x12, x15, x 23, x 24, x34, x35, x 46, x54, x57, x 69, x 6,10, x 67, x 78, x 7,10, решением, полученным в соответствии с алгоритмом x8,10, x9,10. Дейкстры.

59 x12 + x15 = 1;

x + x + x + x = 1;

6,10 7,10 8,10 9, x12 x23 x24 = 0;

x23 x34 x35 = 0;

x + x x = 0;

34 24 x35 + x15 x54 x57 = 0;

x x x x = 0;

46 67 69 6, x57 + x67 x78 x7,19 = 0;

x78 x8,10 = 0;

x x = 0;

69 9, Рисунок x12, x15, x23, x24, x34, x35, x46, x54, x57, x69, x6,10, x67, x78, x7,10, x8,10, x9,10. {0, 1}.

Рисунок Рисунок 51 Рисунок 61 n состоит в определении матрицы D, представляющей крат чайшие пути между всеми вершинами исходного графа. В ал горитме Флойда в качестве исходной выступает матрица D.

Затем по ней вычисляется матрица D, а по ней – матрица D 2 и т.д. Процесс повторяется до тех пор, пока не будет вы n числена матрица D.

Предположим, что нам известны 1) кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование толь ко первых (m-1) вершин;

2) кратчайший путь из вершины m в вершину j, в котором в качестве промежуточных допускается использование толь Рисунок ко первых (m-1) вершин;

3) кратчайший путь из вершины i в вершину j, в котором в Поиск всех кратчайших путей (алгоритм Флойда) качестве промежуточных допускается использование толь Перенумеруем все вершины исходного графа целыми ко первых (m-1) вершин.

m числами от 1 до n. Обозначим через d ij длину кратчайшего пу По предположению исходный граф не может содержать кон ти из вершины i в вершину j, который в качестве промежуточ- туров отрицательной длины. Следовательно, один из двух пу ных может содержать только первые m вершин графа. Если же тей – путь, совпадающий с путем, описанным в пункте 3, или между вершинами i и j не существует ни одного пути указан путь, являющийся объединением путей из пунктов 1–2 – дол ного типа, то условно будем считать что d ij =. Из данного m жен быть кратчайшим путем из вершины i в вершину j, в кото m определения величины d ij следует, что величина d ij представ- ром в качестве промежуточных допускается использование ляет собой длину кратчайшего пути из вершины i в вершину j, только первых m вершин. Таким образом, не имеющего промежуточных вершин, то есть, длину крат { } чайшей дуги, соединяющей вершины i и j (если такие дуги d ij = min d im1 + d mj1,d ij 1.

m m m m присутствуют в графе). Будем считать, что d ij 0 для всех i и j (1 i j n). Для любой вершины i положим d ii = 0.

Приведем пошаговое описание алгоритма Флойда [13].

Шаг 1. Пронумеровать вершины исходного графа целы m Обозначим через D матрицу размера nn, элемент ко ми числами от 1 до n. Определить матрицу D, задав величину торой, расположенный на пересечении i-й строки и j-го столб m ца, совпадает с d ij. Если в исходном графе известна длина каждого ее элемента d ij равной длине кратчайшей дуги, со каждой дуги, то можно сформировать матрицу D. Наша цель единяющей вершины i и j. Если в исходном графе указанные 63 Таблица вершины не соединяются дугами, положить d ij =. Кроме { } Соответст d ij = min d i0 + d10j, d ij 1 того, положить d ii = 0 для всех i (1in).

вующие пути Шаг 2. Для целого m, последовательно принимающего d11 = d11 = 1 значения 1, 2, …, n, определить по величинам элементов мат рицы D m1 величины элементов матрицы D m, используя соот- (1, 2) d12 = d12 = 1 ношение (1, 3) d13 = d13 = { } 1 d ij = min d im1 + d mj1, d ij 1.

m m m m (1, 4) d14 = d14 = 1 При определении величины каждого элемента матрицы (2, 1) d 21 = d 21 = 1 m D фиксировать соответствующий кратчайший путь. По окон d 22 = n n чании данной процедуры величина элемента d ij матрицы D { } d 23 = min d 21 + d13, d 23 = min{2 + 2,7} = определяет величину кратчайшего пути, ведущего из вершины (2, 1), (1, 3) 1 0 0 i в вершину j.

= min{d, d } = min{2 + 1, } = 3 (2, 1), (1, 4) + d 1 0 0 d m Строки и столбцы матрицы D, для которых i=m и j=m, 21 будем называть базовыми. Нетрудно заметить, что в таких (3, 1) d31 = d31 = строках и столбцах значения матрицы можно не пересчиты- 1 вать, так как они полностью совпадают с соответствующими { } d32 = min d31 + d12, d32 = min{6 + 1,5} = 5 (3, 2) 1 0 0 m значениями матрицы D.

d33 = Задача 5.4. Для графа, приведенного на рис. 55, найти { } d34 = min d31 + d14, d34 = min{6 + 1,2} = 2 (3, 4) кратчайшие пути между любой парой вершин. 1 0 0 (4, 1) Решение. Матрица D для данного графа приведена на. d 41 = d 41 = 1 { } d 42 = min d 41 + d12, d 42 = min{ + 1, } = рис. 55 слева. Весь процесс вычислений приведен в таблице 3 (4, 1), (1, 2) 1 0 0 = min{d } = min{1 + 2,4} = 0 1 2 (4, 1), (1, 3) + d13, d 1 0 0 d 2 D0 = d 44 = 0 1 4 0 2 3 Аналогично определяются матрицы D, D, D. Полу ченные результаты приводятся в таблице 4.


Рисунок 65 Таблица 4 1 0 1 2 2 Матрицы Кратчайшие пути 2 0 1 2 3 D = R = 0 2 (1,4) 0 1 2 1 (1,2) (1,3) 65 1 2 1 4 0 1 (2,1) (2,1), (1,3) (2,1), (1,4) 2 0 4 3 2 D = (3,1) (3,4) 2 (3,2) 650 0 1 1 1 2 2 (4,1) (4,1), (1,2) (4,1), (1,3) 1 2 3 0 2 0 4 3 1 2 1 D = R = 1 2 6 5 0 1 2 (1,4) 0 1 2 1 (1,2) (1,3) 1 0 1 2 3 1 (2,1) ( 2,1), (1,3) ( 2,1), (1,4) 2 0 4 0 1 1 D = 2 1 (3,1) (3,4) 5 0 2 (3,2) 6 (4,1) (4,1), (1,2) ( 4,1), (1,3) 1 2 1 2 0 4 1 2 3 0 R = D = 2 1 2 6 5 0 0 1 2 1 (1,4) 1 (1,2) (1,3) 1 0 1 2 3 2 0 4 3 (2,1) (2,1), (1,3) (2,1), (1,4) D = 0 1 1 2 3 1 4 0 2 (3,4), (4,1) (3,4), (4,1), (1,2) (3,4) 3 1 2 3 0 2 0 4 (4,1) 1 2 1 (4,1), (1,2) (4,1), (1,3) D = R = 3 2 2 3 6 5 0 1 0 1 1 1 2 Для решения реальных задач приведенный выше способ 1 2 3 0 1 2 формирования кратчайших путей малопригоден.

Удобно ввести в рассмотрение матрицу маршрутов R. На 1 2 1 2 0 4 () R = D = 4 3 4 0 m-ой итерации она определяется как R = rij, где rijm — m m 1 1 1 1 2 3 первый промежуточный узел кратчайшего пути из i в j, выби- раемый среди множества {1, 2,…, m} (ijm). Алгоритм начи () нает работу при R = rij, где rij0 = j. На m-ой итерации эле 0 0 Чтобы воспользоваться матрицей R для определения пути, например, из вершины 3 в вершину 2, просматриваем m мент rij может быть получен из следующего соотношения: элемент r32. Так как он равен 4, это означает, что вершина с m, d ij -1 d im1 + d mj1 номером 4 является первой промежуточной в этом пути. Далее m m m r = m m просматриваем элемент r42. Так как он равен 1, это означает, ij rij.

что вершина с номером 1 является второй промежуточной в этом пути. Далее просматриваем элемент r12. Так как элемент Для рассмотренного выше примера имеем:

67 =ЕСЛИ(ДВССЫЛ(АДРЕС(СТРОКА(A11);

$G$16);

ИСТИНА)+ равен номеру конечной вершины 2, получаем, что искомый путь проходит по дугам (3, 4), (4, 1) и (1, 2) (что соответствует +ДВССЫЛ(АДРЕС($F$16;

СТОЛБЕЦ(A11));

ИСТИНА)A11;

(7) результату из таблицы 3).

$G$16;

I11) Решение задачи о поиске всех кратчайших путей =ЕСЛИ(ДВССЫЛ(АДРЕС(СТРОКА(A16);

$G$21);

ИСТИНА)+ с использованием MS EXCEL (8) +ДВССЫЛ(АДРЕС($F$21;

СТОЛБЕЦ(A16));

ИСТИНА)A16;

0 Расположим исходные данные D, R индивидуальной $G$21;

I16) задачи на рабочем листе, например, так, как на рис. 56. Здесь через 1000 обозначено отсутствие соответствующей дуги в ис 1 2 3 4 1 2 3 ходном графе. Матрицы D, D, D, D и R, R, R, R получены по формулам вида (1)–(4) и (5)–(8) соответственно, а затем распространены на соответствующие диапазоны.

=МИН(ДВССЫЛ(АДРЕС(СТРОКА(A1);

$G$6);

ИСТИНА)+ (1) +ДВССЫЛ(АДРЕС($F$6;

СТОЛБЕЦ(A1));

ИСТИНА);

A1) =МИН(ДВССЫЛ(АДРЕС(СТРОКА(A6);

$G$11);

ИСТИНА)+ (2) +ДВССЫЛ(АДРЕС($F$11;

СТОЛБЕЦ(A6));

ИСТИНА);

A6) МИН(ДВССЫЛ(АДРЕС(СТРОКА(A11);

$G$16);

ИСТИНА)+ (3) +ДВССЫЛ(АДРЕС($F$16;

СТОЛБЕЦ(A11));

ИСТИНА);

A11) =МИН(ДВССЫЛ(АДРЕС(СТРОКА(A16);

$G$21);

ИСТИНА)+ (4) +ДВССЫЛ(АДРЕС($F$21;

СТОЛБЕЦ(A16));

ИСТИНА);

A16) =ЕСЛИ(ДВССЫЛ(АДРЕС(СТРОКА(A1);

$G$6);

ИСТИНА)+ +ДВССЫЛ(АДРЕС($F$6;

СТОЛБЕЦ(A1));

ИСТИНА)A1;

(5) $G$6;

I1) =ЕСЛИ(ДВССЫЛ(АДРЕС(СТРОКА(A6);

$G$11);

ИСТИНА)+ +ДВССЫЛ(АДРЕС($F$11;

СТОЛБЕЦ(A6));

ИСТИНА)A6;

(6) $G$11;

I6) Рисунок 69 На рис. 56 показаны используемые в формулах вспомо- 1 2 3 4 5 6 7 8 9 гательные значения для указания базовых номеров строк и 0 2 9 столбцов. 0 3 3 4 0 9 3 Задачи для самостоятельного решения 0 5 Граф содержит 10 вершин. Расстояния между вершинами 4 0 3 заданы таблицей. Найти кратчайший путь между вершинами 1 0 1 10 и 10 (номера вариантов указаны в верхнем левом углу табли- 0 3 цы). 0 0 1 2 3 4 5 6 7 8 9 1 0 8 9 0 3 8 2 2 1 2 3 4 5 6 7 8 9 0 5 6 3 0 2 9 0 6 4 0 2 6 3 2 0 9 5 0 9 2 0 5 4 6 0 2 0 5 7 7 0 2 0 8 0 10 6 0 9 0 3 10 0 0 1 2 3 4 5 6 7 8 9 2 0 3 10 1 2 3 4 5 6 7 8 9 0 4 3 7 0 7 3 0 5 5 0 10 1 3 0 6 0 2 10 9 0 5 0 8 0 6 9 9 0 2 0 2 0 6 5 0 0 4 0 0 0 71 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 6 0 10 2 0 10 7 1 0 5 6 1 0 5 4 8 2 0 10 5 0 10 1 3 0 6 0 2 4 9 0 3 3 0 8 5 0 2 2 6 0 9 5 6 0 5 5 0 3 7 0 6 0 8 0 5 0 9 0 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 7 0 10 5 0 8 5 1 0 1 3 7 0 2 10 7 2 0 4 5 0 4 1 3 0 7 0 1 4 7 0 1 4 0 6 5 0 10 9 2 0 7 3 6 0 6 8 0 3 7 0 3 0 8 0 3 0 9 0 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 8 0 6 7 0 7 10 1 0 4 8 9 0 4 5 1 2 0 6 6 0 1 10 3 0 3 0 9 4 5 0 5 8 0 3 5 0 6 3 10 0 3 5 6 0 6 5 0 2 7 0 7 0 8 0 4 0 9 0 73 1 2 3 4 5 6 7 8 9 0 4 5 0 12 10 7 0 4 10 0 10 14 0 6 0 7 13 0 13 0 0 6. Задача о максимальном потоке ( ) и минимальном разрезе в сети Разрезом X, X в сети G = (N, А), отделяющим узлы s и Пусть G = (N, А) – связный граф, в котором выделены t, называется множество дуг, где s X, t X. При этом две вершины: s – источник, t – сток. Каждой дуге (x, y) графа X X =, X X = N.

поставлено в соответствие неотрицательное число с(x, y), ко Приведем формулировку теоремы о максимальном по торое интерпретируется как максимальное количество единиц токе и минимальном разрезе.

некоторого товара, которое может быть доставлено из верши ны x в вершину y за единицу времени. Это число принято на- Теорема [25]. Для любой сети максимальная величина зывать пропускной способностью дуги. Такой граф называют потока из s в t равна минимальной пропускной способности сетью, а его вершины – узлами. разреза, отделяющего s и t.

Стационарный поток величины v из s в t в сети G = (N, Задача построения максимального потока между задан А) есть функция f, отображающая множество А в множество ной парой вершин sN и tN заключается в том, чтобы из неотрицательных чисел, удовлетворяющих линейным уравне множества путей, соединяющих указанные вершины, найти ниям и неравенствам следующего вида:

такие, по которым можно пропустить максимальное количест во единиц потока в единицу времени. При этом должны со v, x = s;

блюдаться следующие ограничения:

x )f ( x, y) yB ( x )f ( y, x ) = 0, x s, t;

поток по каждой дуге не должен превышать ее про v, x = t ;

x A ( пускную способность;

поток из источника s равен потоку, приходящему в f ( x, y ) c( x, y ) ( x, y ), сток t;

для промежуточных вершин количество единиц по где А(х) — подмножество множества N, включающее верши тока, попавшего в этот узел, должно в точности рав ны y, являющиеся концами дуг с началом в вершине х;

В(х) — няться количеству единиц потока, вышедшего из подмножество множества N, включающее вершины y, являю этого узла.

щиеся началом дуг, входящих в вершину х.

75 ( ) Для решения задачи можно воспользоваться алгоритмом узлу y. Вообще, если узел y имеет пометку x +, ( y ), то f(x, y) ( ) расстановки пометок Форда-Фалкерсона [25].

заменяем на f(x, y)+(t), а если он имеет пометку x, ( y ), то Алгоритм может начинать работу с нулевого потока. За f(x, y) заменяем на f(x, y)-(t) и переходим к узлу х. Когда мы тем вычисления развиваются в виде последовательности «рас достигнем источника s, изменение потока прекращается. Нуж становки пометок» (операция А), каждая из которых либо но стереть все старые пометки и вновь перейти к операции А.

приводит к потоку с большей величиной (операция В), либо заканчивается заключением о том, что рассматриваемый по- Примечание. Пропускные способности дуг должны быть це ток максимален. Все узлы сети находятся в одном из следую лыми неотрицательными числами. В [3] приведен пример с щих состояний: не помечен, помечен и не просмотрен, поме иррациональными пропускными способностями, для которого чен и просмотрен. Вначале все узлы не помечены.

алгоритм приводит к неоптимальному решению.

Операция А (процесс расстановки пометок). Источник s получает пометку (-, (s)=) (источник теперь помечен и не Задача 6.1. Найти максимальный поток и минимальный просмотрен, остальные узлы не помечены). Выбираем любой разрез, отделяющий источник 1 и сток 6 для сети, приведенной помеченный и не просмотренный узел х. Пусть он имеет по ( ) на рис. 57. Пара чисел около каждой дуги означает пропуск метку z ±, ( x). Всем узлам y, которые не помечены и для ко ную способность и поток по дуге соответственно.

( ) торых f(x, y) c(x, y) приписываем пометку x +, ( y ), где ( y ) = min[ ( x), c(x, y)-f(x, y)] (такие узлы y теперь помечены и не просмотрены). Всем узлам y, которые после этого не помечены и для которых f(y, x) ( ) приписываем пометку x, ( y ), где ( y ) = min[ ( x), f(y, x)] (такие узлы y теперь помечены и не просмотрены, а узел х по сле этого помечен и просмотрен).

Этот общий шаг повторяем до тех пор, пока 1) не окажется помеченным и не просмотренным сток t, 2) или же до тех пор, пока нельзя будет пометить ни один узел, а сток t останется непомеченным. Рисунок В первом случае переходим к операции В, а во втором — алго Решение. На рис. 58 показаны пометки, полученные в ритм закончил работу, так как максимальный поток в сети по ходе выполнения операции А на первой стадии работы алго лучен.

ритма. Источник (узел 1) получил пометку (-, ). Затем из узла Операция В (изменение потока). Пусть сток t имеет по- 1 помечаются узлы 2, 3 и 4. Из узла 2 помечается узел 5, а из ( ) ( ) метку y ±, (t ). Если он имеет пометку y +, (t ), то f(y, t) за- узла 3 – сток (узел 6). Так как сток оказался помеченным, пе ( ) реходим к операции В. Сток получил пометку (3+, 2). Следова меняем на f(y, t)+(t);

если он имеет пометку y, (t ), то f(y, t) тельно, f(3, 6) станет равным 0+2=2. Переходим к узлу 3. Так заменяем на f(y, t)-(t). В любом из этих случаев переходим к 77 как он имеет пометку (1+, 2), то поток по дуге (1, 3) станет рав ным 0+2=2.

Рисунок Рисунок Так как в результате выполнения операции В достигнут источник (узел 1), то следует стереть старые пометки и снова перейти к операции А. Состояние сети приведено на рис. 59.

Жирными стрелками указаны дуги, по которым идут две еди ницы потока.

Снова выполняем операцию А. Источник (узел 1) полу чил пометку (-, ). Затем из узла 1 помечаются узлы 2 и 4 (рис.

60). Из узла 2 помечаются узлы 3 и 5, а из узла 3 – сток (узел 6). Так как сток оказался помеченным, переходим к операции В. Сток получил пометку (3+, 1). Следовательно, f(3, 6) станет равным 2+1=3. Переходим к узлу 3. Так как он имеет пометку (2+, 1), то поток по дуге (2, 3) станет равным 0+1=1. Переходим к узлу 1 и увеличиваем поток по дуге (1+, 3), то поток по дуге (1, 2): он станет равным 0+1=1. Следовательно, поток в сети стал равен 3. На рис. 60 жирными стрелками указано новое Рисунок увеличение потока в сети.

79 Рисунок На рис. 61 показано новое состояние сети с потоком в 3 Рисунок единицы. На рис. 62–67 показано выполнение операций А и В, которые привели к увеличению потока в сети до 8 единиц.

Рисунок 62 Рисунок 81 Рисунок Рисунок На рис. 68 показана попытка нахождения нового прорыва в сети. При этом вершины 2 и 5 получили пометки (1+, 1) и (2+, 1) соответственно. Заметим, что в данном случае удается по метить узел 3 пометкой (5-, 1), так как по дуге (3, 5) есть нену левой поток. После этого удается пометить вершину 4 помет кой (3+, 1). Однако дальнейшее выполнение алгоритма невоз можно, так как дуги (5, 6), (3, 6) и (4, 6) имеют нулевую оста точную пропускную способность. Так как не удается пометить вершину 6 (сток), то на предыдущем шаге выполнения алго ритма получен максимальный поток величины 8.

Поскольку помеченными оказались вершины 1–5, а не помеченной – вершина 6, то минимальный разрез, отделяющий источник и сток, представляет собой совокупность дуг (X, X ) = {(5, 6), (3, 6), (4, 6) }, где X = {1, 2, 3, 4, 5 }, X = {6}.

Состояние сети приведено на рис. 68. Жирными стрелка ( ) Рисунок ми изображен минимальный разрез X, X.

83 n x (1) max, sj x j = n n x sj xii = 0;

(2) j =1 i = n n x ij x ji = 0 (i {, 2,..., n}, i s, i t );

(3) i =1 i = 0 xij cij (4) xij Z 1 (i, j {, 2,..., n}). (5) Рисунок Задача 6.2. Используя приведенную на рис. 70 сеть, най ти максимальный поток с использованием надстройки «Поиск решения».

Рисунок Решение задачи о максимальном потоке и минимальном разрезе с использованием надстройки MS EXCEL «Поиск решения»

Для получения математической модели задачи введем неотрицательные целочисленные переменные xij, которые ин терпретируются как величина потока по дуге (i, j). Тогда мате матическая модель может иметь, например, такой вид, как на рис. 69 [12].

Ограничение (2) требует, чтобы величина потока, выхо- Рисунок дящего из источника s, была равна величине потока, пришед- Решение. Расположим исходные данные на рабочем лис шего в вершину t. Ограничение (4) требует, чтобы искомый те так, как на рис. 71. В столбец Е введены ограничения в со путь был связным, то есть проходил через вершины графа G. ответствии с моделью для данной индивидуальной задачи. На Ограничение (5) требует, чтобы все переменные модели были рис. 72 приведено окно диалога надстройки «Поиск решения», неотрицательными целочисленными переменными. а на рис. 73 – полученное решение. Величина максимального 85 потока в точности равна полученному значению при использо вании алгоритма Форда-Фалкерсона.

Рисунок 71 Рисунок Задачи для самостоятельного решения Сеть содержит 10 вершин (рис. 74). Пропускные способ ности дуг заданы таблицей. Найти максимальный поток между вершинами 1 и 10 и соответствующий минимальный разрез (номера вариантов указаны в верхнем левом углу таблицы).

Рисунок Рисунок 87 1 1 2 3 4 5 6 7 8 9 10 4 1 2 3 4 5 6 7 8 9 1 0 8 2 9 0 0 0 0 0 0 1 0 10 10 10 0 0 0 0 0 2 0 0 0 0 3 0 2 0 0 0 2 0 0 0 0 10 0 10 0 0 3 0 0 0 0 0 7 0 0 0 0 3 0 0 0 0 0 1 0 0 0 4 0 0 0 0 0 3 2 0 0 0 4 0 0 0 0 0 6 7 0 0 5 0 0 0 0 0 0 0 1 0 1 5 0 0 0 0 0 0 0 4 0 6 0 0 0 0 0 0 4 0 9 0 6 0 0 0 0 0 0 4 0 3 7 0 0 0 0 0 0 0 0 0 10 7 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 2 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 4 9 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 2 1 2 3 4 5 6 7 8 9 10 5 1 2 3 4 5 6 7 8 9 1 0 5 5 4 0 0 0 0 0 0 1 0 6 5 6 0 0 0 0 0 2 0 0 0 0 6 0 3 0 0 0 2 0 0 0 0 10 0 3 0 0 3 0 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 5 0 0 0 4 0 0 0 0 0 5 4 0 0 0 4 0 0 0 0 0 7 3 0 0 5 0 0 0 0 0 0 0 9 0 7 5 0 0 0 0 0 0 0 8 0 6 0 0 0 0 0 0 1 0 5 6 0 0 0 0 0 0 3 0 6 7 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 3 1 2 3 4 5 6 7 8 9 6 1 2 3 4 5 6 7 8 9 1 0 9 6 7 0 0 0 0 0 1 0 10 7 4 0 0 0 0 0 2 0 0 0 0 2 0 8 0 0 2 0 0 0 0 7 0 6 0 0 3 0 0 0 0 0 7 0 0 0 3 0 0 0 0 0 7 0 0 0 4 0 0 0 0 0 1 5 0 0 4 0 0 0 0 0 4 2 0 0 5 0 0 0 0 0 0 0 10 0 5 0 0 0 0 0 0 0 3 0 6 0 0 0 0 0 0 10 0 5 6 0 0 0 0 0 0 7 0 6 7 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 89 7 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 1 0 5 2 6 0 0 0 0 0 0 1 0 3 10 9 0 0 0 0 0 2 0 0 0 0 6 0 9 0 0 0 2 0 0 0 0 2 0 2 0 0 3 0 0 0 0 0 6 0 0 0 0 3 0 0 0 0 0 2 0 0 0 4 0 0 0 0 0 9 8 0 0 0 4 0 0 0 0 0 4 9 0 0 5 0 0 0 0 0 0 0 6 0 7 5 0 0 0 0 0 0 0 6 0 6 0 0 0 0 0 0 9 0 10 0 6 0 0 0 0 0 0 10 0 3 7 0 0 0 0 0 0 0 0 0 9 7 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 4 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 6 9 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 8 1 2 3 4 5 6 7 8 9 1 0 7 9 6 0 0 0 0 0 1 0 2 9 2 0 0 0 0 0 2 0 0 0 0 5 0 10 0 0 2 0 0 0 0 2 0 1 0 0 3 0 0 0 0 0 6 0 0 0 3 0 0 0 0 0 2 0 0 0 4 0 0 0 0 0 2 10 0 0 4 0 0 0 0 0 8 6 0 0 5 0 0 0 0 0 0 0 1 0 5 0 0 0 0 0 0 0 1 0 6 0 0 0 0 0 0 6 0 9 6 0 0 0 0 0 0 3 0 6 7 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 9 1 0 8 6 4 0 0 0 0 0 1 0 5 10 2 0 0 0 0 0 0 2 0 0 0 0 9 0 2 0 0 2 0 0 0 0 2 0 9 0 0 0 3 0 0 0 0 0 8 0 0 0 3 0 0 0 0 0 8 0 0 0 0 4 0 0 0 0 0 2 2 0 0 4 0 0 0 0 0 5 7 0 0 0 5 0 0 0 0 0 0 0 5 0 5 0 0 0 0 0 0 0 1 0 1 6 0 0 0 0 0 0 1 0 5 6 0 0 0 0 0 0 2 0 3 0 7 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 4 8 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 9 9 0 0 0 0 0 0 0 0 0 6 10 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 91 7. Решение задачи коммивояжера длины контура. Затем множество всех гамильтоновых конту ров разбивается на два подмножества. Первое подмножество методом ветвей и границ состоит из гамильтоновых контуров, которые включают неко Пусть n требований обслуживаются одним прибором. торую дугу (i, j). Обозначим это множество {(i, j)}. Второе Все требования поступают на обслуживание в момент времени множество состоит из гамильтоновых контуров, которые не d=0. Длительность обслуживания требования k (k=1, 2,…, n) включают эту дугу. Обозначим его {(i, j )}. Для каждого из равна tk единиц времени. Если требование k обслуживается подмножеств {(i, j )} и {(i, j )} определяется нижняя граница первым, то для подготовки прибора к обслуживанию этого требования необходимо 0k единиц времени. Если требование j (i, j ) длины гамильтоновых контуров и. Каждая новая обслуживается непосредственно после требования i, то для пе- (i, j ) реналадки прибора с обслуживания требования i на обслужи- граница оказывается не меньше нижней границы всего множе вание требования j необходимо ij единиц времени (1ijn). ства гамильтоновых контуров (R). Среди двух подмножеств контуров {(i, j )} и {(i, j )} выбирается подмножество с мень Требуется так организовать процесс обслуживания (то есть указать такую их последовательность), чтобы общее время об- шей нижней границей. Это подмножество снова разбивается на служивания всех требований было минимальным. Нетрудно два подмножества. Для вновь образованных подмножеств на заметить, что искомой последовательности при этом должно ходится нижняя граница. Процесс разбиения подмножеств соответствовать наименьшее время пуско-наладочных работ. В аналогичным образом продолжается до тех пор, пока не будет ряде случаев желательно также учитывать время k0, требуемое выделено подмножество, содержащее единственный гамиль на приведение обслуживающего устройства в исходное со- тонов контур. Взаимосвязь подмножеств, полученных в ре стояние, если требование k обслуживается последним. Таким зультате разбиения, изображается в виде дерева, вершинам ко образом, необходимо найти такую последовательность торого приписываются нижние границы.

=(i1, i2,…,in) обслуживания требований, чтобы величина Получив гамильтонов контур, просматривают оборван n ные ветви дерева и сравнивают нижние границы множеств, 0i1 + ik ik +1 + in 0 соответствующих оборванным ветвям, с длиной полученного гамильтонова контура (рекорда). Если нижние границы под k = была наименьшей. множеств, соответствующих оборванным ветвям, окажутся Эта задача допускает простую графическую интерпре- меньше рекорда, то эти ветви развивают по тому же правилу. В тацию. Рассмотрим полный симметрический ориентированный результате развития ветвей могут быть получены новые га граф (X,U), где X={0,1,…,n} – множество вершин, U – множе- мильтоновы контуры. В этом случае рекорд берется равным ство дуг. Каждой дуге (i, j) графа приписано число ij. Требу- наименьшей из длин гамильтоновых контуров. Решение задачи ется найти контур, проходящий через каждую вершину один и считается законченным, если нижние границы обозванных только один раз (гамильтонов контур), которому соответствует ветвей окажутся не меньше рекорда. В качестве оптимального наименьшая длина. Под длиной контура понимается величина, контура выбирается контур с наименьшей длиной.



Pages:   || 2 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.