Page 303 - 6197

Рисунок Д3.8 – Дерево
Дерево, яке зображено на рис. Д3.8 має 7 вершин і 7-1=6
ребер.
Вершину V називають коренем дерева. Дерево, в якому
0
визначений його корінь називають кореневим деревом.
Вершини дерева степені 1 називаються листям. Інші
вершини дерева носять назву внутрішніх вершин.
Якщо вибраний корінь дерева, то рівень вершини V
визначається довжиною єдиного шляху із кореня у вершину
V . Для дерева, яке зображено на рис. 2.8, рівень вершини V
1
дорівнює 1, а рівень вершини V дорівнює 2.
3
Висота дерева визначається найбільшою довжиною його
шляху, який починається у вершиніV і закінчується його
0
листом. Висота дерева, яке зображено на рис. Д3.8, дорівнює
2. Якщо найбільша із степний вершин дерева має значення m ,
тоді дерево називається m -арним деревом. У тому випадку,
коли m  1 2 , дерево називається бінарним. Дерево, що
зображене на рис. Д3.8 – бінарне дерево.
Д3.2 Матричне подання графів
Для машинного подання графів використовують матриці
інцидентності та суміжності.
Нехай заданий орієнтований граф G . Тоді елементи
матриці інцидентності B визначають так:
 1 якщо i  та вершина інцидентна j  тому ребру,
b   (Д3.1)
ij
 0 в інших випадках.

303