Алгоритмы на графах

Определение графа и орграфа. Связь с отношениями. Вершины и ребра (дуги). Изображение и представления графов. Подграфы. Остовные подграфы. Порожденные подграфы. Отноше- ние порядка на подграфах и максимальные подграфы. Связность и компоненты связности. Гомоморфизм и изоморфизм графов. Инварианты. Степени вершин. Группа автоморфизмов графов.Подробнее

Неориентированное дерево. Критерии: n вершин и n − 1 ребро (при наличии связности; единственность цепи, соединяющей произвольные две вершины. Ориентированное дерево. Остовное дерево (остов). Пример орграфа без остова. Максимальный остовный лес и его построение с помощью алгоритма поиска в глубину. Алгоритм построения всех остовных деревьев графа. Понятие кратчайшего остовного дерева. Алгоритм Краскала и алгоритм Прима. Задача Штейнера. Связный ациклический (т.е. без циклов) неориентированный граф называется неориентированным деревом (далее просто деревом). Подробнее

Поскольку остов неориентированного графа определен неоднозначно, возникает задача выбора остова, оптимального в том или ином смысле. Например, граф представляет собой сеть дорог. Возникает задача прокладки маршрута наименьшей длины, проходящего через данные населенные пункты. Математически подобного рода задача ставится следующим образом. Пусть дан размеченный (взвешенный) граф, т.е. граф, каждому ребру которого приписан вес. Требуется выбрать остов наименьшего веса. Подробнее

Отношение достижимости и матрица достижимости. Граф как отношение (отношение смежности) и транзитивное замыкание. Понятие о размеченном графе. Сведение задачи к вычислению итерации матрицы в полукольце. Алгоритм Дейкстры. Алгоритм Флойда. Подробнее

Эйлеровы цепи и циклы. Циклы в графе. Фундаментальные циклы, числа Бетти. Разрезы. Критерий существования. Приложения. Эйлеровы графы. Подробнее