Определение

Множество V₀ V называется базой графа G = (V, U), если выполняются следующие свойства:

1) никакие две вершины из V₀ не соединяет путь в G;

2) из любой вершины множества V \V₀ существует путь в одну из вершин множества V₀.

Очевидно, что если V₀  это база графа G, то V₀ является внутренне устойчивым множеством.

Теорема 5.10

Всякий ориентированный граф имеет базу.

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

Заметим, что поскольку петли в графе считается неориентированными ребрами, то ориентированные графы не имеют петель.

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

Иначе говоря, множество D состоит только из таких вершин, которые находятся на некоторых циклах, в том числе циклах нулевой длины. При этом все вершины некоторого цикла включаются в D, если не существует путей, начинающихся в вершинах цикла, которые ведут в вершины вне данного цикла.

На множестве D определим отношение эквивалентности  соотношением  a, b D (a  b a и b лежат на одном цикле).

Образуем множество S, включив в него по одной вершине из каждого класса эквивалентности для отношения .

Покажем, что множество S образует базу графа G.

1. Никакие две вершины из S не соединяет путь в G, поскольку в противном случае эти две вершины должны лежать на общем цикле, или из вершин некоторого цикла в G, входящего в D, ведут пути в вершины, не лежащие с ними на одном цикле. Первый случай противоречит тому, что в S содержится не более чем по одной вершине из каждого класса эквивалентности отношения в . Второй случай противоречит определению множества D.

2. Если v  V \ S и v  D, тогда из v ведет путь в такую вершину из S, которая лежит с v на одном цикле.

Если же v D, то из v ведут пути в вершины, не лежащие с v на одном цикле. Возьмем любой такой путь. Дополнительно потребуем, чтобы он был простым и имел максимальную длину среди всех подобных путей.

Поскольку множество вершин графа G  конечное, то этот путь заканчивается либо в вершине, из которой не выходят ребра, либо в вершине некоторого цикла, вершины которого образуют класс эквивалентности в отношении .

В первом случае путь заканчивается в вершине из S. Во втором случае выбранный путь может быть продолжен до вершины класса эквивалентности, которая была включена в S.

Следовательно, множество S является базой графа G.

Доказательство окончено.

Пусть G = (V, U)  произвольный граф и V₀ V.

Множество всех вершин, из которых в вершины множества V₀ ведут ребра, обозначается как ^1(V₀).

Множество всех вершин, в которые из вершины множества V₀ ведут ребра, обозначается как  (V₀).

Теорема 5.11

Всякий ориентированный граф, не содержащий циклов нечетной длины, имеет ядро.

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

Пусть граф G = (V, U) удовлетворяет условиям теоремы. Построим ядро графа G с помощью следующей процедуры.

1. Обозначим S₁ базу графа G. Определим множество

V₁ = S₁   ^1 (S₁).

Удалим из G вершины V₁ вместе с ведущими в них ребрами.

3. В полученном графе G¹ найдем базу S₂, для которой

S₂ Г^1 (Г^1 (S₁) \ V₁) (1).

То есть в базе S₂ содержатся только такие вершины G, из которых в вершины S₁ ведут пути длины 2.

Такая база существует, поскольку в графе G из всякой вершины v  V \ S₁ ведет путь в некоторую вершину множества S_1. Тогда всякий такой путь из вершины, не являющейся соседней с вершинами множества S₁, проходит через вершины, лежащие от вершин множества S₁ на расстоянии 2. Поэтому в G¹ существует база, удовлетворяющая условию (1). Она состоит из вершин, находящихся на расстоянии 2 от вершин множества S₁.

Образуем множество V₂ = V₁  S₂  Г^{ 1}(S₂).

3. Удалим из G¹ вершины S₂  Г^1(S₂) вместе с ведущими в них ребрами.

4. Если еще удалены не все вершины исходного графа, то повторим действия 2 и 3.

Описанный процесс продолжаем до тех пор, пока не будут удалены все вершины исходного графа.

В результате будет построено семейство множеств вершин:

S₁, ... , S_m.

Образуем множество S = .

Покажем, что S является ядром графа G.

1. Множество S является внешне устойчивым, поскольку всякая вершина графа G в процессе удаления вершин этого графа попадает либо в некоторое множество S_i либо во множество Г^1(S_i). Поэтому, если v V\S, то i (v Г^1 (S_i)), т.е. из v ведет ребро в некоторую вершину множества S_i, а значит и в вершину S.

2. Множество S является внутренне устойчивым. Докажем это утверждение методом от противного. Предположим, что во множестве S содержатся две соседние вершины v₁ и v₂ графа G.

Положим для определенности, что v₁ S_i и v ₂ S_j, причем i < j . Это означает, что ребро, соединяющее эти вершины, ведет из v₁ в v₂. Эта ситуация изображена на рис. 5.29:

S₁ S_{2 . . .} S_{i . . .} S_{j . . .}

v₁ v₂

v₀

Рис. 5.29

По определению последовательности множеств S₁, .., S_m из вершины v₂ в некоторую вершину v₀ S_i ведет путь четной длины. Обозначим такой путь как W.

Так как S_i  это база подграфа, полученного из графа G на одном из шагов работы описанной выше процедуры, и последовательность v₁,W  это путь в этом же подграфе, то v₀ = v_1, поскольку в противном случае вершина v₁ не может входить в базу S_i.

Поэтому путь v₁,W образует цикл нечетной длины в графе G. Это противоречит условиям теоремы. Следовательно, множество S является внутренне устойчивым.

Доказательство окончено.

Упражнение. Привести пример ориентированного графа с циклами четной длины, который имеет ядро.