222 Глава 7. Связность графов

единяющее их ребро вместе с соединяющим их маршрутом четной длины образовало бы циклический маршрут нечетной длины.

Следствие. Граф G = (X; U) является бихроматическим тогда и только тогда, когда он не содержит простых циклов нечетной длины.

7.3 Компоненты связности

Если маршрут рассматривать с учетом ориентации ребер (может быть и по звеньям), т.е. в определении маршрута

x0u1x1 : : : xl¡1ulxl

считаем

P (x0; u1; x1) & : : : & P (xl¡1; ul; xl), получим соответствующие определения:

²частично ориентированный маршрут;

²частично ориентированная цепь;

²частично ориентированный цикл.

Если же все ui – дуги, то все маршруты, соответственно, ориентированные. Обычно при ссылке на ориентированные маршруты для краткости используют префикс “ор” – ормаршрут, орцепь, орцикл, в том числе и простые: простая орцепь, простой орцикл и т.д. Часто встречается термин путь – орцепь (простой путь – простая орцепь).

Вопросы, которые мы сейчас рассмотрим применимы, по отдельности, к неориентированным и ориентированным графам.

Для неориентированных графов

Определение. Вершины x; y графа G называются отделенными , если в G не существует никакой соединяющей их цепи, и неотделенными, если хотя бы одна такая цепь существует.

Отношение неотделенности вершин

²рефлексивно (каждая вершина соединена с собой цепью нулевой длины);

²симметрично (цепь, записанная в обратном порядке – тоже цепь);

7.3. Компоненты связности	223

²транзитивно (если существует цепь из x в y, и цепь из y в z, то существует и цепь из x в z).

Таким образом, отношение неотделенности есть отношение эквивалентности на множестве вершин X; при этом X разбивается на классы попарно неотделенных вершин X1; X2; : : : X·.

Определение. Подграфы Gi = (Xi; Ui; P ), порожденные подмножествами Xi, не имеют общих вершин и ребер и называются компонентами связности (или просто компонентами).

Число их обозначается через ·(G) (каппа). Если ·(G) = 1, то граф называется связным. Другая крайность – вырожденный граф: число его компонент равно числу вершин.

Отношение “быть в одной компоненте” для ребер – эквивалентность, как и для вершин.

Для ориентированных графов.

Вершина y достижима из вершины x, если существует путь из x в y. Высказывание “y достижима из x” обозначим через D(x; y).

Вершины x и y взаимодостижимы , если истинно высказывание

D(x; y) & D(y; x).

Отношение взаимодостижимости рефлексивно, симметрично и транзитивно, т.е. является отношением эквивалентности. Множество X вершин графа разбивается на классы взаимодостижимых

вершин X1; X2; : : : X!.

·

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

G.

Число бикомпонент обозначается ~·(G) .

Множество вершин, достижимых из x, обозначим D(x).

Теорема 7.2 Вершины x и y взаимодостижимы тогда и только тогда, когда D(x) = D(y).

Д о к а з а т е л ь с т в о . 1. °( Достаточность. Пусть D(x) = D(y); требуется доказать взаимодостижимость x и y. Так как x 2 D(x) и y 2 D(y), то из равенства D(x) = D(y) следует, что y 2 D(x) и x 2 D(y), т.е. вершины x и y взаимодостижимы.