Если вы любите решать задачи на смекалку, логические, олимпиадного типа или головоломки, то, наверное, не раз составляли таблицы, изображали объекты точками, соединяли их отрезками или стрелками, подмечали закономерности у полученных рисунков, выполняли над точками и отрезками операции, не похожие на арифметические, алгебраические или на преобразования в геометрии, то есть вам приходилось строить математический аппарат специально, для решения задачи. А это означает, что вы заново открывая" для себя начала теории графов. Исторически сложилось так, что теория графов зародилась именно в ходе решения головоломок двести с лишним лет назад. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания. Толчок к развитию теория графов получила на рубеже XIX и XX вв., когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнига в 30-е гг. XX в. В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ля не всю современную математику. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Широкое применение находят графы в таких областях прикладной математики, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей. Конечно, в небольшой книге невозможно рассказать о всех направлениях развития теории графов и разработанных приложениях. Главная цель автора в другом – помочь школьникам и учителям овладеть основными понятиями теории графов, новыми для школы методами решения задач, в популярной форме познакомить с некоторыми ее приложениями. Материал книги Сорганизован так, что знакомство с графами происходит в процессе решения самых разнообразных задач, в формулировках условий которых не упоминаются графы. Для решения их требуется "увидеть" возможность перевести условие на язык графов, решить задачу "внутри теории графов", интерпретировать полученное решение в исходных терминах. Возможность представить граф с помощью наглядных рисунков делает все это более доступным. Вначале приводятся задачи, которые можно решать с помощью неориентированных графов (с одноцветными вершинами и ребрами), потом появляются задачи, для решения которых требуется ввести цветные ребра, и наконец задачи, для решения которых полезны ориентированные графы. Таким образом, расширение понятия "граф" происходит как бы по необходимости, с целью решения очередной задачи. При чтении книги обратите внимание на то, что сначала граф появляется как рисунок из точек и отрезков, соединяющих пары точек. Шаг за шагом выявляются закономерности необычной "геометрии", в которой нет углов, нет расстояния между точками в привычном понимании этого слова, равноправны расположения точек на рисунке, безразлично, соединены ли две точки отрезком прямой или отрезком кривой, и т. д. Постепенно содержание понятия "граф" уточняется, а объем его расширяется. Определение графа появляется лишь в пятой главе книги. Если в начале книги рассматриваются приложения частного характера, иллюстрирующие теорию графов и ее связь с жизнью, то вторая половина книги посвящена прикладным разделам теории графов, имеющим практическое значение в экономике и управлении. Конечно, при чтении придется потрудиться, поработать с карандашом и бумагой. Но ведь иначе и быть не может. Это математическая книга, и она требует такой работы. Многое сделано, чтобы облегчить чтение, – материал в каждой главе излагается последовательно от простого к более сложному, от легкого к более трудному. После каждого нового материала приведено большое число упражнений. Для чтения книги не требуется каких-либо специальных предварительных знаний. Большинство ее разделов можно рекомендовать уже девятиклассникам; она содержит много материала, интересного для обучающихся в X–XI классах. Книга предназначена для индивидуального чтения любителям математики, но может быть использована и как элективный учебный курс по выбору обучающихся старших классов. Книга призвана направить их познавательные интересы в сферу дискретной математики, достаточно быстро развивающейся и находящей все более широкое применение. Для тех, кто пожелает более основательно познакомиться с теорией графов и ее приложениями, в конце книги приведен список литературы. Главы VI, VII, VIII независимы друг от друга; поэтому их можно читать в любом порядке. Все задачи, рисунки, теоремы и упражнения имеют двойную нумерацию: первое число обозначает номер главы, а второе – их порядковый номер в главе. Автор выражает искреннюю признательность за полезные советы по структуре и содержанию книги и постоянную поддержку во время работы над ней В. Н. Березину – моему мужу и другу по жизни, а также другу нашей семьи, одному из первых читателей первого издания нашей книги, тогда еще школьнику, а ныне доктору физико-математических наук Б. И. Яцало, благодарность редакции журнала "Квант", в свое время познакомившей широкую школьную читательскую аудиторию с отдельными материалами книги. Лариса Юрьевна БЕРЕЗИНА Ведущий научный сотрудник лаборатории содержания и технологий общего образования в системе начального и среднего профессионального образования Центра профессионального образования Федерального института развития образования (ФИРО), кандидат педагогических наук, доцент. В 1964 г. закончила математический факультет МГПИ им. В. И. Ленина. Четыре года работала учителем математики в старших классах московской общеобразовательной школы N 52 с углубленным изучением математики; восемнадцать лет – в лаборатории математического образования НИИ содержания и методов образования Российской академии образования; двадцать лет работает в Институте развития профессионального образования (с 2006 г. – Федеральный институт развития образования). Опубликовала более 100 работ, в том числе: "Графы и их применение" (1979), "Геометрия в 8 классе" (1985; в соавторстве), "Сборник задач для факультативных и внеклассных занятий по математике" (1985), "Сборник задач и упражнений по математике для средних профтехучилищ транспортного профиля" (1985; в соавторстве), "Геометрия в 7-9 классах" (1990; 2008). Автор статей по использованию графов в решении задач в журналах "Математика в школе" и "Квант". |