Мельников О.И.

Теория графов в занимательных задачах: Более 250 задач с подробными решениями Изд. стереотип.

Содержание

Введение

Современная математика уже не такая, какой она была в начале XX века. В ней появилось большое количество новых дисциплин, широко применяющихся на практике. Например, дисциплины, объединенные под общим названием "Дискретная математика". Математическая энциклопедия говорит о дискретной математике как о ряде математических теорий, не связанных непосредственно с концепцией предельного перехода и непрерывности. Дискретная математика является в настоящее время очень интенсивно развивающимся разделом математики. Это связано с повсеместным распространением кибернетических систем, языком описания которых она является. Кроме того, дискретная математика является теоретической базой информатики, которая все глубже и глубже проникает не только в науку и технику, но и в повседневную жизнь.

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

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

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

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

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

В книге представлены более 250 занимательных задач разной трудности и их решения. Большинство задач придумано или интерпретировано автором. Некоторые задачи (например, три дома и три колодца, обход мостов, задача о рукопожатиях и т.д.) относятся к математическому фольклору. Есть в сборнике и задачи, заимствованные автором из различных источников. Некоторых из них имеют новые решения.

Для решения задач достаточно знаний по математике в объеме неполной средней школы. Лишь несколько задач решаются с помощью математической индукции. Знак |X| всюду обозначает число элементов в множестве X. Часто вводимые понятия используются при решении нескольких задач. Поэтому в конце книги помещен указатель, где для каждого определения указана задача, в которой это понятие вводится.

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

* * *

Автор благодарит П.В.Скумса за помощь в работе над рукописью.

Об авторе

Мельников Олег Исидорович

Профессор механико-математического факультета Белорусского государственного университета, доктор педагогических наук, кандидат физико-математических наук. Научные интересы: теория графов, обучение дискретной математике в высшей и средней школе. Лауреат Государственной премии Республики Беларусь.