ЛЕКЦИЯ 22

 

ТЕМА: ОРИЕНТИРОВАННЫЙ ГРАФ

ПЛАН:

1. Основные понятия
2. Способы задания ориентированного графа
3. Путь в ориентированном графе
4. Связность. Компоненты связности в орграфе

Главная

 

1. Основные понятия

Напомним определение ориентированного графа:

Непустое множество V = {v₁, v₂,…,v_n} и набор Х упорядоченных пар объектов (v_i, v_i+1) , где v_iÎV, v_i+1ÎV, называется ориентированным графом и обозначается D(V, X).

Пары х = (v, w) называются дугами и изображаются на диаграмме следующим образом:

v– начало дуги х, w – конец дуги х.

Говорят: дуга исходит из v и заходит в w .

Пусть х – дуга. Если v конец или начало дуги, то v и х инцидентны.

Вершины v и w смежны, если (v, w) Î X.

Для ориентированного графа аналогично определяются понятия: петли, кратные дуги, псевдограф, мультиграф, граф.

Рассмотрим понятия: полустепень исхода и полустепень захода:

Полустепенью исхода вершины v называется число d⁺(v) дуг орграфа D, исходящих из вершины v.

Полустепенью захода вершины v называется число d^-(v) дуг орграфа D, заходящих в вершину v.

Замечание: вклад каждой петли, инцидентной некоторой вершине v, равен 1, как в d⁺(v), так и в d^-(v).

Для орграфа, представленного на рисунке найти полустепени захода и исхода:

V1

d⁺(u₁) = 2

d^-(u₁) = 0

d⁺(u₂) = 2

d^-(u₂) = 3

d⁺(u₃) = 0

d^-(u₃) = 1

d^`+(u₄) = 0

Найдем суммы степеней исходов и сумму степеней заходов:

еd⁺(u) = 2 + 2 + 0 + 0 = 4;

еd^-(u) = 0 + 3 + 1 = 4 .

В данном графе 4 ребра. Замечаем, что еd⁺(u) = еd⁺(u) = m .Действительно, для орграфа справедливо утверждение:

Для любого ориентированного графа выполняется равенство

еd⁺(u) = еd⁺(u) = m,

где m – количество дуг.

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

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

 

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

 

Пусть задан граф 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₂ : полустепень исхода - d⁺(v₂) = 2, т.к. в соответстующем этой вершине столбце одна «-1» и еще учитываем петлю; полустепень захода - d^-(v₂) = 3, т.к в столбце две единицы и петля.

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

 

Пусть задан граф 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:

 

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

 

3. Путь в ориентированном графе

Определение: Путем , соединяющим вершины v₁ и v_k+1 , называется последовательность v₁x₁v₂x₂…v_kx_kv_k+1 , где k³ 1, v_i Î V, x_iÎ X, дуга x_i соединяет вершины v_i с вершиной v_i+1 . Вершина v₁ (v _нач)– начало пути (начальная вершина), v_k+1 (v _кон)– конец пути (конечная вершина). Остальные вершины называются внутренними вершинами пути.

Найдем какой-либо путь из v₁ в v₃ : v₁x₁v₂x₃v₂x₄v₃ .

Допускается краткая запись пути. В том случае, если в пути нет кратных дуг, то составляют последовательность только из вершин.

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

Перепишем наш путь, использую комбинированную запись: v₁x₁v₂v₂v₃. В последовательность включено только кратное ребро x₁ .

Длиной пути l называется количество дуг в нем.

В нашем пути 3 дуги, значит его длина l =3.

Познакомимся с видами путей.

Если v_нач = v_кон , то путь называется замкнутым.

Если v_нач ¹ v_кон , то путь называется незамкнутым.

Виды незамкнутых путей:

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

Цепь, в которой все вершины попарно различны называется простой цепью.

Виды замкнутых путей:

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

Контур, в котором все вершины попарно различны называется простым контуром.

Заметим, что петля являются простым контуром.

Составим различные пути для приведенного выше орграфа :

v₁x₁v₂x₃v₂x₄v₃ – незамкнутый путь, являющийся цепью (в нем все дуги попарно различны);

v₂x₃v₂ – простой контур;

v₁x₂v₂x₄v₃ – простая цепь (все вершины и дуги попарно различны).

Для графа D(V,X) справедливы утверждения:

Из любого контура можно выделить простой контур.

Из любого незамкнутого пути можно выделить простую цепь с теми же начальной и конечной вершинами.