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

Модератор: Модераторы

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

Сообщение Oleg_D » 25.03.2020 22:26:12

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

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

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

http://oleg.derevenets.com/Page02.html
http://oleg.derevenets.com/Page04.html
Oleg_D
постоялец
 
Сообщения: 390
Зарегистрирован: 09.05.2011 11:28:36

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

Сообщение Alex2013 » 27.03.2020 19:26:53

Спасибо ! Пригодится.
Alex2013
долгожитель
 
Сообщения: 2922
Зарегистрирован: 03.04.2013 11:59:44

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

Сообщение Oleg_D » 18.11.2022 19:24:33

Вторая редакция от 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
Oleg_D
постоялец
 
Сообщения: 390
Зарегистрирован: 09.05.2011 11:28:36

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

Сообщение zub » 19.11.2022 08:21:23

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

С автором связяться не получилось, поэтому разместил в своем github
zub
долгожитель
 
Сообщения: 2884
Зарегистрирован: 14.11.2005 23:51:26


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

Рейтинг@Mail.ru