Инструменты пользователя

Инструменты сайта


examination:diskretka:question19

Вопрос №19. Остовное дерево

Пусть Г произвольный неориентированный граф. Остовным графом графа Г называется его минимальная часть, индуцирующая на множестве вершин графа Г отношение связности.

Замечание:

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

В случае бесконечного графа построение его остовного дерева требует применения трансфинитной индукции.(?)

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

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


Из педивикии

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

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

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

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

Свойства

  • Любое остовное дерево в графе с n вершинами содержит ровно n − 1 ребро.
  • Число остовных деревьев в полном графе на n вершинах выражается знаменитой формулой Кэли: n^{n-2}
  • В общем случае, число остовных деревьев в произвольном графе может быть вычислено при помощи так называемой матричной теоремы о деревьях.
examination/diskretka/question19.txt · Последние изменения: 2014/01/15 12:14 (внешнее изменение)