Путь и цикл в графе

Определение 1. Путем от x_i до x_j называется такая последовательность ребер графа, ведущая от x_i к x_j, в которой два соседних ребра имеют общую вершину и никакое ребро не встречается дважды. Длиной пути называется число ребер этого пути.

Определение 2. Путь от x_i до x_j называется простым, если он не проходит через одну вершину более одного раза.

Пример 1. Рассмотрим граф

В данном графе есть следующие пути от x ₁ до x ₆:

1) x ₁, x ₂, x ₅, x ₆ - путь длиной 3;

2) x ₁, x ₂, x ₃, x ₅, x ₆ - путь длиной 4;

3) x ₁, x ₂, x ₄, x ₅, x ₆ - путь длиной 4;

4) x ₁, x ₂, x ₃, x ₅, x ₄, x ₂, x ₅, x ₆ - путь длиной 7.

Первые три пути являются простыми.

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

Определение 4. Цикл называется простым, если он не проходит через одну вершину более одного раза.

Пример 2. Рассмотрим граф

В данном графе есть следующие циклы:

1) x ₁, x ₅, x ₄, x ₁ - цикл длиной 3;

2) x ₁, x ₂, x ₃, x ₁ - цикл длиной 3;

3) x ₁, x ₂, x ₄, x ₅, x ₃, x ₁ - цикл длиной 5;

4) x ₁, x ₂, x ₄, x ₅, x ₂, x ₃, x ₁ - цикл длиной 6;

и т. д.

Первые три цикла являются простыми.

Теорема. Если у графа G(X,T) все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

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