Дискретная математика

145 В других дорогах пет твоей, а в твоей содержатся все дороги. П. Коэльо § И. Задача о минимальном соединении Пусть имеется п городов. Требуется соединить их телефонной или газовой сетью, но так, чтобы минимизировать, например, суммарную длину телефонного кабеля или газопроводов соответственно. Очевидно, что если соединение имеет минимальную длину, то циклов не должно быть. Следовательно, требуется построить на заданных вершинах дерево, обладающее минимальной суммой длин ребер. При достаточно большом числе вершин перебрать все возможные деревья невозможно (слишком их много) даже с помощью ЭВМ, поэтому необходимо разработать процедуру, приводящую к решению за приемлемое время. В терминологии теории графов эту задачу можно сформулировать следующим образом. Дан связный взвешенный граф G(V,X) для каждого ребра u=(v,u) которого определен вес (длина) f2(v,u). Задача о минимальном соединении состоит в построении остовного подграфа Т (связного подграфа Т, содержащего все вершины G) и такого, чтобы его мера /л(Т)= Е (vM)eT был а минимальной. Очевидно, Т должно быть деревом. Для решения сформулированной задачи известны различные алгоритмы. Рассмотрим алгоритм Краскала (Kruskal). Построение начинается с выбора кратчайшего ребра Ti=E] в G. На каждом последующем г-м шаге, > 2, добавляется к Ti-i такое ребро £ „ что оно является кратчайшим из оставшихся и получающийся граф Г, не имеет циклов. Если имеется несколько таких ребер одинаковой длины, то можно выбирать любой из них. Докажем, что Г„./ является остовны.м подграфом с минимальной мерой. Т „.1, не имеет циклов и содержит п-1 рёбер, следовательно, является деревом, связывающим все вершины графа. Пусть Т является деревом, содержащим (покрьшающим) все вершины графа G, я Т имеет минимальную меру и(Т)< /u(S), S - любое дерево, покрывающее все вершины. Если Т= T „.i, то утверждение доказано. Допустим, что Т„.1. Считаем, что рёбра дерева перенумерованы в том порядке, в котором они присоединялись к T „.i при его построении. Так как Т „.1, то в Т,,.] найдется хотя бы одно ребро, не содержащееся в Т. Пусть Е, - первое такое ребро (в перенумерованной последовательности рёбер), тогда граф TuEi будет иметь цикл С. Так как Г„., не имеет циклов, существует ребро Е' в С, не принадлежащее Г„./. Граф Mi=TuEi \ Е' тоже будет деревом, покрывающим все вершины графа G. Дерево Г имеет минимальную меру, поэтому /л(М()> /л(Т). По построению Mi и из последнего неравенства имеем: 1л(М) = iufT)^pi(Ei)-fi(E')