Вторая редакция от 17 ноября 2022 г.Вторая редакция книги дополнена двумя главами:
Глава 29 — поиск паросочетания в произвольном взвешенном графе быстрым
алгоритмом Эдмондса (Edmonds).
Глава 35 — решение замкнутой и разомкнутой задач коммивояжёра на графах
и орграфах.
Нумерация глав, начиная с 29-й сдвинута. Исправлены мелкие технические и
стилистические ошибки. Пояснительная часть некоторых глав существенно
переработана с целью облегчить понимание изложенных алгоритмов.
Добавлено спустя 9 минут 48 секунд:Содержание материала Главы
- Код: Выделить всё
Знакомство с объектами, отношениями и множествами 2
Представление объектов в языке Delphi 3, 4, 5
Представление множеств, операции с множествами 6, 7
Понятие о сложности (трудоёмкости) алгоритмов 8
Задачи на множествах:
• разбиение множества на подмножества;
• задача о наименьшем разбиении (ЗНР);
• задача о наименьшем покрытии (ЗНП). 9, 10, 11
Представление отношений графами 12
Программная реализация графов, ввод и вывод графов 13
Группа задач на достижимость:
• взаимная достижимость вершин;
• кратчайшие пути между вершинами;
• выделение сильно связанных компонент. 14, 15, 16
Группа задач на размещение:
• независимые вершины и клики;
• доминирующие множества;
• раскраски;
• центры;
• p-центры;
• p-медианы. 17 – 22
Остовные деревья 23
Группа задач о потоках:
• максимальный поток в сети;
• поток, ограниченный сверху и снизу;
• минимальная стоимость потока. 24 — 26
Паросочетания:
• паросочетание в двудольном графе;
• паросочетание в произвольном графе. 27 — 29
Цикл Эйлера и задача почтальона:
• на неориентированном графе;
• на орграфе. 30, 31
Задачи Гамильтона и коммивояжёра:
• разомкнутая задача Гамильтона;
• замкнутая задача Гамильтона (контур);
• комбинирование методов для задач Гамильтона;
• замкнутая и разомкнутая задачи коммивояжёра. 32 — 35
