5. Элементы теории графов

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

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

При этом природа зависимостей компонент систем может быть произвольной для конкретных систем в разных областях деятельности.

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

1. Транспортные сети. Компонентами таких систем являются отдельные населенные пункты или строения, а связями  указание на наличие дорог, которые их соединяют.

2. Молекулы химических соединений. Частями таких систем являются отдельные атомы, составляющие молекулы, а связями  химические соединения между атомами.

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

4. Административный аппарат учреждения. Здесь частями являются отдельные должностные лица, а связи указывают на наличие должностной подчиненности между сотрудниками учреждения.

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

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

Изображение системы, для которой выполнены перечисленные условия, называется геометрической реализацией этой системы.

Пример. Возможна следующая система подчиненности по службе сотрудников аппарата управления некоторой фирмы (рис.5.1.):

Директор

Главный Начальник Референт

менеджер отдела по правовым

маркетинга вопросам

Менеджер Менеджер

Рис. 5.1.

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

Графом называется всякая пара G = (V, U), в которой V  это конечное множество, называемое множеством вершин графа, а U  конечное множество ребер графа.

Всякое ребро графа представляется либо одной парой вершин (а,b), либо двумя противоположными парами (a,b) и (b,a). Если ребро из U представляется только одной парой (a, b), то оно называется ориентированным ребром, ведущим из a в b. При этом a называется началом, а b концом такого ребра.

Если ребро u представляется двумя парами (a, b) и (b, a), то u называется неориентированным ребром. Всякое неориентированное ребро между вершинами a и b ведет как из a в b, так и обратно. При этом вершины a и b являются как началами, так и концами этого ребра. Говорят, что ребро ведет как из a в b, так и из b в a.

Всякие две вершины, которые соединяются ребром, называются смежными.

Будем рассматривать только такие графы, у которых все ребра разные и не допускается одновременная связь одной и той же пары вершин ориентированным и неориентированным ребром или парой противоположно ориентированных ребер. Графы, которые допускают возможность нескольких ребер, соединяющих пары вершин, называются мультиграфами. Такие графы в данном учебном пособии не рассматриваются.

(В последнем случае соответствующая пара ребер будет рассматриваться как одно неориентированное ребро.)

Тогда ребра графов можно представлять просто парами вершин вида (a, b), для которых дополнительно указывается; является ли ребро ориентированным или нет. В этом случае число ребер графа совпадает с числом пар вершин, которые представляют собой ребра графа.

Поэтому в дальнейшем будем считать, что U  это множество пар вершин. При этом каждое ребро представляется одной парой вершин или двумя парами. То есть, если G = (V, U) и пара (a, b) представляет ребро графа G, то допустима запись (a, b)  U.

Замечание. Можно считать, что перечисленные условия запрещают любое дублирование ребер. Введенные ограничения не приводят к ограниченности проводимого ниже изучения графов, определения и результаты которого могут быть перенесены или обобщены на случай графов, имеющих произвольные количества ребер между парами вершин. При представлении графов с кратными ребрами можно считать, что любая пара вершин в них соединена не более чем одним ребром, которому сопоставлена числовая характеристика, равная кратности ребер между парами вершин. Такая характеристика ребер оказывается полезной в случаях, когда представляемые ребрами связи относятся к разным классам или снабжены дополнительной информацией о длине, стоимости или пропускной способности.

Ребро, у которого вершины начала и конца совпадают, называется петлей.

Число ребер, выходящих из некоторой вершины a и отличных от петель, называется степенью этой вершины и обозначается как d(a). Вершина a для которой выполнено равенство d(a) = 0, называется изолированной.

Граф, все ребра которого неориентированные, называется неориентированным графом.

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

Рассмотрим пример геометрического задания графа, приведенный на рис. 5.2.:

a

b

v

e

c d

Рис. 5.2.

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

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

Рассмотрим основные способы заданий графов с помощью специальных структур.