Ноу Інти, лекція, дерева

Доказ Нехай граф G = (V, E) задовольняє умовам визначення 10.2. Покажемо індукцією по числу вершин | V |. що.

Якщо | V | = 1. то єдина вершина є по властивості (1) коренем дерева, тобто в цьому графі ребер немає:. Тоді.

Припустимо, що всякий граф з <= n вершинами, удовлетворяющий определению 10.2 входит в . Пусть граф G=(V,E) с (n+1) -й вершиной удовлетворяет условиям определения 10.2. По условию (1) в нем имеется вершина - корень r0. Пусть из r0 выходит k ребер и они ведут в вершины r1. rk (k>= 1). Позначимо через Gi, (i = 1. K) граф. що включає вершини і з'єднують їх ребра. Легко зрозуміти, що Gi задовольняє умовам умов визначення 10.2. Дійсно, в ri не належать ребра, тобто ця вершина - корінь Gi. У кожну з інших вершин з Vi входить по одному ребру як і в G. Якщо, то вона досяжна з кореня ri за визначенням графа Gi. Так як | Vi | <= n. то по индуктивному предположению . Тогда граф G получен по индуктивному правилу (2) определения 10.3 из деревьев G1. Gk и поэтому принадлежит классу .

Якщо деякий граф G = (V, E) входить в клас, то виконання умов (1) - (3) визначення 10.2 для нього легко встановити індукцією по визначенню 10.2. Надаємо це читачеві як вправа.

З орієнтованими деревами пов'язана багата термінологія, яка прийшла з двох джерел: ботаніки і області сімейних відносин.

Корінь - це єдина вершина, до якої не входять ребра, листя - це вершини, з яких не виходять ребра. Шлях з кореня в лист називається гілкою дерева. Висота дерева - це максимальна з довжин його гілок. Глибина вершини - це довжина шляху з кореня в цю вершину. Для вершини, підграф дерева T = (V, E). що включає всі досяжні з v вершини і з'єднують їх ребра з E. утворює поддерево Tv дерева T з коренем v (див. задачу 10.3). Висота вершини v - це висота дерева Tv. Граф, який є об'єднанням декількох непересічних дерев, називається лісом.

Якщо з вершини v веде ребро в вершину w. то v називається батьком w. а w - сином v (останнім часом в ангоязичной літературі вживається асексульная пара термінів: батько - дитина). З визначення дерева безпосередньо випливає, що у кожної вершини крім кореня є єдиний батько. Якщо з вершини v веде шлях в вершину w. то v називається предком w. а w - нащадком v. Вершини, у яких загальний батько, називаються братами або сестрами.

Виділимо ще один клас графів, узагальнюючий орієнтовані дерева - орієнтовані ациклічні. Два види таких розмічених графів будуть використані далі для подання булевих функцій. У цих графів може бути кілька коренів - вершин, в які не входять ребра, і в кожну вершину може входити кілька ребер, а не одне, як у дерев.

Схожі статті