Составители:
Рубрика:
11
На практике очень часто решается задача о построении сетей связи,
газопроводов, линий электропередач с минимальной “ стоимостью “, причем,
под “ стоимостью “ соответствующих
объектов можно понимать не только
финансовые затраты, но также и количество материала, требующееся для
построения объекта. На языке теории графов эта задача формулируется,
следующим образом:
Дан взвешенный граф с n вершинами. Построить для него остовное
дерево с минимальным суммарным весом ребер. Здесь в качестве вершин графа
выступают пункты, к которым следует проводить элементы соответствующей
сети, а в качестве ребер - участки этой сети. Вес p
ij
ребра ( x
i
, x
j
) в
зависимости от конкретной задачи может интерпретироваться, как количество
материала, используемого на изготовление ребра ( x
i
, x
j
), или его денежную
стоимость.
Опишем в общих чертах одну из процедур решения задачи о
минимальном остовном дереве - так называемый,
алгоритм
ближайшего соседа.
Обозначим через n число вершин и через m - число ребер графа.
1. Выбираем произвольную вершину, скажем x
1
, и сравниваем веса всех
ребер, инцидентных этой вершине. Ребро с минимальным весом включаем в
искомое дерево. Другую вершину выбранного ребра обозначим через x
2
.
2. Просматриваем все ребра, отличные от (x
1
, x
2
), инцидентные вершинам
x
1
и x
2
, выбираем из них ребро с минимальным весом и включаем его в
будущее дерево. Другую вершину, инцидентную этому ребру, обозначим через
x
3
.
3. Рассматриваем теперь три вершины x
1
, x
2
, x
3
,
сравниваем веса ребер,
инцидентных каждой из них и отличных от двух уже выбранных. Ребро с
наименьшим весом включаем в искомое дерево.
Дальнейшая процедура ясна: алгоритм прекращает работу после, того,
как будут пройдены все n вершины графа. Мы оставляем без доказательства
два следующих утверждения:
а). В процессе построения мы никогда не получим циклов,
б). Описанная выше процедура действительно порождает минимальное
остовное дерево.
Задача о кратчайшем пути
Многие прикладные задачи на языке теории графов могут быть
сформулированы следующим образом:
Пусть дан граф такой, что для любых двух его вершин из одной исходит,
а в другую заходит не более одного ребра (иначе говоря, граф не имеет
параллельных ребер). Пусть, кроме того, каждому ребру ( x
i
, x
j
) приписано
неотрицательное число R
ij
- его вес (здесь удобно интерпретировать веса ребер
как их длины). Веса не существующих ребер будем считать как угодно
большими и обозначать их символом ∞ . Для любых двух выделенных вершин
графа требуется найти длину кратчайшего пути между ними и указать этот
путь.
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
