Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
60
Добавлен:
19.05.2015
Размер:
660.48 Кб
Скачать

Логическое

программирование.

Языки,

свойства.

Деревья и их свойства

Лесом называется граф, не содержащий циклов, связанный лес называется деревом. Например:

Деревья и леса – простые графы.

Теорема 1. Пусть граф Т имеет m вершин. Тогда следующие утверждения эквивалентны:

1)Т является деревом;

2)Т не содержит циклов и имеет n-1 ребер; 3)Т связен и имеет n-1 ребер;

4)Т связен и каждое его ребро является мостом. 5)Любые 2 вершины Т соединены ребром.

6)Т не содержит циклов, но добавляя к нему любое иное ребро, мы получим ровно 1 цикл.

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

Если m=1, утверждение очевидно. Пусть n≥2.

1) ->2) По определению Т не содержит циклов; тогда удаление любого ребра разбивает Т на 2 графа, каждый из которых – дерево. По индуктивному предложению число ребер в каждом из этих деревьев на единицу меньше числа вершин.

Отсюда получаем, что полное число ребер графа Т равно n-1.

Из 2) ->3) Если Т несвязен, то каждая из его компонент - связанный граф без циклов, число вершин в каждой из его компонент на 1 больше, чем ребер. Тогда полное число вершин Т больше полного числа его ребер по крайней мере на 2, а это противоречит тому, что Т имеет n-1 ребро.

3) ->4) удаление любого ребра приводит к графу с n вершинами и n-2 ребрами, который не может быть связен.

4) ->5). Так как Т связен, то каждая пара его вершин соединена по крайней мере одной простой цепью. Если же данная пара его вершин соединена двумя простыми цепями, то они замыкаются в цикл, а это противоречит тому, что каждое ребро в Т является мостом.

5) ->6). Если Т содержит цикл, то любые 2 вершины этого цикла соединены, по крайней мере, двумя прямыми цепями.

Добавим теперь к графу Т какое – то ребро L; тогда, мы получим цикл, поскольку инцидентные ребру L вершины уже соединены в Т простой цепью.

При этом получим только 1 цикл.

6) ->1). Пусть Т несвязен, тогда добавление любого ребра, соединяющего вершину одной компоненты с вершиной другой компоненты, не приводит к образованию цикла.

Следствие:

Пусть G – лес с n вершинами и k компонентами; тогда G имеет n-k ребер.

Доказательство: Применим к каждой компоненте G предложения 2) теоремы 1. Сумма степеней всех n вершин дерева равна удвоенному числу его ребер 2n – 2; отсюда следует, что при n≥2 дерево, имеющие n вершин, всегда содержит не менее 2-х висячих вершин.

В связном графе G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающее все вершины графа G; - остовное дерево (остов, каркас) графа G.

Пример:

В общем случае G – произвольный граф с n вершинами, m ребрами и k компонентами. Удаляя ребра в G, получим в результате граф, называемый остовным лесом. Число удаленных в этой процедуре ребер называется циклическим рангом (или цикломатическим числом) графа G и обозначаются через γ(G). Видим, что γ(G)=m-n+k. Итак, циклический ранг дает меру связности графа: циклический ранг дерева равен нулю, а циклический ранг циклического графа равен единице. Коциклический ранг (или ранг разреза) графа G – число ребер в его остовном лесе; коциклический ранг обозначается через f(G) и равен n-k.

Дополнением остовного леса T графа G является граф, полученный из G удалением ребер Т.

Теорема 2. Если Т остовной лес графа G, то 1) всякий разрез в G имеет общее ребро с Т; 2) каждый цикл в G имеет общее ребро с дополнением Т.

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

1) Пусть C* - разрез графа G, удаление которого разбивает одну из компонент G на 2 подграфа H и К (так как при удалении ребер, принадлежащих разрезу, остается граф имеющий ровно 2 компоненты. Если имеем разрез из одного ребра L, то L – мост или перешеек). Поскольку Т – осnовной лес, в нем должно содержаться ребро, соединяющее вершину из H с вершиной из K;это и есть требуемое ребро.

2)Пусть C – цикл в графе G, не имеющий ни одного общего ребра с дополнением Т, тогда C содержится в Т, что невозможно.

Фундаментальные система циклов, ассоциируемая с Т.

Если добавить к Т любое, не содержащееся в нем ребро из G, то по 6) теоремы 1 получим единственный цикл; множество всех циклов, полученных тем же способом (путем добавления по отдельности каждого ребра из G, не содержащегося в Т), называется фундаментальной системой циклов, ассоциируемой с Т.

Число циклов равно циклическому рангу графа G.

Пример:

По 4) теории 1 удаление любого ребра из Т разбивает множество вершин дерева Т на 2 непересекающихся компонента V1 и V2. Множество всех ребер графа G, каждое их которых

соединяет вершину из V1 с вершиной из V2, является разрезом

графа G. Множество всех разрезов назовем фундаментальной системой разрезов, ассоциируемой с Т.

Разрезы должны быть различны и их число равно коциклическому рангу графа G. Имеем, фундаментальная система разрезов: {l1,l5}, {l2,l5,l7,l8}, {l3,l6,l7,l8},{l4,l6,8}.

Помеченным графом называется пара {G,φ}, где G – граф, и φ – распределение меток в G. Числа 1, …, n называются метками графа и обозначает вершины G через υ1, и υ4.

Два помеченных графа (G1 и φ1) и (G2 и φ2) назовем

изоморфными, или существует изоморфизм между G1 и G2, сохраняющий распределение меток в этих графах.

Пример:

Общее число различных распределений меток 3 * 4 = 12

Число всех неизоморфных деревьев с 4 – мя вершинами равно 16.

Теорема 3: (Kэли 1889) существует ровно nn-2 различных помеченных деревьев с n вершинами (без доказательства)

Следствие: Число остовных деревьев в Kn равно nn-2 (Kn – полный граф с n вершинами).