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

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

t_p=р^р-2

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

deg(n₂)=4

deg(n₅)=0

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

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

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

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

1. Даны два множества Х={x₁,x₂,x₃,x₄,x₅,x₆} Y={y₁,y₂,y₃,y₄}

и определено бинарное отношение А={(x₁,y₂),(x₂,y₁),(x₂,y₂),(x₄,y₂), (x₄,y₃),(x₅,y₁),(x₅,y₃)}.

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

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

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

в) определить сечения по подмножествам Х'={x₁,x₄} и Х''={x₂,x₃,x₅} множества Х;

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

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

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

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

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

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

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

Æ=A

Æ

Æ=Æ