кістяк
Кістяк - ациклічний зв'язний підграф даного зв'язкового неориентированного графа. в який входять всі його вершини. Неформально кажучи, кістяк складається з деякого підмножини ребер графа, таких, що з будь-якої вершини графа можна потрапити в будь-яку іншу вершину, рухаючись по цим ребрах, і в ньому немає циклів, тобто з довільної вершини можна потрапити в саму себе, не пройшовши якесь ребро двічі.
Поняття остовно ліс неоднозначно, під ним можуть розуміти один з наступних подграфов:
- будь-який ациклический підграф, в який входять всі вершини графа, але не обов'язково зв'язний;
- в незв'язному графі - підграф, що складається з об'єднання остовних дерев для кожної його компоненти зв'язності.
Властивості [ред]
- Будь-яке кістяк в графі з вершинами містить рівно ребро.
- Число остовних дерев в повному графі на вершинах виражається знаменитої формулою Келі. [2]
- У загальному випадку, число остовних дерев в довільному графі може бути обчислено за допомогою так званої матричної теореми про дерева.
Алгоритми [ред]
Кістяк може бути побудовано практично будь-яким алгоритмом обходу графа, наприклад пошуком в глибину або пошуком в ширину. Воно складається з усіх пар ребер, таких, що алгоритм, переглядаючи вершину, виявляє в її списку суміжності нову, поки не виявлену раніше вершину.
Остовне дерева, побудовані при обході графа алгоритмом Дейкстри. починаючи з вершини, володіють тим властивістю, що найкоротший шлях в графі з до будь-якої іншої вершини - це (єдиний) шлях з до цієї вершини в побудованому остовном дереві.
Існує також кілька паралельних і розподілених алгоритмів знаходження остовного дерева. Як практичний приклад розподіленого алгоритму можна привести протокол STP.
Якщо кожному ребру графа привласнений вага (довжина, вартість і т. П.), То знаходженням оптимального остовного дерева, яке мінімізує суму ваг входять до нього ребер, займаються численні алгоритми знаходження мінімального остовного дерева [3].
Завдання про знаходження остовного дерева, в якому ступінь кожної вершини не перевищує деякої наперед заданої константи, є NP-повною. [4]