2020-04-07
92
МОДУЛЬ 4. ОСНОВЫ ТЕОРИИ ГРАФОВ 299
Глава 15. Введение в теорию графов 300
15.1. Способы задания и виды графов 301
15.1.1. Способы задания графов 301
15.1.2. Виды графов 308
15.1.3. Нечеткие неориентированные графы 313
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 314
КОНТРОЛЬНЫЕ ВОПРОСЫ 319
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 319
15.2. Маршруты, цепи, циклы 321
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 326
КОНТРОЛЬНЫЕ ВОПРОСЫ 328
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 328
15.3. Алгоритмы нахождения кратчайших по стоимости маршрутов (цепей) 330
15.3.1. Алгоритм Форда 330
15.3.2. Алгоритм Дейкстра 333
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 338
КОНТРОЛЬНЫЕ ВОПРОСЫ 342
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 343
Глава 16. Специальные циклы и метрика графов 345
16.1. Эйлеровы и гамильтоновы цепи и циклы 345
16.1.1. Связь между эйлеровыми и гамильтоновыми
графами 349
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 355
КОНТРОЛЬНЫЕ ВОПРОСЫ 356
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 357
16.2. Алгоритмы построения гамильтонова цикла 358
16.2.1. Алгоритм Робертса – Флореса 358
16.2.2. Алгебраический метод 362
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 363
КОНТРОЛЬНЫЕ ВОПРОСЫ 368
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 368
16.3. Задача о коммивояжере и алгоритмы ее решения 370
16.3.1. Алгоритм Хелда и Карпа 370
16.3.2. Геометрический метод решения 370
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 374
КОНТРОЛЬНЫЕ ВОПРОСЫ 377
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 378
16.4. Расстояния на графах 379
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 383
КОНТРОЛЬНЫЕ ВОПРОСЫ 385
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 385
16.5. Деревья 387
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 396
КОНТРОЛЬНЫЕ ВОПРОСЫ 402
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 402
Глава 17. Графовые инварианты 404
17.1. Цикломатическое и хроматическое числа графа 404
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 409
КОНТРОЛЬНЫЕ ВОПРОСЫ 411
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 412
17.2. Числа внутренней и внешней устойчивости графа 413
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 420
КОНТРОЛЬНЫЕ ВОПРОСЫ 423
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 424
17.3. Планарность графов 425
17.3.1. Плоские и планарные графы 425
17.3.2. Эвристики для определения планарности 429
17.3.3. Минимизация пересечений ребер графов 432
КОНТРОЛЬНЫЕ ВОПРОСЫ 439
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 439
17.4. Ориентированные графы 441
17.4.1. Способы задания 441
17.4.2. Решение стандартных графовых задач с использованием орграфов 443
17.4.3. Выделение сильносвязных компонент 444
17.4.4. Нечеткие ориентированные графы 446
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 447
КОНТРОЛЬНЫЕ ВОПРОСЫ 455
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 455
17.5. Гиперграфы 457
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 460
КОНТРОЛЬНЫЕ ВОПРОСЫ 460
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 461
ТЕСТОВЫЕ ЗАДАНИЯ К МОДУЛЮ 4 462
ГЛОССАРИЙ К МОДУЛЮ 4 471
БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ 480
ЛИТЕРАТУРА 484
ЗАКЛЮЧЕНИЕ 489
ПРИЛОЖЕНИЕ 1. 491
Хорошее начало – половина всего.
Платон
В одном мгновеньи – видеть вечность,
Огромный мир – в зерне песка,
В единой горсти – бесконечность,
И небо в чашечке цветка.
У.Блейк
ВВЕДЕНИЕ
Данный учебник является частью курса “Дискретная математика”, который проводился в Таганрогском государственном радиотехническом университете в течении 20 лет (1986 – 2006). В настоящее время данный курс ставится и читается на основе инновационных, информационных и интеллектуальных технологий обучения в Южном федеральном университете (г. Ростов-на-Дону, г. Таганрог). В пособии рассматриваются основные положения теории множеств, теории алгоритмов и алгебры логики, теории графов, а также их применение для решения практических задач науки и техники. Для лучшего усвоения материала была использована инновационная методика обучения на основе “решебников”. В начале каждого модуля приводится краткое изложение теории, затем подробно рассматриваются примеры и задачи с решениями. Также приводятся контрольные задачи, упражнения и глоссарий с пояснением основных терминов. Задачи и упражнения составлены авторами на основе фундаментальных научных исследований в этой области, а также современной учебной литературы. Опыт преподавания в вузах России, США, Германии, Франции и Японии показал эффективность такого метода представления материала.
Теория множеств является базой, на основе которой строится вся современная дискретная математика. Основное влияние дискретная математика оказала на развитие вычислительной техники, микроэлектроники, нанотехнологии, биологии, генетики, информатики и других наук. В настоящее время применение теории множеств является повсеместным во всех областях науки и техники, поэтому дискретная математика и ее основная часть - теория множеств являются не только фундаментом современной математики, но и основным звеном подготовки специалистов XXI века.
Учебник состоит из четырех модулей. В первом модуле учебника авторы рассмотрели вопросы: исчисления множеств выполнения основных операций над множествами, представления упорядоченных множеств, задания отношений и соответствий, описания упорядоченных бесконечных множеств, мультимножеств и нечетких множеств. Теоретический материал модуля 1 состоит из большого числа моделей, аксиом, теорем и формулировок, используемых в пособии понятий. Каждое новое понятие и положение выделяется жирным шрифтом и включается в глоссарий, где дается его пояснение. Авторы стремились показать широкие возможности применения теории множеств, ее универсальность и специализированность для решения задач информатики и вычислительной техники. Методы теории множеств используются в таких разделах дискретной математики, как комбинаторика, алгебра логики, теория алгортимов, теория графов, теория автоматов, математическое программирование. Положения теории множеств являются основой курсов «Математическая логика и теория алгоритмов», «Базы данных и СУБД», «Исследование операций», «Методы оптимизации» и др. Студент, обладающий знаниями в области теории множеств, будет подготовлен к эффективной деятельности в науке, бизнесе и производстве.
Во втором и третьем модулях учебника рассматриваются основные положения теории алгоритмов и алгебры логики, а также их применение для решения практических задач. Авторы рассмотрели следующие вопросы: основные алгоритмические модели, свойства и классификация алгоритмов, виды универсальных алгоритмов, проблемы временной сложности алгоритмов, классы алгоритмов в зависимости от временной сложности, основные логические функции и законы алгебры логики, нормальные и совершенно нормальные формы представления булевых функций, проблемы функциональной полноты, проблемы минимизации булевых функций, логические схемы, проблемы представления булевых функций в виде логических элементов.
Основы теории алгоритмов и алгеброы логики используются в таких разделах дискретной математики, как комбинаторика, теория графов, теория автоматов, математическое программирование и др. Положения теории алгоритмов являются основой курсов «Исследование операций», «Методы оптимизации», «Теория принятия решений», «Теория игр и комбинаторика» и др.
В четвертом модуле учебника рассматриваются основные положения теории графов, способы задания графов, основные числа графов, Эйлеровы и Гамильтоновы графы, алгоритмы определения кратчайших путей в графе, а также их применение для решения практических задач информатики и вычислительной техники. Авторы стремились показать широкие возможности применения теории алгоритмов и алгебры логики, их универсальность и специализированность для решения задач науки и техники.
Теория графов является базой, на основе которой строится вся современная дискретная математика. Основное влияние теория графов оказала на развитие вычислительной техники, микроэлектроники, нанотехнологии, биологии, генетики, информатики и других наук. В настоящее время применение теории графов является повсеместным во всех областях науки и техники. Дискретная математика и ее основная часть − теория графов − являются не только фундаментом современной математики, но и основным звеном подготовки специалистов XXI века.
Авторы стремились показать широкие возможности применения теории графов, ее универсальность и специализированность для решения задач информатики и вычислительной техники. Методы теории графов используются в таких разделах дискретной математики, как комбинаторика, алгебра логики, теория алгортимов, теория автоматов, математическое программирование. Положения теории графов являются основой курсов «Математическая логика и теория алгоритмов», «Базы данных и СУБД», «Исследование операций», «Методы оптимизации» и др. Студент, обладающий знаниями в области теории графов, будет подготовлен к эффективной деятельности в науке, бизнесе и производстве.
Вместе с теорией множеств, математическая логика и теория алгоритмов образуют теоретический фундамент современных вычислительных наук. Причем в этом случае математическая логика трактуется в широком смысле, включающем в себя и собственно математическую логику, понимаемую как теория формализованных языков, и теорию алгоритмов.
Основная задача учебника – обучение студентов построению моделей множеств, методам доказательств различных тождеств с множествами и, самое главное, методам абстрактного мышления. Студенты должны владеть методами минимизации булевых функций и уметь строить основные схемы алгоритмов решения различных задач науки и техники. Студенты также должны знать способы задания графов, построения графовых моделей, выполнения операций на графах, методы определения кратчайших путей, цепей и циклов в графах, определения Эйлеровых и Гамильтоновых циклов на графах, определения таких инвариантных чисел на графах, как цикломатическое и хроматическое число, число внутренней и внешней устойчивости, построения деревьев и основные алгоритмы на графах.
Для успешного изучения курса «Дискретная математика» студентам необходимо знание информатики, высшей математики и основ программирования. Студент, обладающий знаниями в области дискретной математики, будет подготовлен к эффективной деятельности в науке, бизнесе и производстве.
Авторы благодарны рецензентам - коллективу кафедры прикладной математики Московского энергетического института (зав. кафедрой, д.т.н., профессор, лауреат премии президента РФ в области образования А.П. Еремеев) и Ю.О. Чернышеву, д.т.н., профессору, заслуженному деятелю науки РФ, зав. каф. прикладной математики и вычислительной техники Ростовской государственной академии сельскохозяйственного машиностроения. Авторы благодарны д.т.н., профессору Петровскому А.Б., к.т.н., доценту Полякову В.И. за ценные замечания по 1, 3 и 4 модулям данного учебника. Особая благодарность сотрудникам, аспирантам и студентам кафедры САПР за помощь в апробировании материала.
Любые замечания и предложения будут приняты с благодарностью.
Авторы
