Глава 3. Направленные графы

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

Основные способы определения направленных графов:

• графический;

• с помощью множеств;

• последовательность полустепеней;

• матричный;

• таблицы инцидентности.

3.1.1. Графический способ задания

направленного графа

Направленный граф изображается на плоскости некоторым количеством точек (кружков) и каким-то числом направленный отрезков, кривых или прямых линий соединяющих эти точки. Кружки называются вершинами, а направленные линии (линии со стрелками) –дугами. У дуги различаютхвост(конец линии без стрелки) иголову (конец линии со стрелкой).

Определения

Дуга, соединяющая вершину саму с собой, называется петлей.

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

Контрнаправленными дугами будут дуги, соединяющие две вершины, но имеющие противоположное направление.

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

Тип	Наличие
	петель	кратных дуг	контрнаправленных дуг
Направленный граф(диграф) Ориентированный граф (орграф) Направленный мультиграф Направленный псевдограф Направленный пседомультиграф	Нет Нет Нет Да	Нет Нет Да Нет Да		Да Нет Да Да Да

1. Дуги направленного графа показывают не только связь между двумя вершинами, или ее отсутствие, но и направление этой связи (например, направление передачи информации, сигналов, товаров, топлива, грузов и т.д.).

2. Направленные графы будут называться диграфами(от английскогоdirectedgraphs), а ориентированные графы –орграфами(orientedgraphs).

3. Далее простые направленные графы и ориентированные графы будут называться общим именем «диграфы». Только в особо оговариваемых случаях будет использоваться название «орграф».

Пример

c)

Рис.3.1.1. Типы направленных графов: a) простой направленный граф (диграф);b) ориенитрованный граф (орграф); с) направленный мультиграф;d)направленный пседограф;e)направленный псевдомультиграф

3.1.2. Задание диграфов с помощью множеств

Определения

ДиграфомD(V,A) является:

• конечное непустое множество V вершин;

• конечное множество А дуг, задаваемое функцией декартового произведения вершинVV( т.е. у диграфа {v_i,v_j}≠{v_j,v_i}. Если имеется дуга е={v_i,v_j}, то говорят, что дуга направлена из вершиныv_iв вершинуv_j.)

Диграф D=(V,A) называется пустым, если |V|=0, |A|=0. Тривиальный диграф – это диграф D=(V,A) с |V|0 и |A|=0.

Две вершины, соединенные дугой любого направления, являются смежными.

Говорят, что:

• вершина vинцидентна к дуге {v,u}, если голова дуги соединена с вершинойv;

• вершина vинцидентна от дуги {v,u}, если хвост дуги соединен с вершинойv;

• дуга {v,u}инцидентна к вершинеv, если голова дуги соединена с вершинойv;

• дуга {v,u}инцидентна от вершиныv, если хвост дуги соединен с вершинойv.

Рис.3.1.3. Смежные вершины, инцидентные вершины и дуги диграфа

• |D| - порядок диграфа: число вершин диграфа D;

• ||D||-размер диграфа: число дуг диграфа.

Диграф будет конечным или бесконечным в зависимости от величины порядка диграфа |D|.