Глава 3. Орграфы

Определения и примеры

Орграфом D называется пара (V(D), A(D)), где V(D) - непустое конечное множество элементов, называемых вершинами, и A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами; V(D) и A(D) называются соответственно множеством вершин и семейством дуг орграфа D. Так, на рис. 21 представлен орграф, дугами которого являются (u, v), (v, v), (v, w), (v, w), (w, v), (w, u) и (z, w); порядок вершин на дуге указан стрелкой.

Граф, полученный из орграфа D «удалением стрелок» (т.е. заменой каждой дуги вида (v, w) на соответствующее ребро {v, w}), называется основанием орграфа D (рис. 22).

Рисунок 21

Рисунок 22

Две вершины v и w орграфа D называются смежными, если в A(D) существует дуга вида (v, w) или (w, v); при этом вершины v и w называются инцидентными любой такой дуге (а дуга — инцидентной соответствующим вершинам).

Два орграфа называются изоморфными, если существует изоморфизм между их основаниями, сохраняющий порядок вершин на каждой дуге. Матрицей смежности орграфа G множеством вершин {v₁, …, v_n} является матрица А = (a_ij), в которой a_ij равно числу дуг вида (v_i, v_j) в семействе A(D). Матрица, показанная на рис.23, является матрицей смежности для орграфа, изображенного на рис. 21. Простой орграф определяется очевидным образом.

Рисунок 23

Ориентированный маршрут в орграфе D представляет собой конечную последовательность дуг вида (v₀, v_j, (v_l, v₂), v_m). Можно записывать эту последовательность в виде v₀ -> v₁ ->... -> v_m и говорить об ориентированном маршруте из v₀ в v_m. Аналогичным образом можно определить ориентированные цепи, ориентированные простые цепи и ориентированные циклы, или орцепи, простые орцепи и орциклы.

Заметим, что хотя орцепь не может содержать данную дугу (v, w) более одного раза, она может содержать одновременно (v, w) и (w, v); например, на рис. 21 z -> w -> v -> w -> u является орцепью. Теперь мы в состоянии определить связность. Точнее, мы определим здесь два наиболее естественных и полезных типа связности орграфов, которые возникают в соответствии с тем, хотим мы или нет принимать во внимание ориентацию дуг.

Говорят, что орграф D связен (или слабо связен), если он не может быть представлен в виде объединения двух различных орграфов (определенного обычным образом); это эквивалентно тому, что связно основание орграфа D. Предположим дополнительно, что для любых двух вершин v и w орграфа D существует простая орцепь из v в w; тогда D называется сильно связным (этот термин настолько устоялся, что мы использовали его вместо более естественного «орсвязный»). Ясно, что любой сильно связный граф связен, но обратное неверно: на рис. 21 изображен связный орграф, не являющийся сильно связным.

Различие между связным и сильно связным орграфом станет яснее, если мы рассмотрим план города, по всем улицам которого допускается только одностороннее движение. Тогда связность соответствующего орграфа означает, что мы можем проехать из любой части города в любую другую, не обращая внимания на правила одностороннего движения; если же этот орграф сильно связен, то мы можем проехать из любой части города в любую другую, следуя всегда «правильным путем» вдоль улиц с односторонним движением. Важно, чтобы система с односторонним движением была сильно связной, и естественно возникает вопрос: при каких условиях карту улиц можно превратить в систему с односторонним движением таким способом, чтобы можно было проехать из любой части города в любую другую? Если, к примеру, город состоит из двух частей, связанных одним мостом, то мы никогда не сможем сделать все его улицы односторонними, поскольку какое бы направление мы ни приписали мосту, одна часть города будет отрезана. (Заметим, что сюда включается и тот случай, когда в городе имеется тупик.) С другой стороны, если мостов нет, то всегда найдется подходящая односторонняя система.

Для удобства будем называть граф G ориентируемым, если каждое его ребро (рассматриваемое как пара вершин) может быть упорядочено таким образом, что полученный в результате орграф будет сильно связным. Этот процесс упорядочения ребер будем называть «заданием ориентации графа» или «приписыванием направлений ребрам». Если, например, G - граф, изображенный на рис. 24, то его можно ориентировать и получить сильно связный орграф, изображенный на рис. 25.

Рисунок 24

Рисунок 25

Теорема. Пусть G — связный граф; он ориентируем тогда и только тогда, когда каждое его ребро содержится по крайней мере в одном цикле.