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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

22
Важное значение имеет такая точка зрения, когда деревья или лес являются частями
некоторого графа, т.е. образуются из его ребер. Любая связная совокупность ребер,
не содержащая контуров, вместе с инцидентными им вершинами образует дерево
графа. Если такое дерево является суграфом (содержит все вершины графа), то оно
называется остовом (каркасом) графа G. Очевидно
, что в каждом графе существует
остов: разрушая в каждой компоненте циклы, т.е. удаляя лишние ребра, придем к
остову. Так как петля представляет собой простейший цикл, состоящий из одного
ребра, то она не может входить в состав любого дерева графа. Ребра графа, которые
принадлежат его дереву, называют его ветвями.
Несложно
показать, что число ребер произвольного графа G, которые необходимо
удалить для получения остова, не зависит от последовательности их удаления и
равно m(G)-|G|+k(G), где m(G) – число ребер, k(G) – число компонент графа G.
Рис. 30.Дерево как часть графа, а – исходный граф, б – дерево, в – остов.
Выше было определено цикломатическое число графа G:
ν
(G)=m(G)-|G|+k(G)
Справедливы утверждения:
1) Граф G является лесом тогда и только тогда, когда
ν
(G)=0;
2)
Граф G имеет единственный цикл тогда и только тогда, когда ν (G)=1;
3)
Граф, в котором число ребер не меньше, чем число вершин, содержит цикл.
Остов минимального веса.
Рассмотрим задачу, возникающую при проектировании линий
электропередачи, трубопроводов, дорог и т.п., когда требуется заданные центры
соединить некоторой системой каналов связи так, чтобы любые два центра были
связаны либо непосредственно соединяющим их каналом, либо через
другие центры
и каналы, и чтобы общая длина (или, например, стоимость) каналов связи была
минимальной. В этой ситуации заданные центры можно считать вершинами полного
графа с весами ребер, равными длинам (стоимости) соединяющих эти центры
каналов. Тогда искомая сеть будет кратчайшим остовным подграфом полного графа.
Очевидно, что этот кратчайший остовный подграф
должен быть деревом. Решение
этой задачи простым перебором вариантов потребовало бы чрезвычайно больших
вычислений даже при относительно малых n, поскольку полный граф К
n
содержит
n
n-2
различных остовных деревьев. Однако имеются эффективные алгоритмы ее
решения. Опишем алгоритмы Дж. Краскала и Р. Прима применимые к
произвольному связному графу.
Задача
. В связном взвешенном графе G порядка n найти остов минимального
веса.
Алгоритм Краскала, решающий эту задачу, заключается в следующем.

Страницы