Остовное дерево

Остовное дерево — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины. Неформально говоря, остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.

Понятие остовный лес неоднозначно, под ним могут понимать один из следующих подграфов:

• любой ациклический подграф, в который входят все вершины графа, но не обязательно связный;
• в несвязном графе — подграф, состоящий из объединения остовных деревьев для каждой его компоненты связности.

Остовное дерево также иногда называют покрывающим деревом, остовом или скелетом графа. Ударение в слове «остовный» у разных авторов указывается на первый (от слова о́стов) или на второй слог.

Свойства

• Любое остовное дерево в графе с <math>n</math> вершинами содержит ровно <math>n - 1</math> ребро.
• Число остовных деревьев в полном графе на <math>n</math> вершинах выражается формулой Кэли:

  <math>n^{n-2}</math>

• В общем случае, число остовных деревьев в произвольном графе может быть вычислено при помощи так называемой матричной теоремы о деревьях.

Алгоритмы

Остовное дерево может быть построено практически любым алгоритмом обхода графа, например поиском в глубину или поиском в ширину. Оно состоит из всех пар рёбер <math>(u, v)</math>, таких, что алгоритм, просматривая вершину <math>u</math>, обнаруживает в её списке смежности новую, не обнаруженную ранее вершину <math>v</math>.

Остовные деревья, построенные при обходе графа алгоритмом Дейкстры, начиная из вершины <math>s</math>, обладают тем свойством, что кратчайший путь в графе из <math>s</math> до любой другой вершины — это (единственный) путь из <math>s</math> до этой вершины в построенном остовном дереве.

Существует также несколько параллельных и распределённых алгоритмов нахождения остовного дерева. Как практический пример распределённого алгоритма можно привести протокол STP.

Если каждому ребру графа присвоен вес (длина, стоимость и т. п.), то нахождением оптимального остовного дерева, которое минимизирует сумму весов входящих в него рёбер, занимаются многочисленные алгоритмы нахождения минимального остовного дерева.

Задача о нахождении остовного дерева, в котором степень каждой вершины не превышает некоторой наперёд заданной константы <math>k</math>, является NP-полной.

См. также

• Матричная теорема о деревьях
• Минимальное остовное дерево
• Теорема Кэли о числе деревьев
• Spanning Tree Protocol

Отрывок, характеризующий Остовное дерево

– Вот ловко то! А? Дядюшка Игнат! – говорил мальчик, вдруг начиная хлопать обеими руками по клавишам.
– Ишь ты! – отвечал Игнат, дивуясь на то, как все более и более улыбалось его лицо в зеркале.
– Бессовестные! Право, бессовестные! – заговорил сзади их голос тихо вошедшей Мавры Кузминишны. – Эка, толсторожий, зубы то скалит. На это вас взять! Там все не прибрано, Васильич с ног сбился. Дай срок!
Игнат, поправляя поясок, перестав улыбаться и покорно опустив глаза, пошел вон из комнаты.
– Тетенька, я полегоньку, – сказал мальчик.
– Я те дам полегоньку. Постреленок! – крикнула Мавра Кузминишна, замахиваясь на него рукой. – Иди деду самовар ставь.
Мавра Кузминишна, смахнув пыль, закрыла клавикорды и, тяжело вздохнув, вышла из гостиной и заперла входную дверь.
Выйдя на двор, Мавра Кузминишна задумалась о том, куда ей идти теперь: пить ли чай к Васильичу во флигель или в кладовую прибрать то, что еще не было прибрано?
В тихой улице послышались быстрые шаги. Шаги остановились у калитки; щеколда стала стучать под рукой, старавшейся отпереть ее.
Мавра Кузминишна подошла к калитке.
– Кого надо?
– Графа, графа Илью Андреича Ростова.
– Да вы кто?
– Я офицер. Мне бы видеть нужно, – сказал русский приятный и барский голос.
Мавра Кузминишна отперла калитку. И на двор вошел лет восемнадцати круглолицый офицер, типом лица похожий на Ростовых.
– Уехали, батюшка. Вчерашнего числа в вечерни изволили уехать, – ласково сказала Мавра Кузмипишна.
Молодой офицер, стоя в калитке, как бы в нерешительности войти или не войти ему, пощелкал языком.
– Ах, какая досада!.. – проговорил он. – Мне бы вчера… Ах, как жалко!..
Мавра Кузминишна между тем внимательно и сочувственно разглядывала знакомые ей черты ростовской породы в лице молодого человека, и изорванную шинель, и стоптанные сапоги, которые были на нем.
– Вам зачем же графа надо было? – спросила она.
– Да уж… что делать! – с досадой проговорил офицер и взялся за калитку, как бы намереваясь уйти. Он опять остановился в нерешительности.
– Видите ли? – вдруг сказал он. – Я родственник графу, и он всегда очень добр был ко мне. Так вот, видите ли (он с доброй и веселой улыбкой посмотрел на свой плащ и сапоги), и обносился, и денег ничего нет; так я хотел попросить графа…
Мавра Кузминишна не дала договорить ему.
– Вы минуточку бы повременили, батюшка. Одною минуточку, – сказала она. И как только офицер отпустил руку от калитки, Мавра Кузминишна повернулась и быстрым старушечьим шагом пошла на задний двор к своему флигелю.
В то время как Мавра Кузминишна бегала к себе, офицер, опустив голову и глядя на свои прорванные сапоги, слегка улыбаясь, прохаживался по двору. «Как жалко, что я не застал дядюшку. А славная старушка! Куда она побежала? И как бы мне узнать, какими улицами мне ближе догнать полк, который теперь должен подходить к Рогожской?» – думал в это время молодой офицер. Мавра Кузминишна с испуганным и вместе решительным лицом, неся в руках свернутый клетчатый платочек, вышла из за угла. Не доходя несколько шагов, она, развернув платок, вынула из него белую двадцатипятирублевую ассигнацию и поспешно отдала ее офицеру.