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

146 > 1л(Т). Тогда jj(Ei)-iu(E')^ О, поэтому /и(Е^)>1и(Е). Неравенства pi(Ej)>ju(E') не может быть, так как иначе при построении дерева вместо £ , было бы выбрано Е', ибо каждый раз выбирается ребро с минимальной длиной, но чтобы не было цикла. При выборе Е' вместо £ ,• не было бы цикла, ибо дикл С порожден ими обоими, а выбор одного из них не дает цикла. Поэтому ^(Е^)=1Л(Е'), тогда JU(MI)=F.I(T), так что граф (дерево) тЦ также являетс деревом с минимальной мерой. Но М^=ТиЕгЕ' ( £ ,бГ„./, E'g следовательно Mi имеет больше с Г„.; ребер, чем Т. Повторяя аналогичным образом, получим ju(M „.i)=ju(T), что и требовалось доказать. Указанный алгоритм Краскала можно представить следующим образом; Вход: список X ребер графа G с их длинами. Выход: множество Требер кратчайшего остова. Т~0 Упорядочить X в порядке возрастания длин к := 1 {номер рассматриваемого ребра} for i from 1 to m-\ do while добавление ребра E(k) образует цикл в Tdo к:=к+ 1 (пропустить это ребро} end while Т:=Т {Е(к)} (добавить это ребро в 7 } end Можно убедиться, что сложность алгоритма Краскала есть OCmlog^m), где т - число ребер графа. Рассмотрим работу алгоритма Краскала для графа G, представленного на рис. 5.21, а) [11]. Длины ребер графа представлены на этом рисунке. На первом шаге выбирается ребро длины 1, на втором - добавляется ребро длины 2. На третьем шаге - добавляется ребро длины 3; а на четвертом шаге - ребро длины 4, Затем добавляется ребро, имеющее длину 5. Теперь нужно выбрать последнее ребро. Ребер длины б в данном графе четыре. Если выбрать ребро CF либо BD, то получим цикл. Следовательно, их выбирать нельзя. Из ребер FG и DG можно выбирать любое из них, выберем ребро FG. Указанные шаги алгоритма представлены на рис. 5.21, а). Для нахождения остовного подграфа с минимальной мерой можно использовать также алгоритм Дейкстры - Прима, являющийся реализацией, так называемого, жадного алгоритма. Жадные алгоритмы используют в каждый момент лишь часть исходных данных и принимают решения на основе этой части. В данном случае на каждом шаге рассматривается только множество ребер, допускающих присоединение к уже построенной части остовного дерева, и выбирается из них ребро с наименьшей длиной (весом). Повторяя эту процедуру, получим остовное дерево с наименьшей мерой.