|
Оглавление
Введение
Современная математика уже не такая, какой она была в начале XX века. В ней появилось большое количество новых дисциплин, широко применяющихся на практике. Например, дисциплины, объединенные под общим названием "Дискретная математика". Математическая энциклопедия говорит о дискретной математике как о ряде математических теорий, не связанных непосредственно с концепцией предельного перехода и непрерывности. Дискретная математика является в настоящее время очень интенсивно развивающимся разделом математики. Это связано с повсеместным распространением кибернетических систем, языком описания которых она является. Кроме того, дискретная математика является теоретической базой информатики, которая все глубже и глубже проникает не только в науку и технику, но и в повседневную жизнь. Среди дисциплин дискретной математики видное место занимает теория графов. Родившись при решении головоломок, теория графов стала в настоящее время простым, доступным и мощным средством решения как теоретических, так и производственных задач. Одной из целей предлагаемой книги является знакомство учеников с элементами теории графов. В ней можно найти большое количество различных сведений из теории. Автор хотел бы, чтобы представленный задачник можно было назвать "Теорией графов для школьников". С помощью книги можно начинать знакомиться с теорией графов уже с пятого класса. Основные понятия иллюстрируются примерами, а доказательства теорем сознательно встроены в решения занимательных задач. Среди теорем встречаются достаточно глубокие. С этой точки зрения книга будет полезна и студентам. Дискретная математика представлена в школьных программах незначительно. Это приводит к нарушению преемственности между средним и высшим образованием. Выпускники школ приходят в вузы плохо подготовленными к восприятию дискретных математических дисциплин, поэтому у них возникают затруднения при обучении, особенно на младших курсах. Одной из целей книги является развитие у учащихся мышления, направленного на решение дискретных математических задач. Кроме того, для подготовки специалистов высокого класса в вузах постепенно начинают обучать студентов методологии перехода от реальных производственных ситуаций к математическим моделям, их описывающим, и дальнейшему исследованию построенных моделей с помощью вычислительной техники. Автор считает, что начинать учить строить простейшие математические модели следует уже в младших классах. Теория графов предоставляет благодатную почву для этого. В виде графов можно изображать, например, схемы дорог и электрические цепи, географические карты и химические молекулы, отношения между разными объектами и людьми и т.д. Именно это привело к широкому использованию теории графов в физике и кибернетике, химии и биологии, экономике и социологии и других науках. Особенно велика роль теории графов в современном программировании. Примеры перехода от различных ситуаций к графовым моделям представлены в книге. И, наконец, графовые задачи -- частые гости на математических олимпиадах всех уровней. Книга может помочь при подготовке к ним, а также при чтении факультативных курсов по математике и информатике в школе. В книге представлены более 250 занимательных задач разной трудности и их решения. Большинство задач придумано или интерпретировано автором. Некоторые задачи (например, три дома и три колодца, обход мостов, задача о рукопожатиях и т.д.) относятся к математическому фольклору. Есть в сборнике и задачи, заимствованные автором из различных источников. Некоторых из них имеют новые решения. Для решения задач достаточно знаний по математике в объеме неполной средней школы. Лишь несколько задач решаются с помощью математической индукции. Знак |X| всюду обозначает число элементов в множестве X. Часто вводимые понятия используются при решении нескольких задач. Поэтому в конце книги помещен указатель, где для каждого определения указана задача, в которой это понятие вводится. Изучение элементов теории графов, по мнению автора, повысит общую математическую культуру школьников, облегчит освоение ими вычислительной техники и подготовит к обучению в вузе. * * * Автор благодарит П.В.Скумса за помощь в работе над рукописью. Об авторе
Олег Исидорович Мельников
Профессор механико-математического факультета Белорусского государственного университета, доктор педагогических наук, кандидат физико-математических наук. Научные интересы: теория графов, обучение дискретной математике в высшей и средней школе. Автор и соавтор книг: "Лекции по теории графов" (М., 1990; 2-е изд. М.: URSS, 2009); "Exercises in graph theory" (Dordrecht, 1998); "Информатика. Методы алгоритмизации" (Минск, 2000); "Занимательные задачи по теории графов" (Минск, 2001); "Математика для экономистов на базе "Mathcad"" (СПб., 2003), "Обучение дискретной математике" (М.: URSS, 2008). Лауреат Государственной премии Республики Беларусь. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||