Дерево свойства дискретная математика

§3 Деревья и их свойства.

Т.1(о весячей вершине)/ во всяком конечном дереве с числом вершин n>1 существует висячая вершина.

Найдется вершина v степени

Возьмем произвольную вершину дерева

Случай 2: v –не висячая к этой вершине будет смежная с вершиннойv. т.е. vv ` не

т.к. граф цикла не имеет то каждый раз происходит переход в новую нерассматриваемую вершину т.к. граф конечен то и просмотр вершин конечен то рано или поздно попадет висячая вершина.

Двигаясь от вершины v в обратном направлении находим хотя бы еще одну висячую вершину.

Т.2/ для (n,m) графа следующ утверждения эквивалентны:

1. G-дерево
2. G – связный граф и m=n-1
3. G – ациклический граф и m=n-1
4. любые два несовпадающие вершины графа G соединят единственная простая цепь.
5. G- ациклический граф обладающий некоторыми свойствами что если любые две не смежные вершины соеденить ребром то получ граф имеет ровно один цикл.

Док –во: 1 2 док во от противного дано: G- дерево док-ть: m=n-1 воспользуемся теоремой о висячей вершине пусть висячей вершиной является вершина v будем выполнять просмотр дерева начиная с висячей вершины v , при просмотре добовляем каждый раз одно ребро и одну вершину т.к. циклов нет вершины каждый раз разные выполнив просмотр всего дерева получаем чтд 2 3 дано G – связен m=n-1 док-ть: G – не имеет циклов док-во: случай первый kКол-во ребер кол-во вершин граф имеет к=1 связный компонент т.е. связен чтд 4 5 дано: граф G, две вершины. доказать: если любые две не смежные вершины соеденить ребром то получ граф имеет ровно один цикл. док-во: пусть граф G имеет цикл => найдется две вершины соеденяемые по меньшей мере двумя простыми цепями это противоречит условию => циклов в графе нету соеденим вершины u и v ребром по условию они соеденены цепью => получим цикл не трудно видеть этот цикл будет единственным т.к. убрав ребро мы получили бы что в графе еще есть ребра но граф ациклический. 5  дано: G- ациклич если любые 2 не смежные вершины соединить ребром то получается равно 1 цикл док-ть: G-дерево т.е. требуется док-ть связность графа k>1 возьмем две вершины и соеденим их ребром но не получим цикла чтд Остов графа G=(V,E) пусть Н – суграф графа G суграф Н называют остовым графом G если на каждом связном компоненте порождается дерево В случае связного графа G остов называют каркасом покрывающим деревом или стягивающим графом G=(V,E) – это (n,m) – граф Т.(о циклическом ранге)/ Число ребер которые необходимо удалить в произвольном графе G для получения остова не зависит от последовательности их удаления и равно гдеk – число связанных компонентов. (m- число ребер n- число вершин) Док – во: а) G – связен тогда k=1 тогда остов есть дерево которое будет содержать n вершин и n-1 ребер тогда m-(n-1)= m-n+1= б) G – не связен имеет k>1 связных компонетов => m_i – кол-во ребер в i связный компоненте n_i – кол-во вершин =>чтд. Свойство дерева

1. Циклический ранг любого дерева равен нулю. Число — циклич ранг или цикломатическое число.

Т.(о центре дерева)/ Центр любого дерева состоит из одной вершины или двух смежных вершин Док-во: G=(V,E) – это (n,n-1) – граф(дерево) Случай 1 n=1 ●- это граф вершина. центр состоит из одной вершины теорема выполняется Случай 2 n=2 —это граф звено в этом случае центр состоит из двух вершин Случай 3 n>2 По теореме о висячей вершине в дереве есть хотя бы одна висячая вершина. Удалим в дереве все висячие вершины вместе с инцидентными ребрами. Не трудно видеть что в полученном дереве эксцентриситеты оставшихся вершин уменьшается на единицу. И соотношение между эксцентриситетами сохранится. Центр останется таким же как в исходном графе. Процесс удаления всяческих вершин пока не останется одна вершина или две вершины соединенные ребром тогда все сводится к первому или второму случаю. Т.е. центр состоит из одной вершины или двух смежных. Чтд Т.(Кэли)/ Число помеченных деревьев порядка n равно ( Кэли для доказательства использовал отобрадение функций) (Кергоф при док-ве этой теоремы использовал последовательности для чисел от 1 до n из множества причем числа могли повторятся.) Док- во: Подсчитаем число различных таких последовательностей. n – способов поставить на первое место любое число столькоже на второе и тд Док – во Прюфера: Далее доказывается взаимнооднозначное соответствие м/у последовательностями указанного вида и помеченными деревьями. Имеется дерево Т пометим его вершины от 1 до n Выберем в дереве вершину с наименьшим номером пусть это b₁ с ней смежная некоторая вершина а₁ Возьмем ребро e₁=b₁a₁ и рассмотрим дерево Т-e₁ полученное дерево обозначим Т₁ В этом дереве проделываем ту же процедуру выбор вершины с наименьшим номером и т д продолжая процедуру получим: — две вершины соединенных ребром выпишем: Каждому дереву (помеченному) соответствует единственная числовая последовательность построенная таким образом для каждой последn-2 соответствует единичное дерево. Чтд Ориентированное дерево. А— предок B…K – потомки вершины А С,В – непосредственный потомок вершины А(сын) D,E,F – сын для В В – непосредственный предок F для К непосредственный отец О./ Ориентированный деревом называется симметрический орентированный граф G(V,E) В катором одна вершина не имеет предков а все остальные вершины имеют только по одному непосредственному предку. Вершиныназывается корнем дерева Бинарным деревом называется ордерево в котором каждая вершина имеет не более двух непосредственных потомков. Полным бинарным деровом называется бинарн дерево в котором каждая вершина не является листом(лист-висячая вершина дерева) имеет ровно два непосредственных потомка. Взвешенный граф В реальный задачах часто приходится использовать дополнительную информацию (стоимость проезда расстояние между объектами электроники и т д ) это (n,m)-граф Взвешанным графом назыв пару (G,W) где G-граф а W-функция которая каждому ребру ставит в соотношение число— называемое весом ребрагде Весом графа называют суммарный вес его ребер Рассмотрим связный неор граф остов лин веса тогда, остовом является суграф являющийся деревом Для данного взвешенного графа нужно найти остов минимального веса что: Применяется для проектирование дорог создание электроники.

1. Выберем — ребро минимального строим дерево Т₁(2 вершины a и bи ребро)
2. На некотором шаге имеем дерева Т_k (имеем k+1 вершин) если k+1k а другой не принадлежит Т_k выбирается ребро наименьшего веса, если же k+1=n то остов по строению.

i		ei	W(ei)
1		2.5	1
2		2.1	1
3		5.3	1
4		1.4	2
5		2.7	3
6		4.6	9
Ростов=17

Источник

Введение в деревья

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

Дерево и его свойства

Определение – Дерево – это связный ациклический неориентированный граф. Между каждой парой вершин в G существует уникальный путь. Дерево с N числом вершин содержит ( N − 1 ) число ребер. Вершина, которая имеет 0 градусов, называется корнем дерева. Вершина, имеющая 1 градус, называется листовым узлом дерева, а степень внутреннего узла составляет не менее 2.

Пример . Ниже приведен пример дерева.

Центры и Би-Центры Дерева

Центр дерева – это вершина с минимальным эксцентриситетом. Эксцентриситет вершины X в дереве G – это максимальное расстояние между вершиной X и любой другой вершиной дерева. Максимальный эксцентриситет – диаметр дерева. Если у дерева есть только один центр, оно называется Центральным деревом, а если у дерева есть только несколько центров, оно называется Би-центральным деревом. Каждое дерево является либо центральным, либо двухцентральным.

Алгоритм нахождения центров и бицентров дерева

Шаг 1 – Удалите все вершины степени 1 из данного дерева, а также удалите их падающие ребра.

Шаг 2 – Повторяйте шаг 1, пока не останется одна вершина или две вершины, соединенные ребром. Если осталась одна вершина, то это центр дерева, а если осталось две вершины, соединенные ребром, то это бицентр дерева.

Узнайте центр / би-центр следующего дерева –

Сначала мы удалим все вершины степени 1, а также удалим их падающие ребра и получим следующее дерево:

Опять же, мы удалим все вершины степени 1, а также удалим их инцидентные ребра и получим следующее дерево:

Наконец, мы получили одну вершину «c» и остановили алгоритм. Поскольку существует единственная вершина, у этого дерева есть один центр ‘c’, и дерево является центральным деревом.

Узнайте центр / би-центр следующего дерева –

Сначала мы удалим все вершины степени 1, а также удалим их падающие ребра и получим следующее дерево:

Опять же, мы удалим все вершины степени 1, а также удалим их инцидентные ребра и получим следующее дерево:

Наконец, у нас осталось две вершины «c» и «d», поэтому мы останавливаем алгоритм. Поскольку оставлены две вершины, соединенные ребром, это дерево имеет двухцентровый «cd», а дерево является двухцентровым.

Маркированные деревья

Определение – помеченное дерево – это дерево, вершинам которого присваиваются уникальные номера от 1 до n. Мы можем посчитать такие деревья для малых значений n вручную, чтобы предположить общую формулу. Число помеченных деревьев из n вершин равно n n − 2 . Два помеченных дерева изоморфны, если их графы изоморфны и соответствующие точки двух деревьев имеют одинаковые метки.

пример

Немеченые деревья

Определение – немеченое дерево – это дерево, вершинам которого не назначены никакие числа. Число помеченных деревьев с числом вершин n равно $ \ frac <(N + 1)! N! >$ (n- е каталонское число)

пример

Укорененное дерево

Корневое дерево G – это связный ациклический граф со специальным узлом, который называется корнем дерева, и каждое ребро прямо или косвенно происходит от корня. Упорядоченное корневое дерево – это корневое дерево, в котором упорядочены дочерние элементы каждой внутренней вершины. Если каждая внутренняя вершина корневого дерева имеет не более m дочерних элементов, она называется m-арным деревом. Если каждая внутренняя вершина корневого дерева имеет ровно m детей, она называется полным m-арным деревом. Если m = 2 , корневое дерево называется бинарным деревом.

Двоичное дерево поиска

Двоичное дерево поиска – это двоичное дерево, которое удовлетворяет следующему свойству:

• X в левом поддереве вершины V , V a l u e ( X ) l e V a l u e ( V )
• Y в правом поддереве вершины V , V a l u e ( Y ) g e V a l u e ( V )

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

Источник