Логическая структура, определения

Граф - это сложная нелинейная многосвязная динамическая

структура, отображающая свойства и связи сложного объекта.

Многосвязная структура обладает следующими свойствами:

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. Матрицы инцидентности