Геометрия окружностей - Учебное пособие (Мендель В.В.)

Графы и сети

Пояснительная записка

Как составить маршрут путешествия, как спроектировать городскую транспортную сеть, соединить компьютеры локальной сетью, составить график выполнения комплекса работ? На эти и другие вопросы позволяет ответить раздел прикладной математики, который называется « Методы сетевого планирования и управления», или « сетевой анализ».

Сетевой анализ берет свое начало с задачи Эйлера о кенигсбергских мостах: « Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост…»,- из письма Л. Эйлера от 13 марта 1736 г. Спустя более века Джеймс Клерк Максвелл и Густав Роберт Кирхгофф, исследуя электрические сети, сформулировали некоторые принципы сетевого анализа. В настоящее время задачи подобного рода широко используются в теории и практике принятия управленческих решений., поэтому мы считаем целесообразным включить данный курс в образовательную программу летней физико-математической школы.

Математическим аппаратом для данных задач является теория графов, с которой учащиеся знакомы по материалам зимних сессий. Кроме того, благодаря специальной структуре сетевых задач, для их решения получено большое число эффективных алгоритмов, которые легко реализуются  с помощью ЭВМ.

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

Тематическое планирование

п/п

Темы занятий

Количество часов

 

Понятие графа. Виды графов. Способы задания графов. Теорема Эйлера.

4

 

 

Сети. Основные понятия.

2

 

Задача кратчайшего пути. Алгоритм решения.

4

 

 Задача минимизации дерева расстояний. Алгоритм решения.

2

 

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

4

 

Сетевая модель управления комплексом работ. Построение сетевых моделей. Метод критического пути.

4

Итого

20

Текст пособия

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

           В реальных задачах сеть может представлять собой, например, сеть дорог или комплекс взаимосвязанных работ, или сеть связанных между собой объектов. Над каждой ветвью пишется число (или два числа), которое называется величиной ветви (или, если чисел пара, то величиной ветви в прямом и  обратном направлении). Это может быть длина пути от одного пункта до другого, стоимость перевозки, количество дней, за которые может быть выполнена работа и т. д.

         

Рассмотрим насколько задач:

 

I Задача минимизации дерева расстояний

  

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

 

Алгоритм решения.

 

п.1 Выбрать произвольно узел сети. Соединить его с узлом, имеющим  минимальную вершину ветви до выбранного узла.

 

п.2 Выбрать следующий узел, имеющий ветвь с минимальной величиной   до  уже  соединенных узлов. В случае равенства расстояний выбрать произвольно один из узлов.

 

п.3  Если все узлы соединены, то задача решена. В противном случаи перейти к п.2

 

II Задача кратчайшего расстояния.

   

Дана сеть. Найти путь от начального узла к конечному, имеющий наименьшую общую продолжительность.

 

Алгоритм решения.

 

п.1 Определяем начальный узел как элемент постоянного множества и приписываем ему величину U1= 0 .

        Определяем элементы соседнего множества как вершины, достижимые из постоянного множества.

 

п.2 Определяем величину       Uj = Ui + Cij ,

      где Ui –величина узла постоянного множества; Cij –величина ветви ij.

Находим узел с минимальным Uj.

 

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

 

п.4  Определяем соседнее множества, которое можно достигнуть из вершин постоянного множества. Если такое множество определить нельзя, то задача решена. В противном случае переходим к п.2.

 

III Задача максимального потока в сети.

 

        Дана сеть, каждая ветвь которой имеет определенную пропускную способность Cij в прямом и обратном направлении. В общем  случае Cij ≠ Cji.

Требуется определить максимально возможный поток в этой сети из начального узла в конечный.

 

Алгоритм решения.

 

п.1  Определим произвольный путь от истока к стоку. Если такой путь определить нельзя, то задача решена.

 

п.2 В выбранном пути определяем ветвь с минимальной пропускной способностью.   Обозначим ее через С.

 

п.3   Уменьшаем пропускные способности ветвей выбранного пути на величину С в прямом направлении и увеличим пропускные способности ветвей выдранного пути в обратном направлении на величину С. Переходим к п.1.

 

IV Метод критического пути.

 

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

 Для решения задачи вводятся параметры событий и работ.

Ранний срок  наступления события j: показывает самый ранний (ожидаемый) срок наступления события и вычисляется по формуле:

                                            ETj=max {ETi+tij},

где ETj- ранний срок наступления события предшествующего события j,  tij – время выполнения работы ij, ЕТ1=0.  

Поздний срок наступления i – это самый поздний срок, в который может наступить событие j для того, чтобы не сорвался срок выполнения всего комплекса работ. Находится по формуле:

                                           LTi= min{LTj -tij},

 где LTi-поздний срок наступления события j, следующего за событием I

                                                     LTкон = ETнач.

Критический срок – это минимальный срок, за который будет выполнен весь комплекс работ. Он определяется критическими работами –работами, требующими наибольших затрат времени. Критические работы определяются критическими событиями i, для которых

                                                     ETi = LTi

Такие события на сети отличаются контрастным цветом, а также отличаются все работы, связывающие эти события. Критический срок tкр=ETкон=LTкон

 

Задачи

 

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

 

N

A

B

C

D

E

F

A

-

9

7

6

10

20

B

9

-

4

8

7

3

C

7

4

-

2

4

8

D

6

8

2

-

10

9

E

10

7

4

10

-

20

F

20

3

8

9

20

-

 

В школьный  компьютерный класс завезли  5 компьютеров, которые требуется связать локальной сетью. Известны расстояния между компьютерами. Требуется связать компьютеры таким образом, чтобы общая длина кабеля была  бы наименьшей.

 

N       N

1

2

3

4

5

1

-

4

5

7

1

2

4

-

3

8

6

3

5

3

-

4

1

4

7

8

4

-

2

5

1

6

1

2

-

 

 

 

 

На  сети дорог найти кратчайший маршрут из начального пункта в конечный.

 

а)

Овал: 2 

                8                                10

Овал: 1 Овал: 5
 

                10           4             8

                                                          12

Овал: 3 Овал: 7
 

                               5                             3             4

Овал: 6                13

                4

Овал: 4
 

 

б)

Овал: 2 

                7                                 6

Овал: 1 Овал: 5
 

                1                             3

                                                           8

Овал: 3 

                               2                             10          

Овал: 6                5      11

                8

Овал: 4
 

 

 На сети дорог найти максимальный поток транспорта от начального пункта к исходному:

 

a)

Овал: 2 

                3(2)                        4(3)   

Овал: 1 Овал: 6
 

                10(7)      8(8)             3(1)

                                                          

Овал: 3                8(6)

                        6(3)                                    2(2)  

Овал: 5                     

               

                                                                  5(4)

 

                  10(7)

Овал: 4
 

 

               

б)

 

Овал: 2 

                3(3)          4(4)     

Овал: 5Овал: 1                1(1)

Овал: 3                                                      5(5)

                                                          

 

             4(4)                  2(2)                 10(10)    8(8)       

                           

Овал: 6Овал: 4               

 

                6(6)

Найти критический путь и критический срок выполнения комплекса работ.

а)                          

Овал: 2 

Овал: 5                 10                               7

Овал: 1
 

                4                            

                                                          

 

                               5                                1         

Овал: 4                     

                8

Овал: 3
 

 

б)                           

 

Овал: 2                2

Овал: 5                6                                  

Овал: 1                                                   4

                                               5

Овал: 7                                      1                      3

Овал: 3                1

                           8                                                

Овал: 6                                     7

               

                                                                   9

Овал: 4 

                 

 

Казинец Виктор Алексеевич

Элементы конечной математики

Пояснительная записка

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

                Цель предлагаемого курса – познакомить слушателей с идеями и методами современной «компьютерной» математики. Вы узнаете, что такое графы, и какие задачи программирования с ними связаны. Еще один интересный раздел – теория кодирования и криптография (наука о методах шифрования). Сегодня это один из самых актуальных разделов конечной математики.

Тематическое планирование

п/п

Темы занятий

Количество часов

 

Бинарные отношения и графы. Матрица отношений. Частичные утверждения. Разбиения. Графы. Ориентированные графы.

6

 

Алгоритмы на графах. Представление. Поиск в глубину.

Кратчайшие пути. Циклы. Основные деревья.

6

 

Двоичные коды. Кодирование и декодирование. Блочные коды. Матричное кодирование. Групповые коды. Таблицы декодирования. Коды Хэмминга.

4

 

Элементы криптографии. Традиционная криптография.

Криптосистемы с открытым ключом.

4

Итого

20

Текст пособия

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

За рамками программы остаются конечные множества, их свойства и методы работы с ними. В настоящее время интерес к таким множествам и методам работы с ними существенно возрос. Это связано в первую очередь с названием дисциплины «Информатика», в частности с программированием. Так как часто задачи программирования и их решение связаны с обычным пересчетом элементов конечного множества. Мы предполагаем в данной работе ознакомить учащихся с наиболее типичными понятиями и методами связанными с конечными множествами.