9.5.1. Определения

Пусть G(V, Е) — граф. Остовной подграф графа G(V, Е) — это подграф, содержа­щий все вершины. Остовный подграф, являющийся деревом, называется осто­вом.

ЗАМЕЧАНИЕ

Остов определяется множеством ребер, поскольку вершины остова суть вершины графа.

Несвязный граф не имеет остова. Связный граф может иметь много остовов.

ОТСТУПЛЕНИЕ

Если задать длины ребер, то можно поставить задачу нахождения кратчайшего остова. Эта задача имеет множество практических интерпретаций. Например, пусть задано множество аэродромов и нужно определить минимальный (по сумме расстояний) набор авиарейсов, который позволил бы перелететь с любого аэродрома на любой другой. Решением этой задачи будет кратчайший остов полного графа расстояний между аэродромами.

ЗАМЕЧАНИЕ

Существует множество различных способов найти какой-то остов графа. Например, алго­ритм поиска в глубину строит остов (по ребрам возврата). Множество кратчайших путей из заданной вершины ко всем остальным также образует остов. Однако этот остов может не быть кратчайшим.

Пример

На рис. 9.14 показаны диаграммы (слева направо) графа, дерева кратчайших путей из вершины 1 с суммарным весом 5 и два кратчайших остова этого графа.

Рис. 9.14. Граф, дерево кратчайших путей и два кратчайших остова