Введение.
История возникновения и развития теории графов.



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

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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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


Для работы с графами в Maple V предназначена библиотека networks. Команда подключения этой библиотеки стандартная, т.е. достаточно воспользоваться оператором with[].

Граф в Maple представляется особой процедурой типа GRAPH. Для работы с графами можно воспользоваться любой из 75-ти функций, содержащихся в библиотеке networks. Основные функции, которые позволяют создавать и изменять графы, приведены в справочнике учебника.


Учебное пособие можно использовать как учебник для самостоятельного изучения основ теории графов, а также для организации факультативной работы в 9-11 классах.

Предполагается, что пользователь при изучении разделов "Интересные факты", будет пользоваться рекомендованной литературой. Не стоит огорчаться, если какие-то из дополнительных заданий (повышенной сложности) вы не решили. Отложите их решение на будущее.

В простых задачах можете ограничиться лишь построением графов.

Мы желаем вам успехов в изучении теории графов и надеемся, что наш учебник вам в этом поможет!