logo search
Лекции ДМ

Лекция 22

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

ПЛАН:

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

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

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

  4. Связность. Компоненты связности в орграфе

Главная

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

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

Непустое множество V = {v1, v2,…,vn} и набор Х упорядоченных пар объектов (vi, vi+1) , где viV, vi+1V, называется ориентированным графом и обозначается D(V, X).

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

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

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

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

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

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

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

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

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

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

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

V1

d+(u1) = 2

d-(u1) = 0

d+(u2) = 2

d-(u2) = 3

d+(u3) = 0

d-(u3) = 1

d`+(u4) = 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.