Предлагаемая книга посвящена изложению в занимательной форме элементов одного из важных разделов дискретной математики - теории графов. За последние десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это связано с тем, что теория графов, родившаяся при решении головоломок и занимательных задач, стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. В виде графов можно интерпретировать, например, схемы дорог и электронные схемы, географические карты и молекулы химических соединений, связи между людьми и многое другое. Это привело к широкому использованию теории графов в физике и кибернетике, химии и биологии, экономике и статистике и других науках. Особенна важна роль теории графов в современном программировании.
В книге предлагается более ста занимательных задач и их решение. В начале книги задано условное деление задач по степеням трудности. Большинство из этих задач придумано или интерпретировано автором. Некоторые задачи (например, три дома и три колодца, обход мостов, задача о рукопожатиях и т.д.) относятся к математическому фольклору. Есть в сборнике задачи, заимствованные автором из различных книг. Для некоторых из них предложены новые решения.
Автор сознательно выделяет фрагменты решения некоторых задач в виде теорем. Цель этого, во-первых, в использовании этих теорем при решении последующих задач, во-вторых, в желании развития у школьников абстрактного мышления.
Для решения задач достаточно знаний по математике в объеме неполной средней школы. Лишь несколько задач автор решил с помощью математической индукции. Знак \Х\ всюду обозначает число элементов в множестве X. Часто вводимые понятия используются при решении нескольких задач. Поэтому в конце книги помещен словарь, в котором для каждого определения указана страница, на которой это определение вводится.
Изучение элементов теории графов, по мнению автора, повысит общую математическую культуру школьников и облегчит им освоение вычислительной техники.
Кроме того, книга будет полезна учителям математики для использования на кружках, факультативах и олимпиадах.
4
