🗊Презентация Взвешенные деревья

Остовные деревья

Определение. Остовное дерево – дерево Т, которое является подграфом графа G таким, что каждая вершина в G является вершиной в Т. Каждый связный граф имеет остовное дерево. Два метода построения остовного дерева. Первый – метод поиска в ширину, Второй – метод поиска в глубину. Первый метод: произвольную вершину v0 графа G выбирают в качестве корня дерева Т. Для каждой вершины v, смежной с вершиной v0, в дерево Т добавляется вершина v и ребро {v, v0}. Это вершины уровня 1. Затем берем каждую вершину vi уровня 1 и для каждой вершины vj и ребро {vi, vj}. На втором этапе – это вершины уровня 2. Процесс продолжается, пока в графе G не останется вершин, которые можно добавить в дерево.  Т является деревом. Если расстояние от v0 до вершины v графа G равно n, то эта вершина будет добавлена в дерево на уровне n.  Т является остовным деревом.

Пример. Граф Пусть вершина v0 выбрана в качестве первой вершины. Тогда L(v0) =0 и v0  V T. v1 является смежной вершиной с v0, положим v1  V T , {v0, v1}  E T и L(v1) =1. Вершина v2 смежна c v0 , положим v2  V T , {v0, v2}  E T и L(v2) =1. Вершина v3 смежна c v0 , положим v3  V T , {v0, v3}  E T и L(v3) =1. Получаем дерево

Пример (продолжение). Рассмотрим вершины v, что L(v) = 1. Начнем с v1, находим неиспользованные вершины, смежные с v1. Вершина v5 смежна c v1 , положим v5  V T , {v1, v5}  E T и L(v5) =2. Больше нет неиспользованных и смежных с v1 вершин, переходим к v2. Вершина v4 смежна c v2 , положим v4  V T , {v2, v4}  E T и L(v4) =2. Все вершины использованы, процесс завершен. Имеем дерево

Пример. Граф Выберем вершину v0 как начальную. Тогда L(v0) =0 и v0  V T. v1, v2, v3, v4, v5 являются смежными с v0, положим vi  V T , {v0, vi}  E T и L(v1) =1, где 1  i  5. Получим дерево

Пример (продолжение). Начинаем на уровне 1 с вершины v1. На этом уровне: вершина v6 смежная с v0, вершина v10 смежная с v3, т.д. v6, v10, v11, v14, v15, v18  V T, L(v6) = L(v10) = L(v11) = L(v14) = L(v15) = L(v18) = 2 {v1, v6}, {v3, v10}, {v4, v11}, {v4, v14}, {v5, v15} {v5, v18}  E T . Получим дерево

Пример (продолжение). Теперь на уровне 2 . На этом уровне: вершины v7, v8, v9 смежные с v6, v12, смежная с v11, v13, смежная с v14, v16, смежная с v15, v17, смежная с v18. v7, v8, v9, v12, v16, v17  V T, L(v7) = L(v8) = L(v9) = L(v12) = L(v13) = L(v16) = L(v17) = 3 {v6, v7}, {v6, v8}, {v6, v9}, {v11, v12}, {v14, v13}, {v16, v13} , {v17, v18}  E T . Получим дерево

Обратное дерево. При поиске в ширину вначале отыскиваются все вершины, смежные с заданной вершиной. Потом осуществляется переход на следующий уровень. Главная цель при поиске в ширину - построение дерева как можно более длинного пути. Когда путь заходит в тупик и формирует лист, необходимо возвращаться к родителю листа и пытаться формировать другой путь. Возврат к родителю происходит после попытки построить все возможные пути от сына этого родителя. Т.е. пытаемся достичь самый большой уровень, какой возможен. Алгоритм начинается у заданной вершины графа, которую считают корнем. Выбирают вершину, смежную с корнем, формируют ребро дерева. Затем выбирают вершину, смежную с ранее выбранной вершиной и формируют новое ребро. Необходимо помечать использованные вершины.

Обратное дерево. Если, находясь в вершине v, выбираем другую вершину w и обнаруживается, что вершина w уже была добавлена в дерево, то ребро {v, w} между этими вершинами не может быть добавлено в дерево. Такое дерево называют обратным ребром. Чтобы объявить ребро обратным, необходимо проверить, не является ли вершина w родителем вершины v, т.к. ребро {v, w} уже присутствует в дереве. При выборе w следует избегать случая, когда вершина w является родителем v. Если {v, w} - обратное ребро, то остаемся в v и выбираем новую смежную вершину, если это возможно. Любое ребро графа – либо ребро дерева, либо обратное ребро.

В алгоритме множество ребер дерева называют ребра дерева, множество обратных ребер – обратные ребра. “исп.” – использованные вершины, “нов.” – новые вершины.

Пример. Граф Произвольно выбирают вершину а в качестве корня. Меняем метку а с “нов.” на “исп.” Вершина b смежна с а и имеет метку “нов.”, добавляем ребро {a, b} в ребра дерева и меняем метку вершины b на “исп.”

Пример (продолжение). От вершины b переходим к вершине d, т.к. она является смежной с b. Вершина d имеет метку “нов.”, поэтому добавляем ребро {b, d} в ребра дерева и меняем метку вершины d на “исп.”

Пример (продолжение). Выбираем вершину, смежную с вершиной d. (a, f или g) Вершина d (поиск в глубину не единственный) Следующей g (имеет метку “нов.”) Добавляем ребро {d, g} в ребра дерева и меняем метку вершины g на “ исп.”

Пример (продолжение). Из вершины g выбираем вершину f, т.к. она является смежной с g. Вершина f имеет метку “нов.”, поэтому добавляем ребро {g, f} в ребра дерева и меняем метку вершины f на “исп.”

Пример (продолжение). Из вершины f выбираем вершину d, т.к. она является смежной с f. Однако вершина d уже имеет метку “исп.”, поэтому добавляем ребро {d, f} в обратные ребра дерева

Пример (продолжение). Больше нет ребер для проверки смежности с вершиной f, кроме родителя, возвращаемся к вершине g. Иных ребер для проверки на смежность с вершиной g тоже нет, потому возвращаемся к вершине d. Единственной вершиной для проверки является вершина а, но а уже имеет метку “исп.”, поэтому ребро {d, f} добавляем в обратные ребра и возвращаемся в вершину b

Пример (продолжение). Ребер для проверки на смежность с вершиной b больше нет, возвращаемся к вершине а. Выбираем с или e. Предположим, выбираем с (имеет метку “нов.”). Добавляем ребро {a,c} в ребра дерева и меняем метку вершины с на “исп.”

Пример (продолжение). Вершина h смежна с вершиной e . Добавляем ребро {e, h} в ребра дерева и меняем метку e на “исп.”

Пример (продолжение). Больше нет вершин для поверки из вершины h, возвращаемся в вершину e. Больше нет вершин для проверки из вершины e, возвращаемся в вершину с. Больше нет вершин для проверки из вершины с, возвращаемся в вершину а. Других вершин для проверки из вершины а тоже нет. Процесс завершен.

Пример. Найти остовное дерево

Пример (продолжение).

Определение. Лес остовных деревьев называется остовным лесом. Для построения остовного дерева следует выбрать вершину для корня первого дерева и построить остовное дерево.

Теорема (для построения остовного дерева в глубину). Если Т – глубинное остовное дерево графа G(V, E) и {a, b } – ребро графа G(V, E) , то либо а является потомком b, либо b является потомком a. Доказательство: Если {a, b } – ребро дерева Т, то вывод очевиден. Если не так, то одна из вершин (a) должна быть помещена в дерево первой. Но вершина b не была помещена в дерево на шаге 4 алгоритма ПОДГ, то поиск продолжается из вершины а до тех пор, пока не будет найдена вершина b. Поэтому вершина b является потомком а. Ч.т.д.

Теорема. Пусть Т – глубинное остовное дерево графа G(V, E). Вершина a  V является точкой сочленения графа G(V, E) тогда и только тогда, когда вершина а (1) либо является корнем дерева Т и имеет более одного сына, либо (2) вершина а не является корнем дерева Т, и существует такой сын с, что между с, или одним из его потомков, и собственным предком вершины а не существует обратного ребра.

ОР – обратное ребро ЗС – значение счета (с является n-ой вершиной)

Пример. Граф дерево

Теорема (Формула Кэли для дерева). Число остовных деревьев для n размеченных вершин равно nn-2

Алгоритм преобразования остовного дерева в последовательность.

Пример. Т - дерево

Пример (продолжение).

Пример (!). Дерево Т. v2 – лист с наименьшим индексом. Удаляем ребро {v2, v9} и полагаем а1 = 9. В оставшимся дереве v3 – лист с наименьшим индексом, удаляем ребро {v3, v8} и полагаем а2 = 8.

Пример (продолжение). Вершина v4 стала листом с наименьшим индексом, удаляем ребро {v4, v10} и полагаем а3 = 10. Вершина v5 стала листом с наименьшим индексом, удаляем ребро {v5, v10} и полагаем а4 = 10. Вершина v6 стала листом с наименьшим индексом, удаляем ребро {v6, v1} и полагаем а5 = 1.

Пример (продолжение). В оставшемся дереве вершина v7 стала листом с наименьшим индексом, удаляем ребро {v7, v8} и полагаем а6 = 8. Вершина v8 стала листом с наименьшим индексом, удаляем ребро {v8, v9} и полагаем а7 = 9. Оставшаяся вершина v9 стала листом с наименьшим индексом, удаляем ребро {v9, v1} и полагаем а8 = 1. Осталось ребро (справа) Последовательность имеет вид 9, 8, 10, 10, 1, 8, 9, 1

Алгоритм перевода последовательности в дерево.

Пример. Задана последовательность 1, 4, 1, 6, 6, 4 Восстановить дерево. 1, 4, 6 появляются в последовательности дважды, deg(v1) = deg(v4) = deg(v6) = 3. 2, 3, 5 не встречаются вообще, deg(v2) = deg(v3) = deg(v5) = deg(v7) = deg(v8) = 1. Запишем с их помощью восьмерки из чисел (3, 1, 1, 3, 1, 3, 1, 1), которую называют восьмеркой степеней. Считаем а1 = 1, v2 среди всех восьми вершин степени 1 имеет наименьший индекс, создаем ребро {v1, v2} (рис. слева). Положим deg(v1) = 2 и deg(v2) = 0, поэтому восьмерка степеней имеет вид (2, 0, 1, 3, 1, 3, 1, 1).

Пример (продолжение). Далее считаем а2 = 4, т.к. v3 среди всех вершин степени 1 имеет наименьший индекс, создаем ребро {v3, v4}. Получаем граф (посередине)

Пример (продолжение). Полагаем deg(v4) = 2 и deg(v3) = 0, восьмерка степени имеет вид ( 2, 0, 0, 2 1, 3, 1, 1) Теперь считаем а3 = 1, т.к. v5 среди всех вершин степени 1 имеет наименьший индекс, создаем ребро {v1, v5}. Получаем граф (слева)

Пример (продолжение). Полагаем deg(v1) = 1 и deg(v5) = 0, поэтому восьмерка степеней имеет вид (1, 0, 0, 2, 0, 3, 1, 1). Считаем а4 = 6, т.к. v1 среди всех вершин степени 1 имеет наименьший индекс, создаем ребро {v1, v6}. Получаем граф (слева)

Пример (продолжение). Полагаем deg(v1) = 1 и deg(v6) = 2, поэтому восьмерка степеней имеет вид (0, 0, 0, 2, 0, 2, 1, 1). Считаем а5 = 6, т.к. v7 среди всех вершин степени 1 имеет наименьший индекс, создаем ребро {v7, v6}. Получаем граф (посередине)

Пример (продолжение). Полагаем deg(v7) = 1 и deg(v6) = 1, поэтому восьмерка степеней имеет вид (0, 0, 0, 2, 0, 1, 0, 1). Считаем а6 = 4, т.к. v6 среди всех вершин степени 1 имеет наименьший индекс, создаем ребро {v4, v6}. Получаем граф (справа)

Пример (продолжение). Полагаем deg(v4) = 1 и deg(v6) = 0, поэтому восьмерка степеней имеет вид (0, 0, 0, 1, 0, 0, 0, 1). Все последовательности прочитаны и deg(v4) = deg(v8) = 1, формируем ребро {v4, v8}. Получаем искомое дерево

Определение. Пусть G – граф с n размеченными вершинами v1, v2, v3, …, vn. Матрицей степеней графа G называется n  n матрица D, определенная следующим образом: Dij = 0, если i  j, и Dii равно степени вершины vi .

Теорема (матричная формула Кирхгофа). Пусть G – граф с помеченными вершинами. Пусть K = D – A, где А – матрица смежности графа G, а D – матрица степеней графа G. Число остовных деревьев графа G равна любому из алгебраических дополнений матрицы K.

Пример. Найти количество остовных деревьев графа Поскольку deg(v1) = deg(v3) = 2 и deg(v2) = deg(v4) = 3,

Пример (продолжение). Матрица А имеет вид

Пример (продолжение). Алгебраическое дополнение K11 Следовательно, существует восемь остовных деревьев

!!