Направленные графы

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

В свете изложенного, нам придется модифицировать старое определение, ибо теперь конец и начало ребра должны быть строго идентифицированы, то есть пара вершин {v, w} для ребра "е" становится упорядоченной парой вершин, первая из которых отвечает началу ребра, а вторая - его концу (е) = (v, w).

Определение 1.9. Направленный граф D состоит из конечного непустого множества вершин V = V_D и конечного множества направленных ребер Е = E_D, которые производят отображение : Е V х V. Если (е) = (v, w), то v называется начальной вершиной, a w конечной вершиной ребра е.

Для направленного графа D можно путем отмены направленности ребер получить соответствующий ненаправленный граф Г, который называется нижним для графа D. Формально, нижний для графа D граф имеет те же вершины и те же ребра, просто последний утрачивает свою направленность.

Направленный граф называется простым, если он не содержит петель (то есть ребер е, для которых (е) = (v, v)) и не содержит множественных ребер (то есть с одинаковыми начальными и конечными вершинами).

На рис. 3.14 показаны простой направленный и нижний для него графы. Два ребра направленного графа, связывающие вершины v₄ и v₅ не являются множественными, ибо их направления различны, то есть у них разные начальные и конечные вершины. В то же время, соответствующий нижний граф не является простым, ибо он имеет множественные ребра.

Рис. 3.14

Многие определения для ненаправленных графов могут быть перенесены на направленные графы с учетом необходимых модификаций. В частности, определения смежности, инцидентности и валентности остаются неизменными. Так, например, две вершины v и w направленного графа будут смежными, если и только если существует направленное ребро либо из v в w, либо из w в v. Однако, мы должны модифицировать определение матриц смежности для направленного графа с целью учета направленности ребер. Элемент (i, j) матрицы смежности направленного графа представляет число ребер с начальной вершиной v_i; и конечной вершиной v_j, поэтому матрица может и не быть симметричной. Матрица смежности для направленного графа, представленного на рис. 3.14, имеет вид:

Для направленного графа валентность вершины равна сумме эле­ментов в соответствующей строке плюс столбец матрицы смежности. Элементы в строке, отвечающей вершине "v", представляют собой ребра, начинающиеся в вершине "v", элементы в столбце, отвечающей вершине "v", представляют собой ребра, заканчивающиеся на вершине "v". Сумма всех элементов матрицы смежности, конечно, равна сумме всех ребер направленного графа.

Для направленного графа последовательностью направленных ребер из "v₀" в "v_n" называется последовательность ребер е₁ е₂,..., е_n таких, что (е_i) = (v_i-1, v_i)для i=l, 2,..., n. Определения направленного пути и направленной цепи являются очевидными модификациями определений для ненаправленного графа.

Определение 3.16. Направленный граф называется связным (или слабо связным), если его нижний ненаправленный граф является связанным. Направленный граф называется сильно связным, если для каждой упорядоченной пары вершин (v, w) существует направленный путь из v в w.

Дата добавления: 2014-12-27