Способы представления графов в компьютере

Граф G(X,U) может быть полностью определен простым перечислением множеств Х и U. Однако, в большинстве случаев этот метод представления графов не позволяет быстро ответить на вопрос, обладает или не обладает граф различными свойствами. Имеется много разнообразных методов представления графов в памяти ЭВМ. Какого-то одного лучшего метода нет: лучшее представление зависит от специфики решаемой задачи.

Матрица смежности.Любой граф G(X,U) с N вершинами может быть представлен матрицей NxN. Матрица смежности A(G) определяется следующим образом:

A(G)=[ a(ij) ], где a(ij)=1, если вершина x(i) смежная с вершиной x(j), и a(ij)=0, в противном случае.

Если G(X,U) - взвешенный граф, то элемент a(ij) равен весу ребра между вершинами x(i) и x(j).

Рис.2.4.14. Граф и его матрица смежности

На рисунке 2.4.14 приведен граф и его матрица смежности. Заметим, что для неориентированного графа G(X,U) матрица A(G) всегда будет симметричной матрицей (0,1) с нулями по диагонали, а степень вершины x(i) равна числу единиц либо в i-й строке, либо в i-м столбце матрицы A(G).

Матрица инцидентности.Второй метод представления графа использует матрицу инцидентности I(G). Матрица инцидентности NxM (М - количество ребер графа) определяется следующим образом:

I(G)=[ b(ij) ], где b(ij)=1, если вершина x(i) инцидентна ребру u(j), и b(ij)=0 в противном случае.

На рисунке приведена матрица инцидентности I(G) графа G(X,U).

Рис. 2.4.15. Граф и матрица инцидентности.

Заметим, что каждый столбец матрицы I(G) содержит ровно две единицы и никакие два столбца не идентичны, а также, что число единиц в i-й строке равно степени для i-й вершины графа G(X,U). Матрица инцидентности полезна для решения различных сетевых задач.

Векторы смежности.Вместо представления графа матрицами (0,1) можно воспользоваться матрицей, в которой элементы соответствуют непосредственно номерам вершин х(1),х(2),...х(n). В такой матрице i-я строка содержит вектор, компонентами которого являются все вершины, смежные с x(j). Порядок элементов в таком векторе, называется вектором смежности и обычно определяется порядком, в котором представлены ребра в G(X,U). На рис... приводится граф G(X,U), список его ребер в случайном порядке и представление графа в форме вектора смежности. Размер матрицы, содержащей векторы смежности, никогда не превышает NxD, где D - максимальная степень вершины из G(X,U).

Рис. 2.4.16. Граф, перечень ребер и вектор смежности.

Дерево, каждый узел которого может быть представлен одним и тем же типом записи, называется однородным (например, генеалогическое дерево). На рис... изображено дерево, обход которого в соответствии с указанной нумерацией узлов позволяет получить алгебраическое выражение: а1*а2 - а3 + а4/а5

Рис.2.4.17. Дерево алгебраического выражения

Рис. 2.4.18. Неоднородное дерево, отображающее иерархическую структуру

данных.

В неоднородных деревьях каждый узел представлен различным типом данных (рис. 15).

Дерево, в котором каждый узел имеет одинаковое число ветвей, является сбалансированным. Сбалансированное n-уровневое дерево, в котором (n-1)-й уровень заполнен полностью, называется симметричным (рис. 16).

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

а) Сбалансированное дерево

б) Бинарное дерево

Рис. 2.4.18

Вопросы:

1. Что называется графом? Ориентированным графом?

2. Что называется вершинами графа? Ребрами графа?

3. Какие ребра и какие вершины называются смежными?

4. Какой граф называется мультиграфом? Двудольным графом?

5. Что называется разрезом графа?

6. Что называется петлей? цепью? циклом? путем в графе?

7. Какой граф называется деревом?

8. Что называется степенью вершины графа? Что называется полустепенями исхода и захода вершины графа?

9. Какой граф называется сетью?

10. С помощью каких матриц можно задать граф?

11. Определите понятие потока в сети?

12. Какие виды деревьев бывают?