Кістякове дерево англ Spanning tree зв язаного неорієнтованого графа ациклічний тобто без циклів зв язний підграф цього

Кістякове дерево (англ. Spanning tree) зв'язаного неорієнтованого графа — ациклічний (тобто, без циклів) зв'язний (підграф) цього графа, який містить усі його вершини. Неформально кажучи, кістякове дерево складається з деякої підмножини (ребер) графа, таких, що рухаючись цими ребрами можна з будь-якої вершини графа потрапити до будь-якої іншої.
Кістякове дерево також називають каркасним деревом, ^[], кістяком або каркасом графа.

Властивості

Будь-яке кістякове дерево у графі з n вершинами містить рівно n — 1 ребер. Кількість кістякових дерев у повному графі з n вершинами подається відомою формулою Келі: $n^{n-2}$

У загальному випадку, кількість кістякових дерев у довільному графі можна обчислити за допомогою так званої матричної теореми про дерева^[].

Кістякове дерево може бути побудовано майже будь-яким алгоритмом обходу графа, наприклад пошуком у глибину або у ширину. Воно складається з усіх пар ребер (u, v), таких, що алгоритм, переглядаючи вершину u, виявляє в її списку суміжності нову, невиявлену раніше вершину v. Кістякове дерево, побудоване обходом графа починаючи з вершини s за алгоритмом Дейкстри, має властивість, що найкоротший шлях у графі з вершини s до будь-якої іншої вершини — це шлях з s до цієї вершини в побудованому дереві.

Існує кілька паралельних і пошуку кістякового дерева. Як практичний приклад розподіленого алгоритму можна навести протокол STP.

Якщо кожному ребру графа присвоєно вагу ((зважений граф)), то пошук кістякового дерева, яке суму ваги його ребер, здійснюють численні алгоритми пошуку мінімального кістякового дерева.

Докладніше: Мінімальне кістякове дерево

Задача про пошук кістяка, в якому степінь кожної вершини не перевищує деякої наперед заданої константи k, є NP-повною^[].

Узагальнення

Поняття неоднозначне, під ним можуть розуміти один з таких підграфів:

Будь-який ациклічний підграф, до якого входять всі вершини графа, але він не є зв'язним^[];
У незв'язному графі — підграф, що складається з об'єднання кістякових дерев для кожної його компоненти зв'язності.

Див. також

Примітки

Р.М. Трохимчук. Теорія графів. — Навчальний посібник для студентів факультету кібернетики. — К : РВЦ «Київський університет», 1998. — С. 24. — .
Ю. Нікольский, В. Пасічник, Ю. Щербина. Дискретна математика. — К : BHV, 2007. — С. 368. — .

[Трохимчук-1] Р.М. Трохимчук. Теорія графів. — Навчальний посібник для студентів факультету кібернетики. — К : РВЦ «Київський університет», 1998. — С. 24. — .

[2] Ю. Нікольский, В. Пасічник, Ю. Щербина. Дискретна математика. — К : BHV, 2007. — С. 368. — .