|
|
ПОДСЕКЦИЯ «МАТЕМАТИКА»
ПОСТРОЕНИЕ МИНИМАЛЬНЫХ ОСТОВНЫХ ДЕРЕВЬЕВ
Батаршина Г.М., группа 38-61 (Зарипова З.Ф.)
Рассмотрим задачу. Шесть городов^ нужно соединить сетью дорог так, -„бы из каждого города можно было проехать в любой другой. Известны «мости прокладки дорог между каждой парой городов, нужно инимизировать суммарную стоимость дорог.
Введем понятия необходимые для решения задачи. Пусть каждому ребру / vi Графа G(V,E) поставлено в соответствие положительное число w(e)>О, называемое весом ребра.
Весом остовного дерева Т называют сумму весов рёбер, составляющих это дерево. Дерево минимального веса называется минимальным остовным деревом. Рассмотрим строящие минимальные остовные деревья.
При построении минимального остовного дерева можно использовать алгоритм Краскала. Кратко опишем алгоритм без обоснования.
Шаг 1. Упорядочить рёбра графа в порядке возрастания весов. Пусть w(el)Шаг 2. Включить ребро el с минимальным весом в строящееся дерево Т.
Шаг 3. Для i=2, 3,...,q выполнить: если ребро ei не образует цикла с уже включёнными рёбрам, включить ребро ei в дерево Т, иначе пропустить ребро «'. Закончить работу, когда будут выбраны р - 1 рёбер (р - число вершин в графе G).
Особенность алгоритма: Е — множество рёбер графа, е - семейство подмножеств рёбер, не образующих цикла. Задача отыскивания подмножества минимального веса ничем не отличается от задачи отыскивания подмножества максимального веса.
Каждый город представим вершиной графа. Дороги - это рёбра графа.
вес ребра равен стоимости прокладки соответствующей дороги. Граф задан
матрицей смежности, в которой вместо единиц стоят веса рёбер. Так как
атрица смежности неориентированного графа симметрична относительно
внои диагонали, достаточно определить только элементы матрицы, лежащие
выше главной диагонали.
?Ы ®-^Ч2>
Рис.1
Рис.2
193
|
