Способы задания ориентированного графа

Ориентированный граф как и неориентированный можно задать с помощью его диаграммы или в матричной форме.

0. Матрица инцидентности графа.

Пусть задан граф D(V, X), где V ={v₁, v₂, …, v_n}, X = {x₁, x₂,…, x_m}.

Матрицей инцидентности графа D(V, X) называется матрица размера m n, элементы которой определяются следующим образом:

Замечание: если х_j – петля для v_i , то b_ij – любое число, отличное от 1, -1 и 0.

Матрица инцидентности однозначно определяет структуру графа, что позволяет читать всю необходимую информацию о графе. Информация о дугах считывается по строкам, о вершинах – по столбцам.

Составим матрицу инцидентности для орграфа из предыдущего примера . Это матрица размера 4 4:

Элемент b₃₂ = 2 показывает, что дуга х₃ является петлей. Найдем полустепени исхода и захода, например, для вершины v₂ : полустепень исхода - ⁺(v₂) = 2, т.к. в соответстующем этой вершине столбце одна «-1» и еще учитываем петлю; полустепень захода - ^-(v₂) = 3, т.к в столбце две единицы и петля.

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

Пусть задан граф D(V, X), где V ={v₁, v₂, …, v_n}, X = {x₁, x₂,…, x_m}.

Матрицей смежности графа D(V, X) называется квадратная матрица n n, элементы которой определяются следующим образом:

k – количество дуг, соединяющих вершины v_i и v_j .

Составим матрицу смежности для орграфа . Это квадратная матрица размера 4 4:

Матрица смежности ориентированного графа не симметрична относительно главной диагонали, как матрица смежности для неорграфа.