Макаровских Т.А. Комбинаторика и теория графов Изд. стереотип.

Оглавление

Введение

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

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

Многие задачи экономики и математического моделирования также непосредственно связаны с дискретной математикой. Например, к числу этих задач относятся задачи оптимизации: задача о назначениях, задача о максимальном потоке, сетевое планирование и многие другие.

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

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

Учебное пособие основано на лекционном курсе "Комбинаторика и теория графов", который автор читает студентам специальностей "Прикладная информатика в экономике" и "Математические методы в экономике" Южно-Уральского государственного университета. Одна из главных задач этого курса – обучение студентов методам мышления, характерным для дискретной математики, основным понятиям комбинаторики и теории графов. Поскольку обе указанные специальности предполагают умение эффективно решать задачи с помощью компьютера, также была поставлена цель развить у студентов навыки алгоритмического мышления на примерах решения задач из разных разделов дискретной математики.

Пособие охватывает следующие разделы дискретной математики: основы теории множеств, комбинаторику и теорию графов. Из основных разделов отсутствуют общая алгебра, теория алгоритмов, арифметика, математическая логика. Это объясняется тем, что данные разделы студенты изучают в рамках других курсов. Пособие ориентировано на семестровый лекционный курс. Книга также может составить основу разделов курсов, примыкающих к дискретной математике (информатика, алгоритмизация и пр.).

Учебное пособие состоит из 17 глав.

Первая глава содержит материал из элементарной теории множеств, необходимый для чтения последующих глав.

Во второй главе кратко изложен метод математической индукции, который является одним из основных методов доказательства в дискретной математике.

В главах 3 – 7 рассмотрены основные принципы комбинаторики, алгоритмы формирования выборок, размещений и сочетаний. Отдельное внимание уделено технике доказательства комбинаторных тождеств.

В этих (а также некоторых других) главах существенно использованы материалы книги [8].

Главы 8 – 9 посвящены введению в теорию графов, приведены основные понятия теории графов и рассмотрены принципы представления графов на компьютере.

В главе 10 приведены определения деревьев и приведены прикладные задачи, математической моделью которых является дерево. Рассмотрен частный случай – бинарные деревья, и их применение на практике. Описаны основные способы обхода бинарных деревьев. Проанализирована одна из классических задач теории графов – построение минимального остова. Для решения этой задачи приведено два алгоритма.

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

В главе 12 рассмотрены двудольные графы и их применение при решении практических задач: поиск максимального паросочетания, решение задачи о назначениях.

Глава 13 знакомит с укладкой графов на плоскости. Приведены критерии планарности графа, а также алгоритм построения плоской укладки, если таковая существует.

Главы 14 – 16 посвящены решению прикладных задач, в которых необходимо применить объекты теории графов: поиск кратчайшего пути, решение задач сетевого планирования и задачи о максимальном потоке.

В 17 главе рассмотрены вопросы раскраски графов и приведены точный и приближенные алгоритмы решения этой задачи.

В конце каждой главы приведены задачи различного уровня сложности, в том числе и связанные с разработкой алгоритмов и программ.

Автор благодарит профессора Уфимского государственного авиационного технического университета Бронштейна Ефима Михайловича и доцента Южно-Уральского государственного университета Эвнина Александра Юрьевича за критические замечания и предложения.

Об авторе

Макаровских Татьяна Анатольевна

Доктор физико-математических наук, доцент, профессор кафедры «Системное программирование» Южно-Уральского государственного университета. В 2003 г. с отличием окончила ЮУрГУ по специальности «Прикладная математика». В 2006 г. защитила кандидатскую диссертацию по специальности «Теоретические основы информатики» в Вычислительном центре имени А. А. Дородницына РАН. В 2020 г. защитила докторскую диссертацию по той же специальности в ЮУрГУ. Является автором более 100 научных публикаций, 7 учебных пособий, монографии «Маршруты-покрытия специального вида в графах: Теоретические основы и применение в ресурсосберегающих технологиях» (М.: URSS), а также более 10 зарегистрированных программ для ЭВМ.