оналіті raquo ;, превратилась у гіпотезу трьох фарб .
. 9 Дерева и ліс
Визначення. Неорієнтованім деревом (або просто деревом) назівається неорієнтованій зв'язного граф без ціклів, отже без петель и кратних ребер, что має НЕ Менш двох вершин.
Дерево є мінімальнім зв язнім графом у тому розумінні, что відалення хоча б одного ребра приводити до того, что граф віявляється незва язнім.
Приклад. Чі є графи, зображені на рис. 5.25, (а), (б) деревами?
Малюнок 5.25 - Графи
розв язання:
Граф на рис. 5.25 (а) є деревом, тому что ВІН зв'язного и не містіть ціклів. Граф на рис. 5.25 (б) є деревом, тому что містіть цикл.
Дамо без доведення ряд теорем, корисних для Вивчення дерев.
Теорема. Будь-яке дерево з вершинами містіть ребро.
Теорема. Нехай - граф, что містіть более однієї вершини. Відаляючі его ребра можна здобудуть дерево тоді и только тоді, коли ВІН зв'язного.
Визначення. Лісом назівається незва язній неорієнтованій граф без ціклів. Зв язані компоненти лісу є дерева.
Приклад. На рис. 5.26 наведень приклад лісу, что містіть три дерева.
Малюнок 5.26 - Приклад лісу, что містіть три дерева
Добрі зрозумілім прикладом дерева є: будь-яке генеалогічне дерево; Організаційна структура будь-которого підприємства, организации.
Визначення. Орієнтованім деревом назівається вільний від петель орієнтований граф, співвіднесеній граф которого є деревом; того если існує шлях від вершини до вершини, то ВІН єдиний.
Помітімо, что если в орієнтованому дереві є ребро, то немає ребра, інакше шлях БУВ бі циклом.
Приклад. На рис. 5.27 наведено приклад орієнтованого дерева:
Малюнок 5.27 - Приклад орієнтованого дерева
Визначення. Вершини дерева степіня 1 назіваються листя, Інші вершини - внутрішнімі вершинами.
например, у дерева, збережений на рис. 6.49 (а), листя це вершини. Інші вершини є внутрішнімі.
Дерева визначаються такою властівістю: для будь-якіх двох вершин дерева шлях з вершини до вершини єдиний. І, навпаки, если для будь-якіх двох вершин графа існує єдиний шлях з вершини до вершини, тоді граф - дерево.
Припустиме, что дерево представляет собою Якийсь фізичний об'єкт, рухлівій у вершинах. Его можна підвісіті за шкірних з вершин. Так, например, если дерево, збережений на рис. 5.28 (а) підвісіті за вершину, або, то воно буде віглядаті, як показано на рис. 5.28 (а) або на рис. 5.28 (б).
Малюнок 5.28 - Приклад дерева
Звертаючись нами вершина назівається коренем дерева и розташовується в самій верхній его части. Для дерева на рис. 5.28 (а) коренем є вершина, а для дерева на рис. 5.28 (б) - вершина.
Визначення. Дерево, корінь которого визначеня, назівається Коренєва деревом.
Аналогічно візначається и орієнтоване Коренєва дерево. При цьом Варто пам'ятати, что всі его ребра орієнтуються від кореня.
При заміні Коренєва неорієнтованого дерева на Коренєва орієнтоване дерево, говорять, что є породженім Коренєва деревом.
Приклад. На рис. 5.29 (а) збережений неорієнтоване Коренєва дерево, а на рис. 5.29 (б) - породжене Їм орієнтоване Коренєва дерево.
Малюнок 5.29 - Неорієнтоване и породжене ним орієнтоване дерево
Если корінь дерева избран, то можна ввести ще ряд визначеня.
Визначення. Рівнем вершини назівається довжина єдиного шляху від кореня дерева до вершини.
Визначення. Висота дерева назівається довжина самого Довгого шляху від кореня дерева до листя.
Приклад. Для Коренєва дерева, збережений на Наступний малюнку, візначіті рівень вершини, висота дерева.
розв язання: Рівень вершини дорівнює двом; а висота дерева з коренем у вершіні дорівнює максимальному шляху від кореня до вершини - -дорівнює п'яти.
Для генеалогічніх дерев дамо ряд визначеня. Їх можна розповсюдіті на будь-які орієнтовані кореневі дерева.
Визначення. Если існує орієнтоване ребро з в, то вершина назівається батьком вершини, а вершина - сином (дочкою) вершини.
Визначення. Если є одночасно Батько і, то и назіваються братами (сестрами).
Визначенн...
