Лекция № 9. Древовидные графы.
Связный граф без циклов называется деревом.
Граф без циклов называется лесом.
Теорема. T(V,E) - дерево тогда и только тогда, когда T(V,E) - связный граф и |E|=|V| - 1.
Теорема. В любом дереве имеется не менее двух висячих вершин.
Деревом называется связный граф без циклов. Вот пример дерева:
 |
А вот пример графа, не являющегося деревом:
 |
Если граф 
является деревом и число его вершин равно p, то о числе его ребер можно сказать совершенно определенно: кличество ребер равно 
. В каждом дереве имеется еще одна особенность: любые две вершины в дереве связаны и притом единственной простой цепью. Оба эти обстоятельства имеют несложные доказательства.
Определение. Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.
Пример 86.
Граф G1 является деревом (рис.38). Граф G2 является лесом (рис. 38), он содержит три связные компоненты, каждая из которых является деревом.
Следующие утверждения эквивалентны:
· граф G есть дерево;
· граф G является связным и не имеет простых циклов;
· граф G является связным и число его ребер ровно на единицу меньше числа вершин;
· любые две различные вершины графа G можно соединить единственной (и притом простой) цепью;
· граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один (с точностью до направления обхода и начальной вершины обхода) и притом простой цикл (проходящий через добавляемое ребро).
Утверждение. Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина.
Утверждение. Пусть G – дерево. Тогда любая цепь в G будет простой.
|
|
Определение. Граф называется деревом, если он является связным и не имеет циклов.
Графы G1 и G2 на рис. 3.26 являются деревьями, а граф G3 – не дерево.
Рис. 3.26
Рис. 3.27
Утверждение 1. Любые две различные вершины дерева можно соединить единственной (и притом простой) цепью.
Утверждение 2. Число дуг дерева на единицу меньше числа его вершин.
Утверждение 3. Пусть G – дерево. Тогда любая цепь в G является простой.
Утверждение 4. Если какую-нибудь пару несмежных вершин дерева соединить дугой, то полученный граф будет содержать ровно одну цепь.
Определение. Граф, все компоненты связности которого являются деревьями, называется лесом.
Граф на рис. 3.27 является лесом, состоящим из двух деревьев.
Определение. Остовным деревом (остовом или каркасом) связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Замечание. Остовное дерево графа не единственно.
На рис. 3.28 изображен граф G и два его остовных дерева G1 и G2.
Рис. 3.28
Утверждение. Число дуг произвольного неорграфа G, которое надо удалить для получения остова, не зависит от последовательности их удаления и равно m – n + k,
где m – число дуг, n – число вершин, k – число компонент связности графа G.
Для графа рис. 3.28 m = 5, n = 4, k = 1. Следовательно, надо удалить из графа две дуги, чтобы получить остов. Остовами этого графа будут графы G 
и G 
.
Для графа G , изображенного на рис. 3.29, m =8, n = 7, k = 2. Следовательно, надо удалить из графа три дуги, чтобы получить остов. Это можно сделать так, чтобы получился граф G , который представляет собой лес из двух деревьев.
|
|
Рис. 3.29
Методы теории графов нашли широкое приложение в химии. Например, А. Келли определил количества химических изомеров углеводородов - C 
H 
. Структурные формулы молекул таких соединений (вершины – атомы, дуги – валентные связи) представляют собой деревья. Структурные формулы двух таких изомеров – бутана и изобутана приведены на рис.3.30.
Рис. 3.30
Важным для приложений классом ориентированных деревьев являются корневые, или растущие деревья, т.е. такие, у которых существует вершина, называемая корнем, из которой существуют простые пути во все остальные вершины дерева. Путь из корня в каждую вершину единственный. Вершины корневого дерева, отличные от корня и висячих вершин называются промежуточными.
Такие структуры принято использовать для организации хранения информации, в частности, таковыми являются компьютерные файловые системы. Корневое дерево файловой системы обычно называют деревом директорий, в котором корень – корневая директория, промежуточные вершины – поддиректории, а висячие вершины – отдельные файлы или пустые поддиректории.
На рис.3.31 изображено корневое дерево. Вершины дерева размещены по трем этажам. Корень дерева v размещен на первом этаже.
Рис. 3.31
При решении прикладных задач часто возникает необходимость обхода вершин дерева, связанная с поиском вершин, удовлетворяющих определенным свойствам. Обычно такой поиск осуществляют обходом по глубине или обходом по ширине.
При обходе дерева по глубине после очередной рассмотренной вершины выбирается смежная с ней вершина следующего этажа. Если очередная рассмотренная вершина висячая и ее достижение не дает желаемого решения задачи, то возвращаются до ближайшей вершины степени e 3 и просматривают вершины другого, еще не пройденного пути в таком же порядке и т.д. На рис.3.31 цифрами показан обход дерева по глубине.
|
|
При обходе дерева по ширине просмотр вершин дерева ведется по этажам. Переход к вершинам следующего этажа производится только после просмотра всех вершин дерева данного этажа.