Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ЛЕКЦИЯ 8.
Деревья.
Ациклический граф называется деревом, если k=1. При k>1 такой граф называется лес. Количество деревьев в лесе равно его k. Дерево не имеет кратных ребер и петель.
Количество деревьев, построенных на n вершинах, равно nn-2.
Любое дерево однозначно определяется его расстоянием – длиной наименьшей цепи - между концевыми вершинами.
Для любого графа определяется понятие остовного дерева (остова) – суграф данного графа, являющийся деревом. Количество остовов дерева можно вычислить через измененную матрицу смежности: 1) изменяем у всех элементов знаки на противоположные; 2) главную диагональ заменяем на степени соответствующих вершин; 3) вычисляем алгебраические дополнения главной диагонали (у всех элементов они равны), значение которых и есть количество остовов.
Теорема о свойствах дерева: G=(V,E) - дерево, если:
Длина максимальной ветки дерева называется его высотой (h).
Расстояние от корня до вершины - уровень вершины (ребра).
Вершины одного уровня – ярус дерева.
Висячие вершины (ребра) имеют I уровень.
Вершина(-ы) максимального уровня называются центром (-ами) дерева.
Если в дереве 1 центр, то оно центрально, если 2 центра, то бицентрально.
Цепи, проходящие через центр(ы), называются диаметральными, а наибольшая из них – диаметр дерева.
Каждая вершина дерева имеет кортеж (последовательность натуральных чисел)- количество вершин соответствующей ветки.
Кортежи центров называются центральными.
Длина кортежа равна своему первому числу.
У изоморфных деревьев центральные кортежи совпадают.
Ордеревья
Если в дереве одну из вершин выбрать корневой, и все ребра направить к корню или от корня, то получим ордерево.
Свойства ордерева:
Если все ребра ордерева направлены к корню, то это сеть сборки.
Ордерево выровнено, если все висячие вершины располагаются на одном или двух последних уровнях. Для выровненного ордерева
Log2(|V|+1)-1h Log2(|V|+1)
Ордерево упорядочено, если: 1). У него единственный корень v0; 2). Множество V\v0 разбивается на попарно непересекающиеся множества, на которых определяются поддеревья.
Пример: корневой каталог диска.
Дерево бинарное, если у корневого дерева s(v0)=2, и дерево состоит из двух бинарных поддеревьев.
Бинарное дерево не является упорядоченным.
Обобщением ордерева является понятие сети.
Сеть задается парой C(V,ε), где V- множество вершин, ε = {Е0, Е1, Е2,…}– семейство наборов дуг. В наборах Еi (i=0,1,2,3,…) элементы могут повторяться.
Е0 – множество полюсов, Еi (i=,1,2,3,…) – множества дуг.
Если каждый из наборов Еi (i=,1,2,3,…) содержит ровно 2 элемента, то сеть есть граф с выделенными полюсами.
Сеть, дуги которой нагружены пропускной способностью, называется транспортной сетью.