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

Глава 3. НАПРАВЛЕННЫЕ ГРАФЫ

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

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

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

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

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

· матричный;

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

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

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

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

	Определения

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

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

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

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

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

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

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

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

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