Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет

информатики и радиоэлектроники»

РЕФЕРАТ

на тему:

 

«ДЕРЕВЬЯ И ИХ СВОЙСТВА (ЧАСТНЫЙ ВИД ГРАФОВ)»

 

Минск, 2008

Рассмотрим частный вид графов, широко используемых, например, в теории электрических цепей, химии, вычислительной технике и в информатике.

Определение 1. Деревом называется связный граф, не содержащий циклов. Любой (в том числе несвязный) граф без циклов называется ациклическим. Несвязный граф, каждая компонента связности которого является деревом, называется лесом. Можно сказать, что деревья являются компонентами леса. На рис.1 изображены два дерева G1, G2 и лес G3.

Рис.1

Сформулируем основные свойства деревьев. Сделаем это в виде совокупности утверждений, которые эквивалентны между собой (т.е. из любого утверждения следует любое другое) [].

Теорема 1. Пусть G(X, E) – неориентированный граф с p вершинами и q ребрами. Тогда следующие утверждения эквивалентны.

1 . G есть дерево.

2 . Любые две различные вершины x и y графа G соединены единственной простой цепью.

3 . G – связный граф, утрачивающий это свойство при удалении любого из его ребер.

4 . G – связный граф и p = q + 1.

5 . G – ациклический граф и p = q + 1.

6 . G – ациклический граф, причем если любые две его вершины x и y соединить ребром e, то в полученном графе будет ровно один простой цикл.

Для доказательства теоремы достаточно доказать следующую цепочку следствий: 1 Þ 2 Þ 3 Þ 4 Þ 5 Þ 6 Þ 1 , так как это означает, что из любого утверждения 1 – 6 выводится любое другое.

1 Þ2 . Так как граф связен, то любые две его вершины можно соединить простой цепью. Пусть m1 и m2 - две различные простые цепи, соединяющие вершины x и y. Если цепи m1 и m2 не имеют общих вершин, за исключением вершин x и y, то есть простой цикл. Предположим, что цепи m1 и m2 имеют общие вершины, отличные от x и y. Пусть z – первая из таких вершин при движении от вершины x к вершине y и пусть m1(x, z) и m2(x, z) – части цепей m1 и m2, взятые от вершины x до вершины z. Тогда  - простой цикл. Это противоречит тому, что граф ацикличен, и поэтому m1=m2, т.е. утверждение 2 доказано.

2 Þ3 . Граф G – связен, поскольку любые две его различные вершины x и y соединены простой цепью. Возьмем некоторое ребро графа e = (x, y). Согласно 2 простая цепь m={e} между вершинами x и y единственна. Если ребро e удалить, то вершины x и y будет невозможно соединить простой цепью, и полученный граф будет несвязным. Утверждение 3 доказано.

3 Þ4 . По условию 3 граф связен. Соотношение p = q + 1 докажем по индукции. Если граф имеет две вершины и удовлетворяет 3 , то он выглядит так:

В этом случае p = 2, q = 1 и соотношение p = q + 1 выполняется. Предположим теперь, что соотношение верно для всех графов, удовлетворяющих 3 и имеющих меньше, чем p вершин, и докажем его для графа G с p вершинами. Удалим из графа G произвольное ребро e. Тогда новый граф G´ будет несвязным и будет состоять из двух связных компонент G1 и G2. По предположению индукции имеем

p1 = q1 + 1, p2 = q2 + 1,

где pi – число вершин компоненты Gi, qi – число ее ребер. Следовательно,

p = p1 + p2, q = q1 + q2 + 1,

поэтому p = q1 + q2 + 2 = q + 1, и свойство 4 доказано.

4 Þ5 . ............