Деревья и обходы графов
dlyachainikov.ru · Дискретная математикаОсновные определения
- Дерево – это связный ациклический граф.
Свойства дерева:
- Количество рёбер равно количеству вершин .
Остовное дерево
- Остовное дерево – минимальное дерево, содержащее все вершины исходного графа.
Алгоритмы построения остовных деревьев:
- Алгоритм Краскала: сортирует рёбра по возрастанию веса и добавляет их в дерево до тех пор, пока не будут охвачены все вершины.
- Алгоритм Прима: строит дерево из одной начальной вершины, добавляя рёбра с минимальной стоимостью.
Пропуски
- дерево
- поиск_в_глубину
- алгоритм_Краскала
- остовное_дерево