 |
Построение остова минимального веса
|
|
|
|
Решение этой задачи имеет большое значение в создании вычислительных сетей, в организации грузоперевозок или ремонтных работ на транспортной сети..
Основная идея состоит в следующем: если есть некоторый фрагмент остова G’=<X’; r’`> и ребро минимального веса l(хi;хj), одна из концевых вершин которого хi принадлежит фрагменту G’, то включить в фрагмент вторую вершину ребра хj и само ребро l(хi;хj). Процедуру продолжать до включения во фрагмент (n-1) ребра графа, где n-число вершин. Эта идея реализуется двумя алгоритмами: Дейкстра и Краскала.
Алгоритм Дейкстра:
шаг 1: определить начальную вершину остова x0;
шаг2: выбрать ребро минимального веса, смежное с начальной вершиной и сформировать фрагмент G’=<X’; r’`>, включив вторую концевую вершину в подмножество Х’;
шаг3: выбрать ребро минимального веса, смежное вершинам фрагмента и не являющееся петлей:
а) если вторая концевая вершина не принадлежит фрагменту,
то включить ее в подмножество Х’, а ребро включить в фрагмент остова G’=<X’; r’`>,
b) если вторая концевая вершина принадлежит фрагменту, то исключить данное ребро из анализа;
шаг 4: если все вершины графа вошли во фрагмент остова, то конец, иначе перейти к шагу 2.
Пример: найти для графа на рис. 3.27а) остов по алгоритму Дейкстра, начиная с вершины x0.
Результаты построения остова графа приведены в таблице.
| li | шаг итерации | L | ||||||||||
| вершины графа | x0 | - | ||||||||||
| x1 | - | |||||||||||
| x2 | - | |||||||||||
| x3 | - | |||||||||||
| x4 | - | |||||||||||
| x5 | - | |||||||||||
| x6 | - | |||||||||||
| x7 | - | |||||||||||
| x8 | - | |||||||||||
| x9 | - | |||||||||||
| ребра графа | l1 | |||||||||||
| l2 | ||||||||||||
| l3 | ||||||||||||
| l4 | - | |||||||||||
| l5 | ||||||||||||
| l6 | ||||||||||||
| l7 | - | |||||||||||
| l8 | ||||||||||||
| l9 | ||||||||||||
| l10 | ||||||||||||
| l11 | - | |||||||||||
| l12 | ||||||||||||
| l13 | - | |||||||||||
| S |
Вес минимального остова графа равен L=101.
|
|
|
Алгоритм Краскала:
шаг 1: установить частичный порядок ребер графа;
шаг2: выбрать ребро минимального веса, не являющееся петлей, сформировать фрагмент остова G’=<X’; r’`>, а концевые вершины ребра включить в подмножество Х’ÍХ;
шаг3: выбрать ребро минимального веса, не являющееся петлей и не принадлежащее фрагменту:
а) если фрагменту принадлежит одна вершина ребра, то вторую концевую вершину включить в подмножество Х’, а ребро включить в фрагмент остова G’=<X’; r’`>,
b) если ни одна концевая вершина ребра не принадлежит фрагменту остова, то сформировать фрагмент другого остова,
с) если концевые вершины принадлежат различным остовам, то соединить фрагменты;
шаг 4: если все вершины графа вошли во фрагмент остова, то конец, иначе перейти к шагу 2.
На каждом шаге итерации выбирается минимальное ребро из всего множества.
Пример: Найти для графа на рис. 3.26а) остов по алгоритму Краскала.
|
|
|
В табл. а) установлен частичный порядок на множестве ребер исходного графа.
таблица а)
| li | l6 | l8 | l9 | l1 | l5 | l7 | l3 | l12 | l4 | l10 | l11 | l2 | l13 |
| L |
таблица b)
| li | шаг итерации | L | ||||||||||
| вершины графа | x0 | - | ||||||||||
| x1 | - | |||||||||||
| x2 | - | |||||||||||
| x3 | - | |||||||||||
| x4 | - | |||||||||||
| x5 | - | |||||||||||
| x6 | - | |||||||||||
| x7 | - | |||||||||||
| x8 | - | |||||||||||
| x9 | - | |||||||||||
| ребра графа | l1 | |||||||||||
| l2 | ||||||||||||
| l3 | ||||||||||||
| l4 | - | |||||||||||
| li | шаг итерации | L | ||||||||||
| l5 | ||||||||||||
| l6 | ||||||||||||
| l7 | - | |||||||||||
| l8 | ||||||||||||
| l9 | ||||||||||||
| l10 | ||||||||||||
| l11 | - | |||||||||||
| l12 | ||||||||||||
| l13 | - | |||||||||||
| S |
Следует обратить внимание, что при построении остова на седьмом шаге все вершины графа были включены в три несвязных фрагмента остова. На восьмом и девятом шаге было выполнено соединение фрагментов в единый остов графа.
|
|
|
