Березина Л.Ю.

Графы и их применение:
Популярная книга для школьников и преподавателей № 83. Изд. стереотип.

Оглавление

От автора

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

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

Толчок к развитию теория графов получила на рубеже XIX и XX вв., когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнига в 30-е гг. XX в.

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

Конечно, в небольшой книге невозможно рассказать о всех направлениях развития теории графов и разработанных приложениях. Главная цель автора в другом -- помочь школьникам и учителям овладеть основными понятиями теории графов, новыми для школы методами решения задач, в популярной форме познакомить с некоторыми ее приложениями. Материал книги Сорганизован так, что знакомство с графами происходит в процессе решения самых разнообразных задач, в формулировках условий которых не упоминаются графы. Для решения их требуется "увидеть" возможность перевести условие на язык графов, решить задачу "внутри теории графов", интерпретировать полученное решение в исходных терминах. Возможность представить граф с помощью наглядных рисунков делает все это более доступным. Вначале приводятся задачи, которые можно решать с помощью неориентированных графов (с одноцветными вершинами и ребрами), потом появляются задачи, для решения которых требуется ввести цветные ребра, и наконец задачи, для решения которых полезны ориентированные графы. Таким образом, расширение понятия "граф" происходит как бы по необходимости, с целью решения очередной задачи. При чтении книги обратите внимание на то, что сначала граф появляется как рисунок из точек и отрезков, соединяющих пары точек. Шаг за шагом выявляются закономерности необычной "геометрии", в которой нет углов, нет расстояния между точками в привычном понимании этого слова, равноправны расположения точек на рисунке, безразлично, соединены ли две точки отрезком прямой или отрезком кривой, и т. д. Постепенно содержание понятия "граф" уточняется, а объем его расширяется. Определение графа появляется лишь в пятой главе книги.

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

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

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

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

Главы VI, VII, VIII независимы друг от друга; поэтому их можно читать в любом порядке.

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

Автор выражает искреннюю признательность за полезные советы по структуре и содержанию книги и постоянную поддержку во время работы над ней В. Н. Березину -- моему мужу и другу по жизни, а также другу нашей семьи, одному из первых читателей первого издания нашей книги, тогда еще школьнику, а ныне доктору физико-математических наук Б. И. Яцало, благодарность редакции журнала "Квант", в свое время познакомившей широкую школьную читательскую аудиторию с отдельными материалами книги.

Об авторе

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

В 1964 г. закончила математический факультет МГПИ им. В. И. Ленина. Четыре года работала учителем математики в старших классах московской общеобразовательной школы N 52 с углубленным изучением математики; восемнадцать лет -- в лаборатории математического образования НИИ содержания и методов образования Российской академии образования; двадцать лет работает в Институте развития профессионального образования (с 2006 г. -- Федеральный институт развития образования). Опубликовала более 100 работ, в том числе: "Графы и их применение" (1979), "Геометрия в 8 классе" (1985; в соавторстве), "Сборник задач для факультативных и внеклассных занятий по математике" (1985), "Сборник задач и упражнений по математике для средних профтехучилищ транспортного профиля" (1985; в соавторстве), "Геометрия в 7-9 классах" (1990; 2008). Автор статей по использованию графов в решении задач в журналах "Математика в школе" и "Квант".