Обзор литературы (стр. 3 )

Определение: Событием называют факт окончания всех работ, в него входящих и начала всех работ, из него выходящих.

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

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

Правила построения сетевого графика

1.В сетевом графике не должно быть «тупиков» - событий, из которых не выходит ни одна работа (за исключением завершающего события).

2. В сетевом графике не должно быть событий, кроме исходного, которым не предшествует хотя бы одного события.

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

4. В сетевом графике не должно быть замкнутых циклов.

Покажем на примере подготовки тестирования школьников, как строится сетевой график. На первом этапе перечисляются все работы, входящие в комплекс и записываются в порядке их следования. Затем определяются начальные работы, которые могут выполняться параллельно, для остальных работ определяется, после каких работ они должны выполняться, и определяется время выполнения каждой работы. Все это заносится в таблицу. Затем рисуется сетевой график, нумеруются события в порядке их следования и каждой работе присваивается код (i,j), где i– номер начального для работы события, j-номер конечного события.

Результаты представлены в таблице:

№	Название работы	Опирается на работы	Продолжительность работы	Код работы
1.	Подготовка оборудования для обработки тестов.	-	5	1-2
2.	Подбор экзаменационной комиссии	-	2	1-4
3.	Проведение семинаров для членов экзаменационной комиссии	2,5	3	4-7
4.	Подготовка вариантов экзаменационных тестов	-	10	1-3
5.	Подготовка документации для проверки работ	4	3	3-4
6.	Проведение экзамена.	4	1	3-6
7.	Монтаж оборудования	1	3	2-5
8.	Обучение технического персонала.	7	2	5-6
9.	Обработка входных документов	6,8	2	6-7
10.	Проверка экзаменационных работ	3,9	3	7-8
11.	Обработка результатов.	10	2	8-9

Сетевой график представлен на рис 11[2].

2.12. Прикладные задачи, решаемые с помощью графов

2.12.1. Графы и информация

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

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

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

2.12.2. Графы и химия

Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой: CnH2n+2.

Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны.

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

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

2.12.3. Графы и биология

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

Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

2.12.4. Графы и физика

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

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

В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках[4].

2.12.5. Графы и экономика

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

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

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

Рассмотрим пример.

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

Интересно, что алгоритм нахождения оптимального варианта строительства довольно прост (чего нельзя сказать о других задачах теории графов).

Продемонстрируем его на примере дороги, соединяющей пять городов: A, B, C, D и E. Стоимость прокладки пути между каждой парой городов указана в таблице.

Сначала строим ту дорогу, которая имеет наименьшую стоимость. В нашем случае это маршрут В – Е. теперь найдем самую дешевую линию, соединяющую город В или Е с каким то из остальных городов. Это путь между Е и С. Включаем его в схему. Далее поступаем аналогично – ищем самый дешевый из путей, соединяющих один из городов В, С, Е с одним из оставшихся – А или D. Дешевле всего соединить его с С. Получим сеть, изображенную на рисунке.

Описанный алгоритм относится к категории «жадных»: на каждом шаге мы выбираем самое дешевое продолжение пути [5].

3. Задачи, решаемые с помощью графов

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

1) Один из ребят сказал: «А у нас в классе 25 человек, и каждый дружит ровно с семью одноклассниками!». «Не может быть этого», - ответила приятелю Маша. Почему она так ответила?

Решение: Представим всех ребят в классе в виде вершин графа. Получим 25 вершин. Соединим вершины, обозначающие друзей, ребрами. Тогда из каждой вершины будет выходить по семь ребер. Сумма степеней вершин графа будет равна 25x7=175. Это нечетное число. А нам известно, что сумма степеней вершин графа должна быть четна. Получили противоречие.

2) В городе N 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение: Представим все телефоны в виде вершин графа. Получим 15 вершин. Соединим вершины, обозначающие соединенные телефоны, ребрами. Тогда из каждой вершины будет выходить по пять ребер. Сумма степеней вершин графа будет равна 15x5=75. Это нечетное число. А нам известно, что сумма степеней вершин графа должна быть четна. Получили противоречие.

3) Между тремя одноклассниками – Юрой, Колей и Мишей распределятся роли Салтана, Гвидона и Черномора. Известно, что на роль Салтана претендует 1 мальчик, а Черномора хотят играть трое. Юра пробовался только на 1 роль, Коля готов играть всех трех персонажей, а Миша пробовался на 2. Кто из мальчиков какую роль в школьном спектакле будет играть?

Решение: Для решения задачи применим графы.

Салтан Юра

Гвидон Коля

 

Черномор Миша

Так как к Салтану идет лишь одна стрелка, то Коля будет играть Салтана. Тогда Коля не будет Черномором, а значит, Черномором будет Юра, который пробовался только на эту роль, тогда Миша будет играть Гвидона.

4) Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств: 1. учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок; 2. учитель литературы может дать либо второй, либо третий урок; 3. математик готов дать либо только первый, либо только второй урок; 4. преподаватель физкультуры согласен дать только последний урок. Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы?

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

1. 1) история

2) математика

3) литература

4) физкультура

2. 1) математика

2) история

3) литература

4) физкультура

3. 1) математика

2) литература

3) история

4) физкультура

4) В составе экспедиции должно быть 6 специалистов: биолог, врач, синоптик, гидролог, механик и радист. Имеется 8 кандидатов, из которых и нужно выбрать участников экспедиции; условные имена претендентов: A, B, C, D, E, F, G и H. Обязанности биолога могут исполнять E и G, врача - A и D, синоптика - F и G, гидролога - B и F, радиста - С и D, механика - C и H. Предусмотрено, что в экспедиции каждый из них будет выполнять только одну обязанность. Кого и в какой должности следует включить в состав экспедицию, если F не может ехать без B, D - без H и C, C не может ехать вместе с G, A - вместе с B?

Решение: для решения этой задачи построим граф.

C не может ехать вместе с G, A - вместе с B. Значит должен поехать кто-то один из каждой пары, но т. к. F не может ехать без B, то А не едет. Значит врачом будет D, а должность радиста займет C. C не может ехать вместе с G, значит G не едет. Механиком будет H. G не едет, следовательно биологом будет E, а синоптиком – F. Должность гидролога займет B.

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

Решение: Построим граф, вершины которого обозначают ученых. Ребра одинакового цвета, обозначают ученых, говорящих на одном языке. Если они говорят на английском, то они соединены черным ребром, если на немецком – красным, а если на русском – синим. Докажем, что в графе есть треугольник, составленный из одноцветных ребер. Рассмотрим произвольную вершину графа. Из вершины должно выходить минимум 6 ребер одного цвета, т. к. степень вершины этого графа равна 16. Пусть для определенности из вершины 1 выходит 6 черных ребер. Если какая-либо пара вершин, соединенных с вершиной 1 также соединена черным ребром, то мы нашли искомый треугольник. Если же они все соединены красными или синими ребрами, то в графе обязательно найдется красный или синий треугольник.

Библиографический список

1. «Избранные лекции по дискретной математике. Часть I. Комбинаторика и графы», Саранск: Изд-во Мордов. ун-та, 2003.

2. О. Оре «Графы и их применение», Москва: Издательство «Мир», 1965.

3. «Занимательные задачи по теории графов», Мн.: «ТетраСистемс»,2001.

4. Интернет ресурс: http://tarefer.ru/works/50/100251/index.html

5. , «Основные понятия теории графов». Елец: ЕГУ им. , 2008.