Відповідно до формули Кейлі, граф із V вершинами може мати V^{(V-2)} різних позначених дерев. Тому ми можемо сказати, що загальна кількість остовних дерев у повному графі буде дорівнювати V^{(V-2)}.
Якщо G є графом або мультиграфом, а e є довільним ребром G, то кількість t(G) охоплюючих дерев G задовольняє рекуррентне видалення-скорочення t(G) = t(G − e) + t(G/e), де G − e — мультиграф, отриманий видаленням e, а G/e — скорочення G на e.
Дано граф G=(V,E), підграф G, який з’єднує всі вершини і є деревом, називається остовним деревом . Наприклад, припустімо, що ми починаємо з цього графіка: ми можемо видаляти ребра, поки не залишимо дерево: результатом буде охоплююче дерево. Очевидно, що охоплююче дерево матиме |V|-1 ребра, як і будь-яке інше дерево.
Перевірка стану інтерфейсів екземплярів Spanning-Tree
- Щоб перевірити стан інтерфейсу екземпляра spanning-tree, скористайтеся командою show interfaces: user@host> show interfaces назва інтерфейсу.
- Ви можете визначити стан інтерфейсу таким чином: якщо в полі BPDU Error немає значення, інтерфейс увімкнено.
Як ефективно створити всі можливі охоплюючі дерева з…
- Отримати всі ребра графа.
- Отримайте всі можливі комбінації V-1 з ребер E.
- Відфільтруйте комбінації, які не є охоплюючим деревом (для охоплюючого дерева всі вузли всередині одного набору ребер V-1 мають з’являтися рівно один раз)