Введение | 5
|
Условное разделение задач по степеням сложности | 7
|
Задачи. Решения задач | 8
|
1. Определение графа | 8
|
2. Полные графы | 12
|
3. Смежность | 18
|
4. Связность графов | 31
|
5. Лемма о рукопожатиях | 40
|
6. Маршруты, цепи, циклы | 48
|
7. Двудольные графы | 53
|
8. Поиск в ширину | 64
|
9. Многодольные графы | 67
|
10. Деревья | 70
|
11. Эйлеровы графы | 99
|
12. Гамильтоновы графы | 111
|
13. Плоские и планарные графы | 115
|
14. Вершинная и реберная связность | 130
|
15. Двойственные графы | 140
|
16. Раскраска графов | 143
|
17. Независимость и покрытия | 157
|
18. Паросочетания | 163
|
19. Графические последовательности | 178
|
20. Ориентированные графы | 184
|
21. Гиперграфы | 225
|
Использованная литература | 234
|
Дополнительная литература | 235
|
Предметный указатель | 236
|
Современная математика уже не такая, какой она была в начале
XX века. В ней появилось большое количество новых дисциплин, широко
применяющихся на практике. Например, дисциплины, объединенные под общим
названием "Дискретная математика". Математическая энциклопедия говорит
о дискретной математике как о ряде математических теорий, не связанных
непосредственно с концепцией предельного перехода и непрерывности. Дискретная
математика является в настоящее время очень интенсивно развивающимся разделом
математики. Это связано с повсеместным распространением кибернетических систем,
языком описания которых она является. Кроме того, дискретная математика
является теоретической базой информатики, которая все глубже и глубже проникает
не только в науку и технику, но и в повседневную жизнь.
Среди дисциплин дискретной математики видное место занимает
теория графов. Родившись при решении головоломок, теория графов стала
в настоящее время простым, доступным и мощным средством решения как
теоретических, так и производственных задач.
Одной из целей предлагаемой книги является знакомство учеников с элементами
теории графов. В ней можно найти большое количество различных сведений
из теории. Автор хотел бы, чтобы представленный задачник можно было назвать
"Теорией графов для школьников". С помощью книги можно начинать
знакомиться с теорией графов уже с пятого класса. Основные понятия
иллюстрируются примерами, а доказательства теорем сознательно встроены
в решения занимательных задач. Среди теорем встречаются достаточно глубокие.
С этой точки зрения книга будет полезна и студентам.
Дискретная математика представлена в школьных программах незначительно. Это
приводит к нарушению преемственности между средним и высшим образованием.
Выпускники школ приходят в вузы плохо подготовленными к восприятию дискретных
математических дисциплин, поэтому у них возникают затруднения при обучении,
особенно на младших курсах. Одной из целей книги является развитие
у учащихся мышления, направленного на решение дискретных математических задач.
Кроме того, для подготовки специалистов высокого класса в вузах постепенно
начинают обучать студентов методологии перехода от реальных производственных
ситуаций к математическим моделям, их описывающим, и дальнейшему
исследованию построенных моделей с помощью вычислительной техники. Автор
считает, что начинать учить строить простейшие математические модели следует
уже в младших классах. Теория графов предоставляет благодатную почву для
этого. В виде графов можно изображать, например, схемы дорог и электрические
цепи, географические карты и химические молекулы, отношения между разными
объектами и людьми и т.д. Именно это привело к широкому использованию
теории графов в физике и кибернетике, химии и биологии, экономике
и социологии и других науках. Особенно велика роль теории графов в современном
программировании. Примеры перехода от различных ситуаций к графовым моделям
представлены в книге.
И, наконец, графовые задачи -- частые гости на математических олимпиадах
всех уровней. Книга может помочь при подготовке к ним, а также при чтении
факультативных курсов по математике и информатике в школе.
В книге представлены более 250 занимательных задач разной трудности и их
решения. Большинство задач придумано или интерпретировано автором. Некоторые
задачи (например, три дома и три колодца, обход мостов, задача
о рукопожатиях и т.д.) относятся к математическому фольклору. Есть в сборнике
и задачи, заимствованные автором из различных источников. Некоторых из них
имеют новые решения.
Для решения задач достаточно знаний по математике в объеме неполной средней
школы. Лишь несколько задач решаются с помощью математической индукции. Знак
|X| всюду обозначает число элементов в множестве X. Часто вводимые понятия
используются при решении нескольких задач. Поэтому в конце книги помещен
указатель, где для каждого определения указана задача, в которой это понятие
вводится.
Изучение элементов теории графов, по мнению автора,
повысит общую
математическую культуру школьников, облегчит
освоение ими вычислительной
техники и подготовит к обучению в вузе.
* * *
Автор благодарит П.В.Скумса за помощь в работе над рукописью.
Мельников Олег Исидорович
Профессор механико-математического факультета Белорусского государственного университета, доктор педагогических наук, кандидат физико-математических наук. Научные интересы: теория графов, обучение дискретной математике в высшей и средней школе. Лауреат Государственной премии Республики Беларусь.