ГРАФЫ

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Граф состоит из множества узлов и множества дуг. Каждая дуга в графе указывается парой узлов.

Примеры графов приведены на рис. 4.1:

Неориентированный в1 и ориентированный в2 графы

Рис. 4.1. Неориентированный в1 и ориентированный в2 графы

В графе в1 множество узлов — {А, В, С, О, Е, Е, в, Н}, множество дуг - {(А, В), (А, О), (А, С), (С, О), (С, Р), (Е, О), (А, А)}.

Дуга, соединяющая узел с самим собой, называется петлей. Узел может не иметь связанных с ним дуг (узел Н графа в2).

Если пары узлов, образующих дугу, упорядочены, то граф называют ориентированным, или направленным, графом (граф в2 — ориентированный); дуги в этом случае изображают стрелками.

В этой теме мы будем рассматривать только ориентированные графы без петель.

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

Степень узла — это число дуг, инцидентных узлу.

Полустепень захода узла — это число дуг, входящих в узел, а полу-степень исхода узла — это число дуг, выходящих из узла. Например, узел С графа в 2 имеет полустепень захода 2, полустепень исхода 1 и степень 3.

Узел п называется смежным с узлом т, если существует дуга из т в п.

Часть графа — это граф, содержащий часть узлов исходного графа и часть (любую) его дуг.

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

Суграф содержит все узлы исходного графа и часть его дуг. Примеры графов приведены на рис. 4.2.

Граф Часть графа Подграф

вЗ в4 в5

Суграф

вб

Примеры графов

Рис. 4.2. Примеры графов

Граф называется полным, если любые два его различных узла соединены дугой. Например, графы вЗ и в5 полные.

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

С каждой дугой графа может быть связано некоторое значение, как в графе в2. Такой граф называется взвешенным графом, а связанное с каждой дугой значение называется весом.

Путь от узла а до узла Ь — это последовательность узлов п0, п{,..., пк такая, что щ=а, пк и для любого / от 0 до к -1 узел пм смежен узлу , т.е. существует дуга из я, в я/+1.

Длина пути п0, ..., пк равна количеству его дуг, то есть к. Напри

мер, в графе в7 (см. рис. 4.3) путь А, В, С, Э имеет длину 3 и соединяет узлы А и О.

Граф С1

Ориентированный связный граф

Рис. 4.3. Ориентированный связный граф

Длина пути во взвешенном графе равна сумме весов дуг, входящих в этот путь.

Путь, не содержащий одинаковых узлов (за исключением, может быть, п0 = пк), называется простым.

Путь от узла к самому себе, не содержащий одинаковых дуг, называется циклом. Если граф содержит цикл, то он называется циклическим, в противном случае — ациклическим.

Расстояние между двумя узлами — это длина кратчайшего пути, соединяющего эти узлы.

Граф называется связным, если для любой пары узлов существует соединяющий их путь. Например, граф вЗ связный, а графы 04— вб — нет. Очевидно, что ориентированный граф не будет связным, если в нем есть узлы, не имеющие входящих или исходящих дуг. Неориентированный граф несвязный, если он содержит узлы, не имеющие инцидентных с ним дуг.

Связный ориентированный граф без петель называется сетью.

 
< Пред   СОДЕРЖАНИЕ     След >