Курапов С.В. Алгоритмические методы в теории графов

Запорожье: Запорожский национальный университет, 2012. — 196 с. — ISBN: 978-966-599-408-4.Изучение алгоритмов является самой сердцевиной науки о вычислениях. Приемы создания алгоритмов и алгоритмические методы рассматриваются во многих не только классических университетских курсах, но и во многих инженерных дисциплинах. К настоящему времени в мировой практике накоплен огромный опыт разработки алгоритмов для решения задач комбинаторного характера, значительная часть которых – задачи на графах. Целью данной работы является ознакомление с важнейшими достижениями в этой области. В нем излагаются основные понятия и математические факты из теории графов и наиболее интересные и важные алгоритмы для решения задач на графах. Большое внимание уделяется умению выбрать алгоритмическую структуру для конкретно решаемой задачи, обоснованию алгоритмов и анализу их трудоемкости.
Для научных работников, студентов и аспирантов высших учебных заведений.Введение
Структуры данных и алгоритмы
Генерирование соединений
Перестановки
Сочетания
Размещения
Элементы теории графов
Связанные списки
Алгоритм формирования матрицы инциденций
Подграфы и суграфы
Клики графа, множество вершинных покрытий и независимое множество вершин
Алгоритм выделения клик графа методом корневого дерева
Пространство суграфов
Деревья, разрезающие множества и циклы
Операции над суграфами
Графы и пространство суграфов
Размерность подпространств циклов и разрезов
Связь между подпространствами циклов и разрезов
Ортогональность подпространств циклов и разрезов
Свойства характерных подмножеств подпространства циклов и подпространства разрезов
Выделение конечного множества единичных циклов ( циклов)
Множество ребер и построение множества единичных циклов
Фундаментальная и базисная системы циклов и разрезов
Алгоритмы для выделения множества единичных разрезов и циклов.
Формирование множества единичных циклов алгоритмом поиска в ширину
Формирование множества единичных циклов из циклов полного графа.
Множество единичных разрезов и циклов как инварианты графа
Свойства множества единичных циклов
0-подмножество единичных циклов и дубль-циклы в графе
Алгоритм выделения множества простых циклов и дубль-циклов в графе
Метод эталона для нахождения дубль-циклов в полных графах
Свойства 0-подмножеств, состоящих из единичных циклов и дубльциклов
Программное и алгоритмическое обеспечение системы решения задач методами теории графов.
Функциональные задачи теории графов
Вычислительная сложность алгоритмов
Структура программного обеспечения и организация вычислительного процесса
Модуль DRAWNAT
Модуль RASTAMAG
Модуль RASMAPKG
Модуль RASSWAZI
Модуль RASMOSTG
Модуль RASRANGR
Модуль RARRANGM
Модуль RASKLIKG
Модуль RASWEPOG
Модуль RASWNYPG
Модуль RASTAYCG
Модуль RASYROWG
Модуль TREENEW
Модуль DLPRIMER
Встроенные процедуры
Встроенные процедуры системы
Procedure InputText
Procedure DrawCurcor
Procedure Formlncide
Procedure DrawTabl
Procedure DrawContur
Procedure FormSvart
Procedure FormVolna2
Procedure RandomizeGraph
Procedure RandomizeGraphNM
Procedure RandomizeGraphSave
Procedure FormStl
Procedure FormStart
Procedure FormKlicM2
Procedure FormStek
Procedure FormSave.
Procedure FormSt
Procedure FormMs2
Procedure FormVerPoc
Procedure FormVolna
Procedure FormKpris
Procedure FormDiz
Procedure FormSwigug
Procedure FormDozas
Procedure FormSoasda
Procedure FormVegin
Procedure FormVolna1
Procedure FormTreeGr
Procedure FormTreeRgr
Procedure FormMatrixMinus
Procedure FormVolna2Tree
Procedure FormCircleFund
Procedure FormSecheniaj
Procedure Form000
Procedure Form000111
Procedure FormMonitor
Procedure FormPemum
Procedure Shell2
Procedure FormPostr
Procedure FormYk
Procedure FormRetzen
Procedure FormObr
Литература