Ориентированный граф. Степень входа и степень выхода вершины. Источник. Сток. Ориентированный путь. Ориентированный цикл (контур).

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

Ребро графа называется ориентированным, если одну из его вершин считать началом, а другую концом этого ребра.

Граф у которого все ребра ориентированные, называется ориентированным графом.

Ребра ориентированного графа имеют определённые фиксированные начало и конец и называются дугами. V_iV_j ¹ V_jV_i

Полустепенью входа вершины ориентированного графа называется число рёбер, для которых эта вершина является концом. Обозначается: deg₊( V)

Полустепенью выхода вершины ориентированного графа называется число рёбер, для которых эта вершина является началом. Обозначается: deg _-( V)

В орграфе маршрут является ориентированным и называется путем.

Ни одно ребро пути не должно встречаться дважды и направление каждой дуги должно совпадать с направлением пути.

Путь - это упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны.

‌‌‌‌ ‌‌| ‌АД| = 3

Если в ориентированном графе нельзя «пройти» от вершины до другой вершины, то расстояние между ними называют бесконечным.

| ВД | = ∞ ‌

Вершина ориентированного графа называется истоком, если в нее не входит ни одна дуга, то есть d+(v) = 0.

Вершина ориентированного графа называется стоком, из нее не выходит ни одной дуги, то есть d-(v) = 0.

Матрица смежности- это квадратная матрица размерностью n*n,(где n -число вершин графа), однозначно представляющая его структуру.

A={aij}, i,j= 1,2,...,n, а каждый элемент матрицы определяется следующим образом:

aij=1, если ∃ дуга (Vi, Vj),

aij=0, если нет дуги (Vi, Vj).

На пересечение стоки и столбца ставится 1 или 0 в зависимости от того , имеется ли дуга, идущая из метки строки в метку столбца.

Строки матрицы инцидентности соответствуют вершинам, а столбцы – ребрам или дугам.

Матрица инцидентности ориентированного графа G – это матрица B=(bij) размера n×m такая, что

рис 25.1

Пусть V_i и V_j – вершины орграфа G. Вершина V_i достижима из V_j, если существует (V_i,y)–путь. Любая вершина достижима сама из себя. Вершины V_i и V_j сильно связаны, если они достижимы одна из другой.

Например, для графа, изображенного на рисунке 25.2, вершины V₂ и V₃ сильно связаны, вершины V₁ и V₄ сильно связаны, вершина V₆ достижима из V₁, но вершина V₁ недостижима из V₆.

рис 25.2

Компонентой сильной связности графа G называется его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа графа ориентированного G.

Граф, изображенный на рисунке. 25.3 имеет три компоненты сильной связности. Они обведены пунктирными линиями.

на рис. 25.3

Заметим, что существуют дуги, не принадлежащие ни одной из компонент сильной связности.

Достижимость в графе описывается матрицей достижимости R=[r_ij], i, j=1, 2, ... n, где n – число вершин графа, а каждый элемент определяется следующим образом:

r_ij=1, если вершина х_j достижима из х_i ,

r_ij=0, в противном случае.

Матрица контрдостижимости Q = [ q_ij], i, j =1, 2, ... n, где n – число вершин графа, определяется следующим образом:

q_ij=1, если из вершины x_j можно достичь вершину x_i ,

q_ij=0, в противном случае.

Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[s_ij] порядка n, элементы которой равны

рис 25.4