Аннотация книги "Графомания"
Рассмотрены алгоритмы на графах и множествах. Неформальное изложение алгоритмов сопровождает работающий код c контрольными примерами, доведенными до числа. Код воплощен на объектно-ориентированном языке программирования Delphi. Подробно описана техника программирования задач, а листинги детально прокомментированы. Книга может служить дополнением к учебникам по дискретной математике, а также справочником по алгоритмам. Будет полезна студентам, аспирантам и программистам, решающим практические задачи на графах.
Ссылки для скачивания:
http://oleg.derevenets.com/Page02.html
http://oleg.derevenets.com/Page04.html
Алгоритмы на графах (книга "Графомания")
Модератор: Модераторы
Спасибо ! Пригодится.
Вторая редакция от 17 ноября 2022 г.
Вторая редакция книги дополнена двумя главами:
Глава 29 — поиск паросочетания в произвольном взвешенном графе быстрым
алгоритмом Эдмондса (Edmonds).
Глава 35 — решение замкнутой и разомкнутой задач коммивояжёра на графах
и орграфах.
Нумерация глав, начиная с 29-й сдвинута. Исправлены мелкие технические и
стилистические ошибки. Пояснительная часть некоторых глав существенно
переработана с целью облегчить понимание изложенных алгоритмов.
Добавлено спустя 9 минут 48 секунд:
Содержание материала Главы
Вторая редакция книги дополнена двумя главами:
Глава 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
Еще реализация либы для графов в fpc/lazarus - https://github.com/zamtmn/agraphlaz
Не моя, я лишь адаптировал под linux и починил для 64бита. Очень старая но качественная (имхо)
С автором связяться не получилось, поэтому разместил в своем github
Не моя, я лишь адаптировал под linux и починил для 64бита. Очень старая но качественная (имхо)
С автором связяться не получилось, поэтому разместил в своем github
Выложена редакция 02.02 от 13 мая 2024 года. Исправлены мелкие технические и стилистические шероховатости.
Выложена редакция 03.01 от 2026-05-15
Она содержит следующие изменения.
· Глава 11 — кратно снижена погрешность жадного алгоритма для
задачи о наименьшем покрытии(ЗНП) до величины порядка 1%.
· Главы 33 и 34 — вдвое повышена скорость алгоритма для замкнутой
задачи Гамильтона.
· Улучшено представление контрольных примеров.
Она содержит следующие изменения.
· Глава 11 — кратно снижена погрешность жадного алгоритма для
задачи о наименьшем покрытии(ЗНП) до величины порядка 1%.
· Главы 33 и 34 — вдвое повышена скорость алгоритма для замкнутой
задачи Гамильтона.
· Улучшено представление контрольных примеров.
Замечательная книга! Но (имхо) слишком академичная. В свое время книга «Песни о Паскале» была хитом именно из-за актуальности поднимаемых там тем. Сейчас актуальными являются нейросети и всё, что рядом с ними, и, как мне кажется, тема искусственных нейросетей вплотную прилегает к темам, поднимаемым в «Графомании», и было бы совсем неплохо, если бы сделать дополнение или второй том, посвященный гибриду графов и искусственных нейросетей.
P. S.
«ИИ-справка от Алисы Яндесовны».
Гибридные подходы, сочетающие графы и искусственные нейронные сети (GNN — graph neural networks), представляют собой модели, которые объединяют возможности обработки графовых данных с другими методами машинного обучения или нейросетевыми архитектурами. Такие гибриды применяются в различных областях, например в малоshot-обучении, рекомендательных системах, биоинформатике и других.
...
Таким образом, гибридные модели на основе графов и нейросетей позволяют решать сложные задачи, где традиционные подходы могут быть недостаточно эффективными, и открывают новые возможности для развития технологий в различных областях.
P. S.
«ИИ-справка от Алисы Яндесовны».
Гибридные подходы, сочетающие графы и искусственные нейронные сети (GNN — graph neural networks), представляют собой модели, которые объединяют возможности обработки графовых данных с другими методами машинного обучения или нейросетевыми архитектурами. Такие гибриды применяются в различных областях, например в малоshot-обучении, рекомендательных системах, биоинформатике и других.
...
Таким образом, гибридные модели на основе графов и нейросетей позволяют решать сложные задачи, где традиционные подходы могут быть недостаточно эффективными, и открывают новые возможности для развития технологий в различных областях.
Спасибо за оценку моей работы, уважаемый Alex! Графовые алгоритмы применяются широко, в том числе в области ИИ, которая не входит в сферу моей компетенции, поэтому по этой части ничего не обещаю. Своей работой мне хотелось сделать упомянутые (непростые!) алгоритмы более доступными для тех, кто нуждается в них. В отличие от «Песен», предназначенных для школьников и начинающих, круг читателей «Графомании» гораздо уже, поэтому на конкуренцию с «Песнями» я, разумеется, не рассчитываю. 
Ещё раз спасибо!
Ещё раз спасибо!