Построение и анализ алгоритмов. Минимальное остовное дерево. (Лекция 6.1)
01.03.2016 Алгоритмы на графах: построение МОД Дерево – связный граф, не содержащий циклов. Граф связный, если каждая пара различных вершин графа связана маршрутом. Для связного графа G = (V, E) остовным деревом (остовом, каркасом, стягивающим деревом, скелетом) является граф (дерево) T = (V, F), где F⊆ E. Рёбра дерева – ветви, остальные рёбра графа – хорды. В графе много остовов, а именно, число остовов nn-2. Остовное дерево … Повторение с предыдущей лекции 01.03.2016 Алгоритмы на графах: построение МОД В дереве из n вершин имеется m = n – 1 рёбер Доказательство (по индукции): Остовное дерево Ti, ni Удаляем некоторый узел и k инцидентных рёбер (k∈1..n − 1 ). Образуется лес из деревьев Ti с числом узлов ni (i ∈1..k).