Идеи брата и сестры Островских

Алгоритм Островского

ВСТУПЛЕНИЕ

Доброго времени суток, дамы и господа. Меня зовут Николай Островский. В данной статье я собираюсь поделиться с вами своим способом построения минимального остовного дерева взвешенного связного неориентированного графа.

ПОДГОТОВКА

Для построения дерева я буду использовать граф из статьи «Алгоритм Краскала» «Википедии», приведенный в качестве примера, в главе «Пример». Ниже на всякий случай приведена весовая матрица указанного графа.

(матрицу вставить сложно и потому ниже просто список ребер (от автора Кузичкиной С.А.))

1. АB – 7
2. AD – 5
3. BC – 8
4. BD – 9
5. BE – 7
6. CE – 5
7. DE – 15
8. DF – 6
9. EF – 8
10. EG – 9
11. FG - 11

ПРАКТИКА

Начертите на бумаге карандашом граф согласно данной весовой матрице. Вершины обозначьте окружностями (белым цветом).

Находим ребро с минимальным весом. В нашем случае есть 2 таких ребер: ребра AD и CE с весом 5. Произвольно выбираем ребро AD. Красим ребро синим цветом, а его вершины A и D, белые вершины, - серым цветом.

Аналогично поступаем с ребром CE.

Из оставшихся ребер ребром с минимальным весом является ребро DF весом 6. Красим ребро DF синим цветом. Его серую вершину D – синим цветом, а его белую вершину F – серым.

Далее идут ребра AB и BE весом 7. Произвольно берем ребро AB. Красим ребро AB синим цветом, его белую вершину B – серым, а его серую вершину A – синим.

У ребра BE весом 7 обе вершины серые, а потому красим его вершины синим цветом. Само ребро тоже красим синим цветом.

Следующие по весу ребра — это ребра BC и EF весом 8. Однако вершина В ребра ВС – синяя, а вершина C - серая, а потому мы пропускаем ребро ВС. Вершина E ребра EF тоже синяя и вершина F – серая, а потому ребро BC мы тоже пропускаем.

Далее идут ребра BD и EG весом 9. Ребро DB мы пропускаем, так как у него обе вершины синие, а вот ребро EG для создания минимального остовного дерева использовать можем, так как его вершина E – синяя, а вершина G – белая.

На этом этапе у нас не осталось ни одной белой вершины. Это означает, что мы закончили построение минимального остовного дерева графа ABCDEFG.

Итак, дамы и господа, сейчас вы на практике познакомились с моим способом построения минимального остовного дерева.

Теперь нам осталось всего лишь структурировать все то, что вы поняли во время постройки минимального остовного дерева, а именно понять, из чего состоит мой способ построения минимального остовного дерева.

ИТОГ. РЕБРА.

• Ребра графа обозначаются серым цветом.
• Синим цветом обозначаются ребра графа, вошедшие в минимальное остовное дерево.

ИТОГ. ВЕРШИНЫ.

• Белым обозначаются «не посещенные» вершины, вершины в которые нельзя попасть по синему ребру, ребру, вошедшему в минимальное остовное дерево.
• Серым обозначаются «посещенные» вершины, вершины в которые можно попасть лишь одним путем, вершины, в которые ведет лишь одно синее ребро, вошедшее в минимальное остовное дерево.
• Синим обозначаются «постоянные» вершины или вершины «константы». Вершины, в которые ведут два пути, два синих ребра.

ИТОГ. АЛГОРИТМ.

Из белых вершин можно провести ребра:

• В белую вершину
• В серую вершину
• В синею вершину

Из серых вершин можно провести ребра:

• В белую вершину
• В серую вершину

Из синих вершин можно провести ребра:

• В белую вершину