Свободные деревья

ДЕРЕВЬЯ

Матрица взаимодостижимости.

Образуем из матрицы E+ A+A²+…+ Aⁿ= (b_{i, j}) матрицу С порядка n по правилу:

с_{i, j} =.

Полученная матрица С называется матрицей связности, если G – неорграф и матрицей достижимости, если G – орграф.

Элемент этой матрицы с_{i, j} =1 тогда и только тогда, когда в графе есть (v_i, v_j) – маршрут (i≠j).

Матрицей контрдостижимости называется матрица Q=(q_{i, j}), элементы которой:

q_{i, j} =

Отметим, что Q=C^T. Матрицы достижимости и контрдостижимости используются для нахождения сильных компонент графа. Для этого используется матрица взаимодостижимости (сильных компонент), где символ означает поэлементное произведение матриц С и Q, т.е. s_ij=c_ij∙q_ij.

Элемент s_{i j}=1 тогда и только тогда, когда вершины v_i и v_j взаимодостижимы. Это означает, что они находятся в одной сильной компоненте. Следовательно, сильная компонента, содержащая вершину v_{i ,} состоит из тех элементов v_{ij ,} для которых s_ij =1.

Пример. Для графа, изображённого ниже, определим матрицы достижимости, контрдостижимости и взаимодостижимости

Матрица достижимости C =.

Матрица контрдостижимости Q=C^T =.

=

По второй строке матрицы S находим, что сильная компонента, содержащая вершину 2 состоит из вершин (1, 2, 3).

Деревом называется связный граф без циклов (контуров).

Несвязный граф без циклов (контуров) называется лесом. Компоненты связности леса являются деревьями.

Подграф G ₁ = (V ₁, E ₁) графа G= (V, E) называется остовным деревом в графе G= (V, E), если G ₁ = (V ₁, E ₁) – дерево и V ₁ =V.

Дерево – это минимальный связный граф, т.к. при удалении хотя бы одного ребра (дуги) он теряет связность. Неориентированное дерево называется свободным.

Например: 1) Диаграммы всех различных свободных деревьев с 5-ю вершинами:

2) Диаграммы всех различных свободных деревьев с 6-ю вершинами:

Лемма 1. Если граф G =(V, E) связный и ребро (u, v) содержится в некотором цикле графа G, то при удалении этого ребра получится новый связный граф.

Доказательство: При удалении ребра (u, v), вершины u и v останутся в одной и той же связной компоненте, т.к. они остаются связными за счет оставшейся части цикла.

Теорема 1. Любой связный граф содержит хотя бы одно остовное дерево.

Доказательство: Если в графе G нет циклов, то G является искомым остовным деревом, если в G есть цикл, то удалим из G какое-нибудь ребро, входящее в цикл. В результате этого получается некоторый подграф G ₁. По лемме 1 G ₁ – связный граф. Если в графе G ₁ нет циклов, то G ₁ есть искомое остовное дерево. В противном случае процесс продолжается. Этот процесс должен завершиться, т.к. Е – конечное множество.

Лемма 2. Если к связному графу добавить новое ребро на тех же вершинах, то в нём появится цикл.

Доказательство: Пусть G= (V, E) – связный граф. Пусть uÎV, vÎV, (u, v) ÏE. Т.к. G – связный граф, то в нем есть цепь от v к u, при этом она является простой цепью соединяющей v и u. Поэтому во вновь полученном графе с добавленным ребром (u, v) имеется цикл C (u, v).

Лемма 3. Пусть в графе G= (V, E) имеется n вершин и m ребер. Тогда в G не менее n-m связных компонент. Если при этом в графе G нет циклов, то он состоит ровно из n-m связных компонент.

Доказательство: Пусть к некоторому графу H, содержащему вершины u и v добавляется ребро (u, v). Тогда, если u и v лежат в разных связных компонентах графа H, то число связных компонент уменьшается на единицу. Если u и v лежат в одной связной компоненте графа H, то число связных компонент не уменьшится. Таким образом, число связных компонент при добавлении ребра уменьшается не более чем на единицу. Значит, при добавлении m ребер, число связных компонент уменьшается не более чем на m. Т.к. граф G, можно получить из графа G ₁=(V, Ø), добавлением m ребер, то в графе G не менее n-m связных компонент. Пусть далее в графе G нет циклов, и пусть в процессе получения G из G ₁ добавляется ребро (u, v). Если бы u и v лежали в одной связной компоненте, то в G, согласно лемме 2, возникал бы цикл. Следовательно, u и v лежат в разных связных компонентах и при добавлении ребра (u, v) число связных компонент уменьшается ровно на 1. Следовательно, G состоит ровно из n-m компонент.

Теорема 2. О различных определениях свободного дерева. (Свойства свободных деревьев).

Следующие пять определений эквивалентны:

1) G – свободное дерево

2) G – без циклов и m=n- 1

3) G – связный граф и m=n- 1

4) G –связный граф, но при удалении любого ребра становиться несвязным

5) G – без циклов, но при добавлении любого ребра на тех же вершинах появляется цикл

Доказательство: Если доказать, что 1)Þ2)Þ3)Þ4)Þ5)Þ1), то из любого условия вытекает любое другое.

1)Þ2) Т.к. G – связный граф и G не содержит циклов, то n-m= 1 по лемме 3. Отсюда m=n- 1.

2)Þ3) По лемме 3 число связных компонент равно n-m= 1, т.е. граф G – связный граф.

3)Þ4) При удалении одного ребра n-m= 2. Тогда по лемме 3 число связных компонент не менее, чем n-m=2 т.е. граф несвязный.

4)Þ5) Если G имеет цикл, то согласно лемме 1 можно удалить одно ребро так, что граф останется связным. Согласно лемме 2, если добавить любое новое ребро к связному графу на тех же вершинах, то появиться цикл.

5)Þ1) Доказательство ведётся от противного. Предположим, что если G несвязный граф и вершины u и v лежат в разных компонентах графа G, но добавление к G ребра (u, v) очевидно, не порождает циклов, что противоречит 5). Отсюда следует, что G связный граф. Теорема доказана.

Вершина в графе называется концевой (висячей), если её степень равна 1. Ребро инцидентное концевой вершине называется концевым. Конечное дерево, состоящее более чем из одной вершины, имеет хотя бы две концевые вершины и одно концевое ребро.

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