загрузка...
загрузка...
На головну

Дерева і деревовидних

  1. Алгоритми роботи з двійковими впорядкованими деревами (деревами пошуку)
  2. Графи, мережі, дерева
  3. дерева
  4. дерева
  5. дерева
  6. Дерева і їх властивості

Окремим випадком зв'язкових мереж є дерева.

Ліс - неорієнтований граф без циклів. Компонентами зв'язності лісу є дерева.

дерево G1 мережі G, Це зв'язний підграф G, Який не містить циклів.

Подграф є деревом, якщо виконані будь-які два з трьох наступних умов:

1. Подграф зв'язний.

2. Подграф ациклический.

3. Число дуг подграфа менше числа його вершин на одиницю.

Для будь-яких двох вузлів дерева існує єдиний шлях між ними. Остовним деревом (кістяком) мережі називають дерево, що містить всі вузли вихідної мережі. Таким чином, Go = {N, Ao} - Кістяк G = {N, A}, якщо Aoc A и Go - Дерево.

Вагою дерева в мережі, для дуг якої визначена узагальнена вартість cij, Називають суму сij по всіх дуг дерева.

Найкоротшим остовом називають остов з найменшим для всіх кістяків даної мережі вагою.

Максимальним остовом називають остов з найбільшим для всіх кістяків даної мережі вагою.

Деревовидних називають дерево, що складається тільки з орієнтованих дуг і має єдиний корінь - вузол, з якого дуги тільки виходять.

Деревоподібне дерево - дерево, що є деревоподібна.

Каскадний остов, який є деревоподібна.

 
 

 Приклади дерева, остова, деревоподібна, деревовидного остова наведені на рис. 5.

Алгоритм визначення остовного дерева для довільного зв'язного псевдографом G = (V, X)

Крок 1. вибираємо в G довільну вершину u1, Яка утворює підграф G1 псевдографом G, Що є деревом. вважаємо i = 1.

крок 2. якщо i = n, де n = n (G), То задача вирішена, і Gi - Шукане кістяк псевдографом G. В іншому випадку переходимо до кроку 3.

крок 3. Нехай вже побудовано дерево Gi, Що є подграфом псевдографом G і містить деякі вершини u1, ..., Ui, де 1 <n-1. будуємо граф Gi + 1, Додаючи до графу Gi нову вершину ui + 1, Суміжну в G з деякою вершиною uj графа Gi, І нове ребро (ui + 1, uj) (В силу зв'язності G і тієї обставини, що i , Зазначена вершина ui + 1 обов'язково знайдеться). Відповідно до твердження граф Gi + 1 також є деревом. Надаємо i: = i + 1 і переходимо до кроку 2.



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   Наступна

Вступ | Перелік використовуваних надалі позначень | визначення | Орієнтовані і неорієнтовані мережі | Теорема про максимальний потік і мінімальному розрізі | Постановка задачі | Алгоритм рішення (алгоритм Дейкстри) | приклад рішення | Приклади економічних задач, що зводяться до задачі про найкоротшою ланцюга | Алгоритм рішення (алгоритм Літтла) |

загрузка...
© um.co.ua - учбові матеріали та реферати