Деревья на множестве вершин

Пусть множество v содержит р вершин, которые пронумерованы v1,… vр. Связав эти вершины (р-1) ребрами так, чтобы отсутствовали циклы, получим некоторое дерево, покрывающее данное множество р вершин. При р=2 такое дерево единственное и состоит из одной ветви. С увеличением р число различных деревьев tp быстро возрастает

tpр-2

многие из них являются изоморфными, т.е. отличаются только нумерацией вершин. Так при р=0 имеем 108 различных деревьев, из которых 106 неизоморфны.

На рис. показаны 16 различных деревьев, которые можно построить на множестве четырех вершин.

Деревья на множестве вершин - student2.ru

Символ дерева

Любому дереву Т можно поставить во взаимно-однозначное соответствие некоторый символ — упорядоченную последовательность (р-2) номеров вершин a(Т)=(a1,a2,… aр-2), среди которых могут быть повторяющиеся, причем a1,a2,… aр-2În.

Эта последовательность для данного дерева образуется следующим образом.

Вводится последовательность Np=(1,2,…р), далее выбирается концевая вершина с наименьшим номером и записывается номер a,связанной с ней вершиной, а сама концевая вершина удаляется из последовательности Np=(1,2,…р). Затем этот процесс повторяется до тех пор, пока не получим последовательность a(Т)=(a1,a2,… aр-2). Каждый такой шаг соответствует удалению из дерева концевой вершины с наименьшим номером и связанного с ней концевого ребра, причем (р-2) шагов от дерева остается единственное ребро, положение которого определяется парой номеров вершин, остав­шихся в последовательности Np. Построение дерева по его символу выполняется последовательным восстановлением концевых вершин и ребер.

На первом шаге из последовательности Np=(1,2,…р) выбирается наименьший номер amin, который отсутствует в a(Т)=(a1,a2,… aр-2) и строится ребро (amin,a1). Далее удаляется номер amin из Np и номер a1 из a(Т) и процесс продолжается до исчерпывания символа a(Т). оставшаяся в последовательности Np пара вершин определяет последнее ребро дерева.

Например, исходя из символа a(Т2)=(1,3,1,1,3) дерева Т2

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru .

Деревья на множестве вершин - student2.ru

последовательность N7=(1,2,3,4,5,6,7) на первом шаге имеем ребро (2,1). Удаляя ''2'' из N7 и ''1'' из a(Т2), получаем последовательность

Деревья на множестве вершин - student2.ru

На втором шаге получаем ребро (4,3) и далее аналогично ребра (5,1),(6,1),(1,3),(3,7). Совокупность всех полученных ребер и обра­зует соответствующее дерево.

Произвольное дерево на множестве р вершин можно рассмат­ривать как одно из покрывающих деревьев графа.

Деревья на множестве вершин - student2.ru

Рис. Дерево полного графа.

Экстремальное дерево.

В ряде практических задач требуется связать р пунктов наибо­лее экономичным способом с линиями связи р пунктов, автомобиль­ными дорогами таким образом, чтобы суммарная длина была наи­меньшей.

На языке теории графов эта задача формулируется в общем виде следующим образом.

Каждому ребру (ni,nj) полного графа с р вершинами приписыва­ется вес mij, выражающий численно расстояние, стоимость и другую величину, характеризующую любую пару вершин.

Требуется построить экстремальное дерево, связывающее все вершины так, чтобы был минимальным суммарный вес mi ветвей дерева

Деревья на множестве вершин - student2.ru .

Перебор вариантов при р³9 больше 106. Существует алгоритм Прима, который основан на последовательном введении выбора ре­бер с наименьшим весом. Затем на каждом следующем шаге выби­рается min по весу ребро и, если оно не образует цикла с ранее вы­бранными ветвями, вводится в дерево. Построение заканчивается после отбора дерева (р-1) ребер. Если имеются ребра с одинаковым весом, то решение может быть единственным в том случае, когда не все такие ребра входят в дерево, а отдается определенный приоритет отдельным.

Построение экстремального дерева с максимальным суммар­ным весом аналогично, необходимо лишь последовательно выбирать для него ребра наибольшего веса.

Деревья графа.

Будем называть деревом связного графа любое покрывающее дерево, связывающее все его вершины и имеющее в качестве ветвей ребра этого графа.

Два дерева считаются различными, если они отличаются хотя бы одним ребром.

Существует простой способ определения количества различных деревьев графа без петель (мультиграфа) с р вершинами. Для этого необходимо записать квадратичную матрицу р-го порядка, по глав­ной диагонали которой расположена степень вершин, а ij-и ji-элементы равны взятому со знаком ''-'' числу ребер, связывающих вершины i и j.

Вычисляя любой из главных минора этой матрицы, получим исходное число деревьев.

Например, для графа имеем дерево (одно из 7в).

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

D22 — один из главных миноров этой матрицы.

Это теорема Трента.

Типы конечных графов.

Число ребер, связанных с вершиной ni (петля учитывается два­жды), называется степенью вершины и обозначается deg(ni).

Деревья на множестве вершин - student2.ru

deg(n2)=4

deg(n5)=0

Степень изилирования вершины равна 0. Легко показать, что в любом графе сумма степеней всех вершин равна удвоенному числу ребер, а число вершин нечетной степени всегда четно.

В орграфе различают положительные d +(ni) и отрицательные d -(ni) степени вершин, которые равны соответственно числу исходящих из ni и заходящих в ni дуг.

Очевидно, что суммы положительных…………………………….

Примеры и задачи.

1. Даны два множества Х={x1,x2,x3,x4,x5,x6} Y={y1,y2,y3,y4}

и определено бинарное отношение А={(x1,y2),(x2,y1),(x2,y2),(x4,y2), (x4,y3),(x5,y1),(x5,y3)}.

Для данного отношения А:

а) записать область определения и область значений;

б) определить сечения по каждому элементу из Х;

в) определить сечения по подмножествам Х'={x1,x4} и Х''={x2,x3,x5} множества Х;

г) записать матрицу и нарисовать граф;

д) определить симметричное отношение А-1.

2. Пусть Х — множество студентов; Y — множество дисциплин и соотношение хАу, где хÎХ и уÎY, означает ''студент х изучает дис­циплину у''. Дать словесное описание областей определения и значе­ний, сечений и обратного отношения, полученных в задаче №1.

3. По результатам задачи определите множества А(х2) Ç А(х4), А(х2)\ А(х4) и А(х2)+А(х4). Дайте им словесное описание согласно условия задачи №2.

Задача. Представьте бинарные отношения, заданные графом как множество упорядоченных пар и запишите его матрицу.

Деревья на множестве вершин - student2.ru

Задача. Записать композицию С=ВА отношений А={(1,2),(1,3), (2,1),(2,4),(3,3)} и В={(1,1),(1,3), (2,2),(3,1),(4,2),(4,3)}. Проверить результат с помощью операций над матрицами и графами заданных отношений.

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

Тождества теории множеств

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru Æ=A

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru Æ

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru Æ=Æ

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

Деревья на множестве вершин - student2.ru

Наши рекомендации