Остовное дерево
Остовное дерево — это подграф связного графа, который содержит все его вершины, соединяет их и не имеет циклов. Иными словами, оно оставляет достаточно рёбер, чтобы между любыми двумя вершинами можно было пройти, но не оставляет ни одного лишнего ребра.
Главные свойства
Если исходный граф содержит \(n\) вершин, любое его остовное дерево содержит ровно \(n-1\) рёбер. Между каждой парой вершин остовного дерева существует единственный простой путь. Если добавить к остовному дереву любое ребро исходного графа, появится цикл; если удалить хотя бы одно ребро дерева, граф перестанет быть связным.
Пусть граф имеет вершины \(A\), \(B\), \(C\), \(D\) и рёбра \(AB\), \(BC\), \(CD\), \(DA\), \(AC\). Набор рёбер \(AB\), \(BC\), \(CD\) образует остовное дерево: все четыре вершины соединены, циклов нет, рёбер \(4-1=3\). А набор \(AB\), \(BC\), \(CA\), \(CD\) не подходит: в нём есть цикл \(A\to B\to C\to A\).
Остовное дерево — не обязательно единственное и не обязательно содержит все рёбра исходного графа. Оно должно содержать все вершины, но только часть рёбер. Если исходный граф несвязный, единого остовного дерева для него не существует: можно построить лишь остовное лесное объединение для его компонент связности.
У графа 6 вершин. Сколько рёбер должно быть в любом его остовном дереве?
Главное
- Остовное дерево содержит все вершины исходного связного графа и не содержит циклов.
- Для \(n\) вершин в нём ровно \(n-1\) рёбер.
- Удаление любого ребра нарушает связность, а добавление любого лишнего ребра создаёт цикл.