Дискретная математика: графы и автоматы. Альпин Ю.А - 5 стр.

§ 1. Первые понятия теории графов                                    5


в которой соседние вершины vi и vi+1 смежны (иногда запятые за-
меняются чёрточками). Про маршрут (1) говорят, что он связывает
вершины v1 и vk+1 , или является (v1 , vk+1 )-маршрутом. Число k рёбер
в маршруте (1) называется его длиной. Маршрут называется замкну-
тым, если v1 = vk+1 .
    Маршрут называется цепью, если все его рёбра различны. Цепь
называется простой, если её вершины различны, кроме, может быть,
первой и последней. Замкнутая цепь называется циклом, замкнутая
простая цепь — простым циклом. Заметим, что длина незамкнутой
простой цепи в графе с n вершинами не больше, чем n − 1, а длина
простого цикла — не больше, чем n.
   Лемма 1. При u 6= v всякий (u, v)-маршрут содержит про-
стую (u, v)-цепь.
   Д о к а з а т е л ь с т в о. Если маршрут не является простой
цепью, то он имеет вид
               u − . . . − s − t − . . . − s − w − . . . − v.
Но тогда имеется более короткий (u, v)-маршрут
                      u − . . . − s − w − . . . − v.
Если и он — не простая цепь, то снова возможно сокращение. Ясно,
что после нескольких сокращений получится простая (u, v)-цепь. ¤
   Следующая лемма доказывается аналогично и рекомендуется в
виде упражнения.
    Лемма 2. Всякий цикл содержит простой цикл, причём каж-
дая вершина и ребро цикла принадлежат некоторому простому цик-
лу.
   Лемма 3. Если в графе есть разные простые (u, v)-цепи, то
граф содержит простой цикл, составленный из вершин и рёбер
этих цепей.
    Д о к а з а т е л ь с т в о. Рассмотрим неравные простые цепи
                      u = l1 − l2 − . . . − lk = v,
                      u = p1 − p2 − . . . − pm = v.
Пусть i — наименьший номер, для которого li = pi , но li+1 6= pi+1 .
Пусть j > i — наименьший номер, такой, что lj = pt при некотором
t. Тогда li − li+1 − . . . − lj − pt−1 − . . . − pi — простой цикл. ¤