11.12. алгоритм построения деревьев

11.12. алгоритм построения деревьев: Справочник по математике для экономистов, В.И. Ермаков, 2009 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Содержит материал, позволяющий анализировать экономические задачи и осуществлять расчеты. Отражены разделы линейной алгебры, математического программирования, сетевое программирование и планирование, обработка результатов измерений, статистический анализ.

11.12. алгоритм построения деревьев

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

Алгоритм построения минимального покрывающего дерева. Просматривают ребра графа G в порядке возрастания их весов. Если ребро включается в покрывающее дерево, то его окрашивают в голубой цвет, если не включается—в оранжевый. Ребра, включенные в дерево, образуют граф, состоящий из нескольких компонент. Если концевые вершины просматриваемого ребра принадлежат одной и той же компоненте, то ребро образует цикл с ребрами, ранее включенными в дерево. Такое ребро не включают в дерево. Если же концевые вершины не принадлежат одной компоненте, то ребро включают в дерево. Вершины одной связной компоненты составляют букет.

1. Берут любое ребро, не являющееся петлей. Окрашивают его в голубой цвет, а его концевые вершины включают в первый букет.

323

Выбирают неокрашенное ребро и окрашивают его:

а) в оранжевый цвет, если концевые вершины ребра принадлежат одному и тому же букету;

б) в голубой цвет, если:

концевые вершины не принадлежат ни одному из букетов (в этом случае вершины включают в новый букет);

концевые вершины принадлежат разным букетам (в этом случае эти букеты объединяют в один);

один конец ребра принадлежит некоторому букету, а второй не входит ни в один букет (в этом случае второй конец включают в тот же букет).

Заканчивают процедуру, если все вершины графа вошли в один букет. В противном случае переходят в шагу 2.

Число шагов при выполнении алгоритма конечно, так как оно не превышает числа ребер графа. Если голубые ребра не образуют покрывающего дерева, то у исходного графа его нет.

О Пример. В новом районе имеется шесть жилых массивов. Нужно соединить их между собой дорогами, стоимость прокладки которых была бы минимальна. В таблице приведена стоимость постройки дорог между каждой парой жилых массивов:

Рис. 11.22

Построено покрывающее дерево, вес которого равен 25 (рис. 11.22). •

Справочник по математике для экономистов

Справочник по математике для экономистов

Обсуждение Справочник по математике для экономистов

Комментарии, рецензии и отзывы

11.12. алгоритм построения деревьев: Справочник по математике для экономистов, В.И. Ермаков, 2009 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Содержит материал, позволяющий анализировать экономические задачи и осуществлять расчеты. Отражены разделы линейной алгебры, математического программирования, сетевое программирование и планирование, обработка результатов измерений, статистический анализ.