«Теория Графов и ее прикладное значение. Решение задач с помощью теории Графов»

«Теория Графов и ее прикладное значение. Решение задач с помощью теории Графов»

Наш современный мир наполнен не только буквами разных языков и цифрами различных видов, но и изображениями, представленными в многочисленных интерпретациях: всевозможные фотографии, картины всех эпох и стилей, а также такие вещи как схемы. Схемы встречаются на логотипах компаний и автомобилей, картах и дорожных знаках, строительных схемах и учебниках по информатике, в математике им даже посвящен отдельный раздел изучения и так далее. Попробуйте вспомнить карту метро или электричек. Вы представляете набор цветных линий (направлений маршрутов) и точек на пересечении этих линий с подписями (станции метро или вокзалов), не так ли? Так вот это один из простейших и наиболее узнаваемых примеров таких схем как графы. Именно о них пойдет речь в этой работе.

Начать исследование графов, как и любой другой темы во многих предметах – с истории. Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Однако теория графов многократно переоткрывалась разными авторами при решении различных задач.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды. В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера. Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя». Эйлер представил эту часть города в упрощенном виде – графе, где мостам соответствуют линии (ребра графа), а частям города — точки соединения линий (вершины графа).

Рис.1 Задача Эйлера

Азы теории графов

Граф – это множество точек, которые также могут называть вершинами или узлами графа, и множество ребер или же дуг графа, которые попарно соединяют вершины. Если мы назовем или отметим какими-либо знаками вершины графа, то он будет называться помеченным (например, ветки метро с помеченными названиями станций узлами). Графы могут быть ориентированными, если задать показать (чаще всего простой стрелочкой) в ребре от какой вершины к какой идет направление. А если мы подпишем какое-либо значение (веса), то такой граф будет называться взвешенным. А если направление не задано, то граф, соответственно, называется – неориентированным. Если все ребра в графе являются ориентированными, то такой граф можно называть – орграфом. На пример взвешенного ориентированного графа международных торговых отношений. Графы имеют множество представлений. Их можно показать, как в графическом виде, так и таблицей или списком. Вершины графа можно изображать в виде точек, окружностей, треугольников, а ребра прямыми отрезками либо же фигурно изогнутых линий. Существует такое понятие как изоморфные графы. Это такие графы, которые эквивалентны друг другу, но выглядят по-разному.

Рис.2 «Три фигуры – три изоморфных представления одного и того же графа»

Применение графов в строительстве

В строительстве графы используются при планировании проведения работ. Граф, изображенный на чертеже, называется сетевым графиком строительства. В данном случае он составлен для строительства жилого дома. Вершины этого графа обозначают отдельные виды работ на стройке, кроме того, есть еще две вершины: начало строительства и его окончание. Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называется направленным. Стрелка от работы А к работе В на графе, изображенном на чертеже, означает, что работа В не может начаться раньше, чем кончится работа А. Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду, для сварочных работ при монтаже нужно иметь подвод электричества и т. д. Около вершины графа указаны числа – продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на чертеже большая стрелка). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства сократится на 30 дней? Нет. В этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократится лишь на 10 дней.

(Рис.3 Сетевой график строительства)

Применение графов при решении комбинаторных задач

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

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

Вот несколько примеров таких задач с решением:

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

Решение: Найти самый короткий путь можно, проанализировав все варианты. Сделать это можно, построив новый граф, на котором можно увидеть все возможные маршруты.

«Почтамт» начало всех маршрутов.

(Рис.4 Граф возможных маршрутов)

Всего 24 способа прохождения маршрута. Расставив вдоль ребер цифры, обозначающие расстояние между отделений связи, найдем длину каждого маршрута. Из полученных чисел видно, что наименьшее число по 21 км соответствуют маршрутам «Почтамт => Отделение связи №3 => Отделение связи №2 => Отделение связи №1 => Отделение связи №4» и «Почтамт => Отделение связи №4 => Отделение связи №1 => Отделение связи №2 => Отделение связи №3». Заметим, что один и тот же путь, пройден в разных направлениях.

Задача 2. Сколькими способами можно выбрать комиссию из трёх человек: председателя, его заместителя и секретаря? По дереву решений получается ответ – 6

Рис.5 Дерево решений

Заключение

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

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

2. Использование моделирования с помощью графов позволяет решать задачи более рациональными методами.

3. Одним из преимуществ применения графов в решении задач является его наглядность.

Список литературы

Оре О. Теория графов. — М.: Наука, 1968. — 336 с.

Уилсон Р. Введение в теорию графов. — М.: Мир, 1977. — 208 с.

Харари Ф. Теория графов. — М.: Мир, 1973.

Кормен Т. М. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ | Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 1296.

Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997.