- •16. Типы конечных графов
- •Типы конечных графов
- •Матрицы смежности и инцидентности
- •Изоморфизм графов общего вида
- •Признаки непланарных графов
- •Алгоритм поиска в глубину
- •Реализация
- •Способы построения матрицы достижимости [править]Перемножение матриц
- •[Править]Случай нескольких путей
- •Каркас неориентированного графа
- •Формулировка
- •[Править]Оценка
- •Обозначения
- •[Править]Псевдокод
- •[Править]Описание
- •[Править]Доказательство корректности
- •Неформальное описание
- •[Править]Формальное описание
- •Основные определения
- •Классификация автоматов по логическим свойствам функций переходов и выходов
- •[Править]Автомат Мили
- •[Править]Автомат Мура
- •Форма компактного представления, применяемая во время выполнения
- •Реализация компактного представления
- •Анализ конечных автоматов.
- •Описание
- •Алгоритм симплекс-метода [править]Усиленная постановка задачи
- •[Править]Алгоритм
- •Модели вычислений
- •Описание
- •Устройство машины Тьюринга
- •[Править]Описание машины Тьюринга
- •Условия применимости
- •[Править]Принцип жадного выбора
- •[Править]Оптимальность для подзадач
Формулировка
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.
[Править]Оценка
До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом общее время работы алгоритма Крускала можно принять за O(E * log(E)).
[править]Доказательство корректности алгоритма
Алгоритм Крускала действительно находит остовное дерево минимального веса, поскольку он является частным случаем алгоритма Радо — Эдмондса для графического матроида, где независимые множества — ациклические множества рёбер.
-------24 Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.
Описание
Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву присоединяется самое лёгкое из рёбер, соединяющих вершину из построенного дерева, и вершину не из дерева.
[править]Вход
Связный неориентированный граф
[править]Выход
Множество T рёбер минимального остовного дерева
Реализация
[править]Обозначения
— расстояние от -й вершины до построенного дерева
— предок -й вершины, то есть такая вершина , что легчайшее из всех рёбер соединяющее i с вершиной из построенного дерева.
— вес ребра
— приоритетная очередь вершин графа, где ключ —
— множество ребер минимального остовного дерева
------25 Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстройв 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
Обозначения
— множество вершин графа
— множество ребер графа
— вес (длина) ребра
— вершина, расстояния от которой ищутся
— множество посещенных вершин
— по окончании работы алгоритма равно длине кратчайшего пути из до вершины
— по окончании работы алгоритма содержит кратчайший путь из в
[Править]Псевдокод
Присвоим
Для всех отличных от
присвоим
Пока
Пусть — вершина с минимальным
занесём в
Для всех таких, что
если то
изменим
изменим