МИНИМАЛЬНОЙ ДЛИНЫ

Коммуникационная сеть минимальной длины (или дерево кратчайших расстояний) – это совокупность дуг сети, имеющая минимальную суммарную длину и обеспечивающая достижение всех узлов сети, т.е. возможность попасть из любого узла в любой другой узел.

Алгоритм:

1. Начать с любого узла и соединить его с ближайшим узлом. Считаем, что эти узлы связанные, а все другие несвязанные.

2. Определить несвязанный узел, ближайший к одному из связанных узлов. Если таких «ближайших» узлов несколько, то выбрать любой. Добавить этот узел к связанным. И т.д., до тех пор, пока есть несвязанные узлы.

Пример. Университет устанавливает компьютерную систему электронной почты, которая позволит передавать сообщения между деканами восьми факультетов. Сеть возможных электронных связей между деканатами показана ниже. Протяженность коммуникаций в километрах отмечена на дугах.

Необходимо предложить проект системы связи, которая позволит всем восьми деканам обеспечить доступ к системе электронной почты. Решение должно обеспечить минимальную возможную общую длину коммуникаций.

Начнем с узла 1. Ближайший к нему узел – это узел 2 на расстоянии 2. Считаем, что узлы 1, 2 – связанные, и выделим эту связь.

Ближайшие несвязные узлы к связным узлам 1 и 2 – это узлы 3 и 6. Выбираем любой из них, например, узел 3. Ребро 1-3 выделяем и считаем узел 3 связанным.

Далее ищем ближайший несвязанный узел к узлам 1, 2, 3. Это узел 7 (ближайший к узлу 3).

Ближайший несвязанный узел к узлам 1, 2, 3, 7 – узел 5 (ближайший к узлу 7).

Далее аналогично. В результате получим минимальное дерево.

Его длина равна сумме расстояний на дугах 2+3+1+1+2+0,5+1=10,5 (км).