информационно-новостной портал

Число помеченных деревьев с n вершинами равно .

Стягивающим (или остовным) деревом связного графа G называется произвольный его подграф, содержащий все вершины G и являющийся деревом. Остовным лесом графа G называется произвольный его подграф, содержащий все вершины G и являющийся лесом. Таким образом, компоненты связности остовного леса графа G являются стягивающими деревьями компонент G.

Построить остовный лес нетрудно: достаточно последовательно удалять из графа ребра, входящие в циклы, до тех пор, пока не будет построен ациклический граф (лес), который, очевидно, будет остовным для исходного графа.

Граф называется взвешенным, если каждому его ребру l поставлено в соответствие неотрицательное число  (вес ребра). Весом графа G = <V;E> называют сумму весов всех его рeбер:

Рассмотрим следующую задачу. Имеется n пунктов. Для любой пары пунктов i и j известна стоимость сооружения дороги между ними - cij . Требуется выбрать сеть дорог такую, чтобы любые два пункта соединялись каким-либо маршрутом и при этом стоимость ее сооружения была наименьшей.

Если рассмотреть полный граф порядка n, вершины которого будут соответствовать указанным (географическим) пунктам, а рeбра будут иметь вес, равный стоимости сооружения дороги между соответствующими пунктами, то задача формулируется так: в данном графе найти стягивающее дерево наименьшего веса. Существуют эффективные алгоритмы нахождения стягивающего дерева минимального веса в связном взвешенном графе. При описании следующих алгоритмов G = <V;E> будет обозначать исходный граф, а T = <V; P> - искомое дерево.

Просмотров: 673 | Дата добавления: 08.02.2016