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

Пусть множество 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

Æ

Æ=Æ