Обложка Мельников О.И. Теория графов в занимательных задачах: Более 250 задач с подробными решениями
Id: 290244
599 руб.

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

Теория графов в занимательных задачах: Более 250 задач с подробными решениями
URSS. 2022. 240 с. ISBN 978-5-9519-3438-3.
Типографская бумага

Аннотация

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


Содержание
Введение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. Часто вводимые понятия используются при решении нескольких задач. Поэтому в конце книги помещен указатель, где для каждого определения указана задача, в которой это понятие вводится.

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

* * *

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


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