Кістякове дерево: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
→Див. також: доповнення |
→Властивості: вікіфікація, оформлення |
||
Рядок 5:
== Властивості ==
Будь-яке каркасне дерево у графі з ''n'' вершинами містить рівно ''n — 1'' ребер.
Кількість кістякових дерев у повному графі з ''n'' вершинами подається відомою [[формула Келі|формулою Келі]]: <math>n^{n-2}</math>
У загальному випадку, кількість кістякових дерев у довільному графі може бути обчислено за допомогою так званої [[матрична теорема про дерева|матричної теореми про дерева]]{{Джерело?}}.
Рядок 15 ⟶ 14:
Існує кілька [[паралельний алгоритм|паралельних]] і [[розподілений алгоритм|розподілених алгоритмів]] пошуку каркасного дерева. Як практичний приклад розподіленого алгоритму можна навести протокол [[STP]].
Якщо кожному ребру графа присвоєно [[вага|вагу]], то пошук оптимального каркасного дерева, яке [[мінімізіція|мінімізує]] суму ваги його ребер здійснюють численні алгоритми пошуку мінімального каркасного дерева.
Задача про пошук кістяка, в якому [[ == Узагальнення ==
| |||