Теория графов - раздел математики, изучающий свойства графов. Последние упрощенно можно рассматривать как совокупность точек (вершины ) соединенных линиями ( ребрами ). Определение графу является настолько общим, что этим термином можно описывать множество событий и объектов повседневной жизни. Высокий уровень абстракции и обобщения позволяет использовать типовые алгоритмы теории графов для решения внешне непохожих задач в транспортных и компьютерных сетях, строительном проектировании, молекулярном моделировании подобное.
Алгоритмы на графах
- Поиск в глубину.
- Поиск в ширину.
- Топологическая сортировка.
- Фундаментальная множество циклов.
- Эйлеров цикл. Теорема Эйлера.
- Гамильтонов цикл.
- Алгоритм Беллмана - Форда.
- Алгоритм Дейкстры.
- Алгоритм Флойда-Уоршела.
- Транзитивное замыкание графа.
- Системы неперетинаючих множеств.
- Связность. Алгоритмы Прима и Крускала. остовное дерево
- Коды Прюфера.
- Матричная формула Кирхгофа.
- Нахождения точек сопряжения и мостов в графе.
- Алгоритм Эдмондс-Карпа.
- Поиск максимального паросочетания.