Понятие ориентированного графа

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

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

Рис. 1 Орграф

Рис. 2. Основание орграфа

Две вершины 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). Матрица, показанная на рис.3, является матрицей смежности для орграфа, изображенного на рис. 1. Простой орграф определяется очевидным образом.

Рис. 3 Матрица смежности

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

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

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

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

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

Рис. 4. Граф

Рис. 5.сильно связный орграф

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

Орграфы и матрицы

Матрицей смежностей А(D) орграфа D называется (р×р)-матрица ||a_ij||, у которой a_ij= 1, если V_iV_j- дуга орграфа D, и a_ij=0 в противном случае. Матрица смежностей которого имеет вид (рис. 6):

Рис. 6. Матрица смежности графа

Легко проверить, что суммы элементов по строкам матрицы A(D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам - полустепеням захода.

Как и в случае графов, степени матрицы смежностей А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Теорема. (i, j)-й элемент а_ijⁿ матрицы А" равен числу маршрутов длины n, идущих из вершины v_i в вершину v_j.

Упомянем здесь вкратце еще о трех матрицах, связанных с орграфом D_s - о матрице достижимостей, матрице расстояний и матрице обходов. В матрице достижимостей R элемент r_ij равен 1,если вершина v_i достижима из v_j и равен 0 в противном случае. В матрице расстояний (i, j)-й элемент равен расстоянию из вершины v_i в вершину v_j; если же из v_i в v_j нет путей, то соответствующий элемент полагаем равным бесконечности. В матрице обходов (i, j)-й элемент равен длине наиболее длинного пути из v_i в v_j, а если таких путей нет, то опять-таки полагаем этот элемент равным бесконечности. Для орграфа D, показанного на рис. 7.

Рис. 7. Матрицы.

Следствие. Элементы матриц достижимостей и расстояний связаны со степенями матрицы А следующими соотношениями:

1) r_ii = 1 и d_ii = 0 для всех i;

2) r_ij = 1 тогда и только тогда, когда a_ijⁿ> 0 для некоторого n;

3) d(v_i,v_j) равно наименьшему из чисел n, для которых a_ijn> 0

Эффективных методов для нахождения элементов матрицы обходов не существует. Эта проблема тесно связана с некоторыми другими давно поставленными алгоритмическими проблемами теории графов, такими, как нахождение остовных циклов и контуров, а также решение задачи о коммивояжере.

Поэлементное произведение В×С матриц B=||b_ij|| и C=||c_ij|| имеет своим (i, j)-м элементом b_ijc_ij. Матрицу достижимостей орграфа можно использовать для нахождения его сильных компонент.