Граф - это сложная нелинейная многосвязная динамическая
структура, отображающая свойства и связи сложного объекта.
Многосвязная структура обладает следующими свойствами:
1) на каждый элемент (узел, вершину) может быть произвольное
количество ссылок;
2) каждый элемент может иметь связь с любым количеством дру-
гих элементов;
3) каждая связка (ребро, дуга) может иметь направление и вес.
В узлах графа содержится информация об элементах объекта.
Связи между узлами задаются ребрами графа. Ребра графа могут
иметь направленность, показываемую стрелками, тогда они называют-
ся ориентированными, ребра без стрелок - неориентированные.
Граф, все связи которого ориентированные, называется ориен-
тированным графом или орграфом; граф со всеми неориентированными
связями - неориентированным графом; граф со связями обоих типов -
смешанным графом. Обозначение связей: неориентированных - (A,B),
ориентированных - <A,B>. Примеры изображений графов даны на
рис.6.1. Скобочное представление графов рис.6.1: а).((A,B),(B,A))
и б).(<A,B>,<B,A>).
а).┌───────────────┐ б).┌───────────────┐
│ │ │ v
(A)─────────────(B) (A)<────────────(B)
Рис.6.1. Граф неориентированный (а) и ориентированный (б).
Для ориентированного графа число ребер, входящих в узел, на-
зывается полустепенью захода узла, выходящих из узела -полусте-
пенью исхода. Количество входящих и выходящих ребер может быть
любым, в том числе и нулевым. Граф без ребер является нуль-гра-
фом.
Если ребрам графа соответствуют некоторые значения, то граф
и ребра называются взвешенными. Мультиграфом называется граф,
имеющий параллельные (соединяющие одни и те же вершины) ребра, в
противном случае граф называется простым.
Путь в графе - это последовательность узлов, связанных реб-
рами; элементарным называется путь, в котором все ребра различны,
простым называется путь, в котором все вершины различны. Путь от
узла к самому себе называется циклом, а граф, содержащий такие
пути - циклическим.
Два узла графа смежны, если существует путь от одного из них
до другого. Узел называется инцидентным к ребру, если он является
его вершиной, т.е. ребро направлено к этому узлу.
Логически структура-граф может быть представлена матрицей
смежности или матрицей инцидентности.
Матрицей смежности для n узлов называется квадратная матрица
adj порядка n. Элемент матрицы a(i,j) равен 1, если узел j смежен
с узлом i (есть путь <i,j>), и 0 -в противном случае (рис.6.2).
(1) (2) (A)(B)(C)(D)
┌──>( A )───>( B )┐ (A)│ 0 1 0 0 │
│ │ │ adj = (B)│ 0 0 1 1 │
│ <──────┘ │ (C)│ 0 0 0 1 │
└────(D)<────(C)<─┘ (D)│ 1 0 1 0 │
<─────┘
Рис.6.2. Графа и его матрица смежности
Если граф неориентирован, то a(i,j)=a(j,i), т.е. матрица
симметрична относительно главной диагонали.
Матрицы смежности используются при построении матриц путей,
дающих представление о графе по длине пути: путь длиной в 1 -
смежный участок - <A,B>, путь длиной 2 - (<A,B>,<B,C>), ... в n
смежных участков: где n - максимальная длина, равная числу узлов
графа. На рис.6.3 даны путевые матирцы пути adj2, adj3, adj4 для
графа рис.6.2.
ш1
(A)(B)(C)(D) (A)(B)(C)(D) (A)(B)(C)(D)
(A)│ 0 0 1 1 │ (A)│ 1 0 1 1 │ (A)│ 1 0 1 0 │
(B)│ 1 0 1 1 │ (B)│ 1 1 1 1 │ (B)│ 0 1 0 0 │
(C)│ 1 0 1 0 │ (C)│ 0 1 0 1 │ (C)│ 0 0 1 1 │
(D)│ 0 1 0 1 │ (D)│ 0 0 1 1 │ (D)│ 0 0 1 1 │
adj2 adj3 adj4
Рис.6.3. Матрицы путей
Матрицы инцидентности используются только для орграфов. В
каждой строке содержится упорядоченная последовательность имен
узлов, с которыми данный узел связан ориетрированными (исходящи-
ми) ребрами. На рис.6.4 показана матрица инцидентности для графа
рис. 6.2.
┌────────────────┬─────────┬─────────┐
│ Узлы │ 1 │ 2 │ номера связей
├────────────────┼─────────┼─────────┤
│ A │ B │ - │
│ B │ C │ D │
│ C │ D │ - │
│ D │ A │ C │
Рис.6.4. Матрицы инцидентности