Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

4.4.2. Поиск минимального связующего дерева
Дерево
.—.это.особый.вид.графа,.в.котором.между.любыми.двумя.вершинами.
существует.один.и.только.один.путь..Это.подразумевает,.что.в.дереве.нет.
циклов
.
(такие.графы.иногда.называют.
ациклическими
)..Цикл.можно.представить.как.
петлю:.если.возможно.из.начальной.вершины.пройти.по.всему.графу,.никогда.
не.проходя.повторно.ни.по.одному.из.ребер,.и.вернуться.к.начальной.вершине,.
то.в.этом.графе.есть.цикл..Любой.граф,.не.являющийся.деревом,.может.им.стать,.
если.удалить.из.него.некоторые.ребра..На.рис..4.6.показано.удаление.ребер,.по-
зволяющее.превратить.граф.в.дерево.
Связный
.
граф
.—.это.граф,.для.которого.существует.способ.добраться.из.любой.
вершины.в.любую.другую.вершину.(все.графы,.которые.мы.рассматриваем.в.этой.

---

124
Глава 4.
Графовые задачи
главе,.связные)..
Связующее
.
дерево
.—.это.дерево,.которое.соединяет.все.верши-
ны.графа..
Минимальное
.
связующее
.
дерево
.—.это.дерево,.которое.соединяет.все.
вершины.во.взвешенном.графе.и.имеет.минимальный.общий.вес.по.сравнению.
с.другими.связующими.деревьями..Для.каждого.взвешенного.графа.можно.найти.
минимальное.связующее.дерево.
Рис. 4.6.
На левом графе существует цикл между вершинами B, C и D,
поэтому он не является деревом. На правом графе ребро, соединяющее C и D, 
удалено, так что этот граф — дерево
Фу-у-ух,.слишком.много.терминологии!.Дело.в.том,.что.найти.минимальное.
связующее.дерево.—.это.то.же.самое,.что.найти.способ.связать.все.вершины.во.
взвешенном.графе.с.минимальным.весом..При.проектировании.любой.сети.—.
транспортной,.компьютерной.и.т..д..—.возникает.важная.практическая.проблема:.
как.с.минимальными.затратами.подключить.к.сети.все.узлы?.Этими.затратами.
могут.быть.провода,.трассы,.дороги.или.что-то.еще..Например,.для.телефонной.
сети.другой.способ.постановки.этой.задачи.таков:.«Какова.минимальная.длина.
кабеля,.необходимого.для.подключения.всех.телефонов?»