Представление графа в памяти эвм.

1. Графический способ представления (если граф небольшой).

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

Числовыми характеристиками графа являются: количество узлов, количество дуг, ранг графа. Ранг графа: R(G) = |X| - K, где К – количество компонентов связности графа в случае, если но не связан.

Рассмотрим матрицу смежности. Пусть задан граф G = (X, U), |X| = n. Имеем матрицу А размерности n  n, которая называется матрицей смежности, если элементы ее определяются следующим образом:

Рассмотрим применение матричной алгебры для определения характеристик графа. Выражение a _{i k}  a _{k j} означает, что между узлами i и j есть две дуги, проходящие через узел k, если значение выражения равно True.

Выражение означает, что всегда имеется путь между этими узлами длиною 2 (два), если выражение истинно.

А  А = А⁽²⁾ – логические операции заменяются арифметическими. Тогда каждый элемент a _{i j} будет давать информацию о том, есть ли путь из i в j (i, j = 1, 2,…,n).

Выражение А⁽ⁿ⁾ = А^{(n – 1)}  А означает, есть ли путь длиной n между различными узлами i. По диагонали будет характеристика, есть ли циклы (контура) в матрице.

Р = А V А⁽²⁾ V …V А⁽ⁿ⁾ =  - матрица связности. Определяется, существует ли какой-либо путь между узлами i и j. Алгоритм вычисления данного выражения:

1. Р = А;

2. повторить 3, 4 (k=1, 2,…, n);

3. повторить 4 для i=1, 2, …,n;

4. повторить Р_{i j} = Р_{i j} V (Р_{i k}  Р_{k j}), j=1, 2,…, n.

В связной памяти наиболее часто представление графа осуществляется с помощью структур смежности. Для каждой вершины множества X задается множество М(X _i) соответственно вех его последователей (если это орграф) или соседей (для неорграфа). Таким образом, структура смежности графа G будет представлять собой список таких множеств: < М(X ₁), М(X ₂),…, М(X _n)> для всех его вершин.

Р

3

2

ассмотрим пример (узлы обозначаем в виде цифр: 1, 2,…, n):

Для неорграфа:

1: 2, 3; 2: 1, 3; 3: 1, 2; 4: 5; 5: 4.

Для орграфа: 1: 2; 2: 3; 3: 1; 4: 5; 5: - .

5

G:

1

4

С

1 2 3 4 5

труктуру смежности можно реализовать массивом из n линейно связанных списков:

2

3

1

5

Представление графа может оказать влияние на эффективность алгоритма. Часто запись алгоритмов на графах задается в терминах вершин и дуг, независимо от представления графа. Например, алгоритм определения количества последователей вершин: C (X) X_i, S – количество дуг.

S = 0;

 x  X выполнить:

начало

С(x)=0;

 t  M(x) выполнить: C(x) = C(x) + 1;

S = S + C(x);

конец;

Алгоритмы прохождения графа.

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

Имеем граф G = (X, U), X = {x₁, x₂,…, x_n}. Каждое прохождение можно рассматривать как определенную последовательность. Максимальное число прохождений (перестановок) – n!.

Алгоритм прохождения графа в глубину:

9

4 6 3

8

7 5 10 5

4

3

1

2. 1

2

Цифры на ребрах графа обозначают шаги посещения. Будем различать посещаемые (  ) и не посещаемые (   ) вершины. Каждая вершина обходится два раза. Если все смежные вершины пройдены, то происходит откат в предыдущую вершину. В том случае, если из текущей вершины все соседние вершины пройдены, то осуществляем возврат к той вершине, откуда был осуществлен переход к текущей.

Определим списки смежности для каждой вершины графа G:

1 : 2, 3, 5 2: 1, 3, 4 3: 1, 2, 4, 5 4: 2, 3 5: 1,3

t : 1, 2, 3, 4, 5

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

Для каждого выбора начальной вершины в связном графе может быть получено единственное прохождение. Если граф представляет собой объединение компонент: и | x _i | = n _i , то количество прохождений такого несвязного графа: n ₁  n ₂  …  n _р ( i = 1, 2,…, p).

Пусть граф G = (X, U) задан структурой смежности < М(x ₁), М(x ₂),…, М(x _n)>. Определим Num(x) как массив для регистрации посещений вершин (Num(x)=1, если вершина не посещалась; Num(x)=0, если вершина посещалась). Тогда алгоритм прохождения графа в глубину будет выглядеть так:

 x  X выполнить Num(x)=1;

 x  X выполнить: если Num(x)=1, то D(x);

Процедура D(x);

начало

R(V);

Num(V)=0;

 t  M(V) выполнить: если Num(t)=1, то D(t);

конец;

Алгоритм прохождения графа в ширину:

Определим списки смежности для каждой вершины графа G:

1: 2, 3, 5 2: 1, 3, 4 3: 1, 2, 4, 5 4: 2, 3 5: 1,3

t: 1, 2, 3, 4, 5 (для выбранной вершины переписываем весь список смежности).

Выберем начальную вершину x _н. Первые элементы искомой перестановки t являются элементами смежного списка вершины x _н, т.е. M(x _н). Обозначим список смежности следующим образом: M(x _н) = {(w₁, x_н), (w₂, x_н),…,(w_k, x_н)}. Следующими элементами перестановки будут те элементы их M(w₁), которые отсутствуют в формируемой перестановке t. Затем, берем все элементы из M(w₂), и т.д. обход прекращается, когда все вершины, достижимые из x _н, будут содержаться в t (w_i  X, i=1, 2,…, k).