Цепи, циклы, компоненты

Чередующаяся последовательность

v ₁, e ₁, v₂ , e₂,..., e_l, v_{l+ 1} (1)

вершин и ребер графа, такая что e_i = v_iv_{i+ 1}(i = ), называется маршрутом, соединяющим вершины v ₁и v_{l+ 1} (или (v ₁, v_{l+ 1}) -маршрутом). Очевидно, что маршрут (1) можно задать последовательностью

v ₁, v₂ ,..., v_{l+ 1} (2)

его вершин, а также последовательностью

e ₁, e ₂,..., e_l ребер.

Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Маршрут (1) называется циклическим, если v ₁ = v_{l+ 1}. Циклическая цепь называется циклом, а циклическая простая цепь — простым циклом. Число l ребер в маршруте (1) называется его длиной. Простой цикл длины l называется l-циклом, 3-цикл часто называют треугольником. Длина всякого цикла не менее трех, если речь идет о простом графе, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.

Очевидно, что любую цепь графа можно рассматривать как его подграф.

Пусть P — некоторая цепь вида (2) в графе G, v _i и v _j— входящие в нее вершины, i < j. Очевидно, что часть v _i, v _i+1 ,..., v _jцепи P, начинающаяся в вершине v _i изаканчивающаяся в v_j, сама является цепью графа G. Эта цепь называется (v_i, v_j) -подцепью цепи P.

Обратимся, например, к графу, изображенному на рис. 4.1. В нем (1, 2) и (1, 2, 4, 7) являются простыми цепями; (1, 2, 4, 7, 8, 4) — цепь, не являющаяся простой; (1, 2, 4, 7, 8, 4, 2)—маршрут, не являющийся цепью; (1, 2, 4, 1)—простой цикл. Обхват этого графа равен 3.

Для ориентированного графа вводится понятие ориентированного маршрута — это последовательность вида (1), в которой e _i = (v _i, v _i+1). Аналогом цепи в этой ситуации служит путь (ориентированная цепь). Вершина v называется достижимой из вершины u, если существует (u, v)-путь. Поскольку при u ¹ v произвольный (u, v)– маршрут, не являющийся простой цепью, превращается в простую (u, v)-цепь после устранения «лишних кусков», то верно

Утверждение 4.1. При u ¹ v всякий (u, v) -маршрут содержит простую (u, v) -цепъ.

Аналогично получается

Утверждение 4.2. Всякий цикл содержит простой цикл.

Ниже окажутся полезными следующие утверждения 4.3 и 4.4.

Утверждение 4.3. Объединение двух несовпадающих простых (u, v) -цепей содержит простой цикл.

> Пусть P = (u ₁ ,..., u_k)и q= (v ₁,..., v_l)—несовпадающие простые цепи, u ₁ = v ₁ = u, u_k = v_l = v, u _aи v _a— первые, считая от u, из несовпадающих вершин этих цепей, u _bи v _g— первые из совпадающих вершин, следующих после u _aи v _a. Тогда a>1 и объединение (u _a-1, u _b)-подцепи цепи P и (v _a-1, v _g)-подцепи цепи Q является простым циклом

u _a-1, u _a ,..., u _b, v _{g -1},..., v _a, u _a-1

(рис. 4.2). <

Утверждение 4.4. Если C и D — два несовпадающих простых цикла, имеющих общее ребро e, то граф (C È D) - e также содержит простой цикл.

> Если e = uv, то C - e и D - e — несовпадающие простые (u, v)-цепи. Поэтому нужное следует из предыдущего утверждения. <

Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Учитывая утверждение 4.1, можно в этом определении заменить маршрут цепью или простой цепью.

Очевидно следующее

Утверждение 4.5. Для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v) -маршрут.

Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой)графа G. Слово «максимальный» означает максимальный относительно включения, т. е. не содержащийся в связном подграфе с большим числом элементов. Множество вершин связной компоненты называется областью связности графа.

Теорема 4.6. Каждый граф представляется в виде дизъюнктного объединения своих связных компонент. Разложение графа на связные компоненты определено однозначно.

> Пусть G — произвольный граф. На множестве VG определим бинарное отношение ~, положив u ~ v для вершин u и v, если u = v или в графе G существует (u, v)-маршрут. Очевидно, что это отношение есть эквивалентность. Следовательно, мы получим разбиение множества VG на классы, отнеся в один класс все вершины, эквивалентные друг другу. Пусть VG = V_i - такое разбиение. Очевидно, что порожденные подграфы G_i = G (V_i)и только они являются компонентами графа G и G= G_i — дизъюнктное объединение. <

Полезно следующее

Утверждение 4.7. Для любого графа либо он сам, либо его дополнение является связным.

> Пусть G — несвязный граф, A — одна из его областей связности, B = VG\A. Тогда для любых a из A и b из B в дополнительном графе есть ребро ab. Следовательно, произвольная вершина из B соединена с a маршрутом длины 1, а произвольная вершина из A (отличная от a)соединена с a маршрутом длины не более чем 2. Теперь из утверждения 4.5 вытекает, что связен. <

С помощью предыдущего утверждения некоторые проблемы (например, проблема изоморфизма) сводятся к случаю связных графов.

Полезна также и следующая

Лемма 4.8. Пусть G — связный граф, e Î EG. Тогда:

1) если ребро e принадлежит какому-либо циклу графа G, то граф G — e связен;

2) если ребро e не входит ни в какой цикл, то граф G — e имеет ровно две компоненты.

> 1) Пусть ребро e = uv принадлежит циклу C графа G. Заменив в каждой (x, y)-цепи, содержащей e, подцепь (u, e, v)(и, v)-цепью C — e, получим (x, y)-маршрут, не содержащий ребра e. Следовательно, в графе G любые две несовпадающие вершины соединены маршрутом, не проходящим через e. Но тогда и граф G — e связен.

2) Пусть ребро e = uv не входит ни в какой цикл графа G. Тогда, очевидно, вершины u и v принадлежат разным компонентам, например, G_u и соответственно G_v, графа G — e. Для произвольной вершины x ¹ u в G существует (x, u)-маршрут. Если ребро e в этот маршрут не входит, x Î G_u. В противном случае x Î G_v. <

Ниже число ребер и число компонент графа G обозначаются через m (G)и k (G)соответственно.

Очевидно, что число ребер в произвольном графе порядка n не больше числа ребер в K_n, равного . Но сколько ребер может быть в графе порядка n с фиксированным числом k компонент? На этот вопрос отвечает следующая

Теорема 4.9. Если k (G) = k для n-вершинного графа G, то

n - k <= m (G)<=(n-k)(n-k + l)/2, (3)

причем обе эти оценки для m (G) достижимы.

>Вначале рассмотрим верхнюю оценку. Пусть G — граф порядка n с k компонентами и максимальным для таких графов числом ребер. Тогда каждая его компонента является полным графом. Пусть, далее, K_p и K_q — две компоненты, p >= q > 1, v — вершина из второй компоненты. Удалив из графа все ребра, инцидентные вершине v, и соединив v ребром с каждой вершиной из первой компоненты, получим новый граф порядка n с тем же числом компонент и большим числом ребер. Последнее невозможно, стало быть, только одна из компонент может иметь порядок, больший 1. Он равен n — k+ 1, и потому

Справедливость верхней оценки (3) и ее достижимость доказаны.

Перейдем к доказательству неравенства m (G) >= n — k. Оно очевидно при m (G)=0, так как тогда k = п. Воспользуемся индукцией по m (G). Пусть m (G) >0 и пусть для графов с меньшим, чем m (G), числом ребер соответствующее неравенство верно. Рассмотрим граф G — e, где e Î EG. Согласно лемме 4.8 число компонент этого графа равно k или k + 1. Число ребер в нем равно m (G) — 1. По индуктивному предположению в обоих случаях m (G)-1 >= n — k — 1. Следовательно, m (G) >= n — k. Нужное неравенство доказано.

Дизъюнктное объединение G = O_k-1 È K_n-k+1 реализует равенство m (G) =n - k. <

Из первой части приведенного доказательства вытекает

Следствие 4.10. При фиксированных n и k<=n среди графов G порядка n с k (G) =k существует только один граф, а именно, G = O_k-1 È K_n-k+1, с максимальным числом ребер.

Графы с минимальным числом ребер (при фиксированных n и k)изучаются в следующей главе.