Деревья. Цепь, в которой начальная и конечная вершины совпадают, называется циклом

Циклы

Цепь, в которой начальная и конечная вершины совпадают, называется циклом. Для циклов вводится понятие циклонического числа z = q – р + k.

Если z = 0, то граф не имеет циклов. Если же z = 1, то граф имеет один цикл. Для мультиграфа z выражает число циклов.

Например: при р = 4, q = 8 и k = 1: z= q - р+ k = 8 – 4 + 1= 5.

Если граф не имеет циклов, то он называется ациклическим. В связном графе мостом называется ребро, при удалении которого увеличивается число компонент связности. Если в графе q = р - 1, то граф называется древовидным.

Ациклический связный граф называется деревом.

Теорема. Следующие утверждения равносильны,, т.е. если для графа G выполнено любое из условий, то он дерево:

1) Граф ацикличен и связан.

2) Граф ацикличен и древовиден.

3) Граф связан и древовиден.

4) Граф ацикличен, но добавление одного ребра приводит к образованию ровно одного цикла.

5) Каждое ребро графа есть мост.

6) Любые две вершины соединены единственной цепью.

Доказательство:

Из 1 2:

Граф ациклический и связный. Так как граф ацикличен, то z = 0. Так как граф связный, то k = 1. Т.к. z = q - р + k, (1) то 0 = q – р + 1, тогда q = р + 1. А это значит граф древовидный.

Докажем теперь, что из 23:

Так как граф древовидный, то q = р - 1. Так как граф ациклический, то z = 0. Подставим в (1): 0 = р - 1- р + k, отсюда k = 1, следовательно, граф связный.

Из 34:

В графе G: k =1; q = р - 1; из (1) получим z = 0. Добавим ребро и получим граф G , в котором q = q + 1; р = р и k = k = 1. Тогда z = q - р + k = q +1- р +1 = р – 1 + 1- р + 1 =1. z= 1,следовательно, образовался один цикл.

Докажем, что из 4 5:

Допустим, что граф G таков, что некоторое ребро U – не мост, то есть его удаление не приводит к увеличению компонент связности, а значит, граф G = G - U остается связным. По 4 он еще и ацикличен. Но если к связному ациклическому графу добавить ребро U, то должен получиться граф с циклом, значит граф циклический. Пришли к противоречию, следовательно, каждое ребро является мостом.

Из 5 6:

Пусть граф G таков, что вершины V и V соединены двумя цепями. Так как каждое ребро мост, то удаление какого-либо ребра из одной цепи должно привести к увеличению компонент связности, то есть V и V ─ не связаны. Но они связаны другой цепью. Пришли к противоречию, следовательно, любые две вершины соединены единственной цепью.

Из 6 цепь единственная.

Из 61:

Т.к существует цепь, связывающая любые две вершины, то граф связный. Предположим, что граф имеет цикл. Вершина V является началом и концом цикла. Тогда V связана с V двумя цепями. А это противоречит единственности цепи.

Что и требовалось доказать.

• V₀

V₁ •

• V₂

V₃ • • V₄

V₅ • • V₆ • V₇ • V₈ • V₉

• • • • • • • • • •

V₁₀ V₁₁ V₁₂ V₁₃ V₁₄ V₁₅ V₁₆ V₁₇ V₁₈ V₁₉

Рис. 55. Граф-дерево

В деревьях обычно одну из вершин выделяют и называют корнем.

Вершины, удаленные от корня на одно и то же расстояние образуют ярус. V₀ - нулевой ярус, V₁, V₂ – первый ярус, V₃, V₄, V₇, V₈, V₉ – второй ярус, V₅, V₆, V₁₅, V₁₆, V₁₇, V₁₈, V₁₉ ─ третий ярус, V₁₀, V₁₁, V₁₂, V₁₃, V₁₄ – четвертый ярус.

Вершины, степень которых равна 1 (висячие) называются концевыми, или листьями. На рис. 55 – это вершины, V₁₀, V₁₁, V₁₂, V₁₃, V₁₄, V₁₅, V₁₆, V₁₇, V₁₈, V₁₉ .

Упорядоченное объединение непересекающихся деревьев называется лесом. Ясно, что лес является несвязным графом.

Остовом связного графа называется подграф, содержащий все его вершины и являющийся деревом. Такое дерево называют покрывающим граф.

Каждая вершина дерева называется узлом.

Дата добавления: 2014-01-06