Алгоритмы построения остовного (покрывающего) дерева сети

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

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

Пусть G=(V,E) — связный неориентированный граф, содержащий  циклы, т.е. замкнутые маршруты,  где Vмножество вершин, а   E – множество ребер.   Остовным (покрывающим) деревом  называется подграф, не содержащий циклов, включающий все вершины исходного графа,  для  которого  сумма весов ребер минимальна.

Введем понятие  цикломатического числа (γ) показывающего, сколько ребер на графе нужно удалить, чтобы в нём не осталось ни одного цикла.  Цикломатическое   число  равно,  увеличенной  на  единицу разности    между количеством  ребер  и  количеством  вершин  графа.     

             γ  = nm +1,

  где       n – количество ребер ,   m – количество вершин,   

Например,   для графа,  изображенного на рисунке,  цикломатическое число равно

 

 

Ссылка на основную публикацию
Adblock detector