Числа внутренней и внешней устойчивости графа 413

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                420

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    423

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 424

Планарность графов                                                       425

17.3.1. Плоские и планарные графы                              425

17.3.2. Эвристики для определения планарности         429

17.3.3. Минимизация пересечений ребер графов          432

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    439

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 439

Ориентированные графы                                                441

17.4.1. Способы задания                                                441

17.4.2. Решение стандартных графовых задач с использованием орграфов                                                                                                                 443

17.4.3. Выделение сильносвязных компонент               444

17.4.4. Нечеткие ориентированные графы                    446

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                447

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    455

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 455

Гиперграфы                                                                       457

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                460

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    460

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 461

ТЕСТОВЫЕ ЗАДАНИЯ К МОДУЛЮ 4                                     462

ГЛОССАРИЙ К МОДУЛЮ 4                                             471

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ             480

ЛИТЕРАТУРА                                                                        484

ЗАКЛЮЧЕНИЕ                                                                      489

ПРИЛОЖЕНИЕ 1.                                                                 491

Хорошее начало – половина всего.

Платон

 

В одном мгновеньи – видеть вечность,

Огромный мир – в зерне песка,

В единой горсти – бесконечность,

И небо в чашечке цветка.

У.Блейк

 

ВВЕДЕНИЕ

Данный учебник является частью курса “Дискретная математика”, который проводился в Таганрогском государственном радиотехническом университете в течении 20 лет (1986 – 2006). В настоящее время данный курс ставится и читается на основе инновационных, информационных и интеллектуальных технологий обучения в Южном федеральном университете (г. Ростов-на-Дону, г. Таганрог). В пособии рассматриваются основные положения теории множеств, теории алгоритмов и алгебры логики, теории графов, а также их применение для решения практических задач науки и техники. Для лучшего усвоения материала была использована инновационная методика обучения на основе “решебников”. В начале каждого модуля приводится краткое изложение теории, затем подробно рассматриваются примеры и задачи с решениями. Также приводятся контрольные задачи, упражнения и глоссарий с пояснением основных терминов. Задачи и упражнения составлены авторами на основе фундаментальных научных исследований в этой области, а также современной учебной литературы. Опыт преподавания в вузах России, США, Германии, Франции и Японии показал эффективность такого метода представления материала.

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

Учебник состоит из четырех модулей. В первом модуле учебника авторы рассмотрели вопросы: исчисления множеств выполнения основных операций над множествами, представления упорядоченных множеств, задания отношений и соответствий, описания упорядоченных бесконечных множеств, мультимножеств и нечетких множеств. Теоретический материал модуля 1 состоит из большого числа моделей, аксиом, теорем и формулировок, используемых в пособии понятий. Каждое новое понятие и положение выделяется жирным шрифтом и включается в глоссарий, где дается его пояснение. Авторы стремились показать широкие возможности применения теории множеств, ее универсальность и специализированность для решения задач информатики и вычислительной техники. Методы теории множеств используются в таких разделах дискретной математики, как комбинаторика, алгебра логики, теория алгортимов, теория графов, теория автоматов, математическое программирование. Положения теории множеств являются основой курсов «Математическая логика и теория алгоритмов», «Базы данных и СУБД», «Исследование операций», «Методы оптимизации» и др. Студент, обладающий знаниями в области теории множеств, будет подготовлен к эффективной деятельности в науке, бизнесе и производстве.

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

Основы теории алгоритмов и алгеброы логики используются в таких разделах дискретной математики, как комбинаторика, теория графов, теория автоматов, математическое программирование и др. Положения теории алгоритмов являются основой курсов «Исследование операций», «Методы оптимизации», «Теория принятия решений», «Теория игр и комбинаторика» и др.

В четвертом модуле учебника рассматриваются основные положения теории графов, способы задания графов, основные числа графов, Эйлеровы и Гамильтоновы графы, алгоритмы определения кратчайших путей в графе, а также их применение для решения практических задач информатики и вычислительной техники. Авторы стремились показать широкие возможности применения теории алгоритмов и алгебры логики, их универсальность и специализированность для решения задач науки и техники.

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

Авторы стремились показать широкие возможности применения теории графов, ее универсальность и специализированность для решения задач информатики и вычислительной техники. Методы теории графов используются в таких разделах дискретной математики, как комбинаторика, алгебра логики, теория алгортимов, теория автоматов, математическое программирование. Положения теории графов являются основой курсов «Математическая логика и теория алгоритмов», «Базы данных и СУБД», «Исследование операций», «Методы оптимизации» и др. Студент, обладающий знаниями в области теории графов, будет подготовлен к эффективной деятельности в науке, бизнесе и производстве.

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

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

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

Авторы благодарны рецензентам - коллективу кафедры прикладной математики Московского энергетического института (зав. кафедрой, д.т.н., профессор, лауреат премии президента РФ в области образования А.П. Еремеев) и Ю.О. Чернышеву, д.т.н., профессору, заслуженному деятелю науки РФ, зав. каф. прикладной математики и вычислительной техники Ростовской государственной академии сельскохозяйственного машиностроения. Авторы благодарны д.т.н., профессору Петровскому А.Б., к.т.н., доценту Полякову В.И. за ценные замечания по 1, 3 и 4 модулям данного учебника. Особая благодарность сотрудникам, аспирантам и студентам кафедры САПР за помощь в апробировании материала.

Любые замечания и предложения будут приняты с благодарностью.

Авторы