Контрольные вопросы

1. Какой граф называется планарным и плоским?

2. Какие области определяет плоский граф на поверхности?

3. Какие вершины называются контактными?

4. Что такое кусок графа? В каком случае кусок графа и грань графа совместимы.

5. Какое равенство справедливо для планарного графа?

6. Сформулировать алгоритм плоской укладки графа.

Лекция 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 называется число ⁺(v) дуг орграфа D, исходящих из вершины v.

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

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

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

V₁

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 – количество дуг.

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

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

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:

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