Читать онлайн «Экстремальные задачи в дискретной математике. Метод раскраски»

Министерство образования и науки РФ ФГБОУ ВПО «Удмуртский государственный университет» Математический факультет В. Н. Баранов, О. В. Баранова Экстремальные задачи в дискретной математике Метод раскраски Учебное пособие Ижевск 2015 УДК 512. 8 ББК 22. 11 Б24 Рекомендовано к изданию Учебно-методическим Советом УдГУ Рецензенты: зав. кафедрой математики и информатики, к. ф. -м. н. , доцент В. И. Родионов председатель методической комиссии МФ, к. п. н. , доцент Н. А. Баранова Баранов В. Н. , Баранова О. В. Б24 Экстремальные задачи в дискретной математике. Метод раскраски: учебное пособие. – Ижевск: Изд-во «Удмуртский университет». – 2015, 56 с. ISBN 978-5-4312-0350-3 Учебное пособие посвящено экстремальным задачам в дискрет- ной математике. Пособие адресовано студентам бакалавриата, обу- чащющимся по направлениям «Прикладная математика и инфор- матика», «Математика и компьютерные науки», изучающим курс дискретной математики. В пособии содержится большое количе- ство заданий для самостоятельной работы. Материал пособия мо- жет быть использован студентами старших курсов и магистрами естественно-научных направлений при работе над курсовыми и вы- пускными квалификационными проектами. УДК 512. 8 ББК 22. 11 ISBN 978-5-4312-0350-3 ○ c В. Н. Баранов, О. В. Баранова, 2015 ○ c ФГБОУ ВПО «Удмуртский государственный университет», 2015 Оглавление Предисловие 3 1 Шахматная раскраска 5 2 Раскраки с заданным условием 25 3 Различные раскраски 35 Литература 54 Предисловие Учебное пособие посвящено экстремальным задачам в дискретной математике, которые традиционно излагают- ся в курсе дискретной геометрии. Клетчатая бумага (множество точек плоскости с цело- численными координатами) является своеобразным мно- жеством, которое дает возможность при решении чисто геометрических задач воспользоваться методами алгеб- ры, теории чисел и математического анализа, и наоборот, задачи аналитического характера позволяет переводить на геометрический язык. Умение решать задачи на клет- чатой бумаге необходимо как для будущих математиков, так и для специалистов в области информатики. Основной упор в пособии сделан на метод раскрас- ки, который часто возникает при исследовании задач, связанных с инвариантами. Эти задачи крайне важны для развития логического мышления у будущих специ- алистов. Такие задачи возникают в различных областях мате- матики, в компьютерных науках, в электронике, в дру- гих дисциплинах (в том числе в экономике). При этом практически отсутствует систематизированное изложе- ние изучаемых вопросов. Задачи о раскрашивании различных математических объектов появились сравнительно недавно, во второй по- 3 4 Оглавление ловине XVIII века (знаменитая проблема четырех красок была сформулирована в 1878г. ).