Элементы теории графов и их технические приложения - 50 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

50
построения наилучшей схемы административного подчинения по критерию
минимального количества непосредственных связей (минимуму непосредственных
подчиненных и непосредственных начальников), задача построения определенной
схемы связи в электрических сетях по критерию минимального количества
контактов, задача выбора при обработке деталей наилучшего порядка, который
должен удовлетворять определенной технологии и др.
При решении подобных задач приходится, имея допустимую
схему связей
объектов, выделить из нее какую-нибудь часть связей, удовлетворяющую
определенным критерием. В качестве элементов (вершин) могут выступать
некоторые узловые коммуникации (населенные пункты, магазины, склады, пункты
электроснабжения и т.д.). Каждая связь (дуга) между вершинами характеризуется
определенной величиной (временем, некоторыми затратами на строительство
коммуникаций, длиной пройденного пути и т.
д.). Требуется, не теряя связности
графа, найти один из вариантов сети, для которой достигается минимум суммарных
весов дуг. Аналогичные задачи могут встречаться при проектировании
строительства сетей транспортных, газовых, воздушных, сети коммуникаций для
передачи информации, при составлении графика выполнения работ и т.д.
Рассмотрим алгоритм решения такой задачи на примере графа изображенного
на рис. 62, в котором дуга
6,3
u с весом 5)6;3(
=
l входит в обязательном порядке в
искомый частичный граф.
Рис. 62. Рис. 63.
Шаг 1. Располагаем дуги графа в порядке убывания соответствующих им весов:
ij
u
6,4
u
4,3
u
6,4
u
′
5,2
u
6,3
u
6,5
u
2,3
u
2,3
u
′
3,1
u
4,2
u
2,1
u
5,4
u
ij
l
8 7 7 6 5 4 4 3 3 2 1 1
Шаг 2
. Рассматривая последовательно каждую дугу
ij
u , удаляем ее из исходного
графа, если вес этой дуги больше, чем длина пути от
i
x к
j
x .
Берем первую дугу
6,4
u из таблицы с максимальным весом 8
6,4
=l . Найдем
пути, соединяющие вершины 4 и 6 . В нашем случае такими путями являются
654
→→ с длиной 5 и 64 → с длиной 7
Среди этих путей выберем путь с наименьшей длиной 5. Следовательно, дуга
6,4
u с
весом 8
6,4
=l удаляется из исходного графа.

Страницы