Алгоритмы на графах (книга "Графомания")

[Oleg_D]

Аннотация книги "Графомания"

Рассмотрены алгоритмы на графах и множествах. Неформальное изложение алгоритмов сопровождает работающий код c контрольными примерами, доведенными до числа. Код воплощен на объектно-ориентированном языке программирования Delphi. Подробно описана техника программирования задач, а листинги детально прокомментированы. Книга может служить дополнением к учебникам по дискретной математике, а также справочником по алгоритмам. Будет полезна студентам, аспирантам и программистам, решающим практические задачи на графах.

Ссылки для скачивания:

http://oleg.derevenets.com/Page02.html
http://oleg.derevenets.com/Page04.html

[Alex2013]

Спасибо ! Пригодится.

[Oleg_D]

Вторая редакция от 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

[zub]

Еще реализация либы для графов в fpc/lazarus - https://github.com/zamtmn/agraphlaz
Не моя, я лишь адаптировал под linux и починил для 64бита. Очень старая но качественная (имхо)

С автором связяться не получилось, поэтому разместил в своем github

[Oleg_D]

Выложена редакция 02.02 от 13 мая 2024 года. Исправлены мелкие технические и стилистические шероховатости.