Представления графов

Наиболее понятный и полезный для человека способ представления графов — изображение их на плоскости в виде точек (вершин) и соединяющих точки линий (ребер). Иными словами, способ представления графа в виде картинки. Визуальное представление весьма полезно при выявлении и доказательстве тех или иных свойств графа. Однако оно не применимо для больших сетей и мало пригодно при обработке графа на электронных вычислительных машинах (ЭВМ). Хотя следует сказать, что современные ЭВМ позволяют вводить в память различные изображения и графы. Однако для того чтобы решать какую-либо задачу на графе при помощи ЭВМ, и вершины и связи между ними необходимо кодировать. Поэтому проще ввести в память ЭВМ соответствующие коды сразу, минуя картинку, изображающую граф.

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

Пусть количество вершин некоторого графа С = (V, Е) равно п, а количество ребер т.

На рис. 2.18 в качестве примера приведено два графа: один ориентированный, другой — нет. Вершины графов помечены цифрами.

2 5 3 4

Ориентированный (а) и неориентированный (б) граф

Рис. 2.18. Ориентированный (а) и неориентированный (б) граф

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

1

1

1

2

2

3

4

4

5

2

3

5

3

5

4

5

6

6

1

1

3

3

5

5

6

2

3

2

4

4

6

5

а) б)

Рис. 2.19. Списки пар вершин графов, приведенных на рис. 2.18: а — орграфа; б — неориентированного графа

Не более сложным способом представления графа (7 является его представление в виде матрицы смежности Л((7), т.е. прямоугольной таблицы чисел с п строками и п столбцами. В клетки этой таблицы записываются единицы, если вершина а смежна

2

Л(Р) = з

  • 5
  • 6

1

2

3

4

5

6

1

2

3

4

5

6

'0

1

1

0

0

0‘

1

'0

1

1

0

1

0'

0

0

0

0

0

0

2

1

0

1

0

1

0

0

1

0

1

0

0

А(С) = з

1

1

0

1

0

0

0

0

0

0

0

0

4

0

0

1

0

1

1

0

0

0

1

0

1

5

1

1

0

1

0

1

0

0

0

0

1

0

6

0

0

0

1

1

0

с вершиной Ь, т.е. между ними существует ребро или дуга, или нуль, если такой связи нет.

На рис. 2.20 приведены матрицы смежности для графов, изображенных на рис. 2.18.

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

а)

'.9

а

/ 8 Ь 0 0 0 0 0 0

  • 4 0 0 3 о о 0 6 0
  • 5 0 0 0 0 4 О 0 1 0 0 0 0 0 0 0 0 0

а

Ь

с

(1

е

/

8

И

У

V

о о о о о о о о о о о о о о о о о о о о о о

Ъ с

  • 0 о
  • 1 о

О 3

о о о о о о о о о о о о о о о о

сI е

о о

О 2

о о о о

О 8

о о о о

О 1

о о о о о о б)

У 6 о о о о о о

О 5

о о о о

О 1

о о 3 о О 2

о о

Рис. 2.21. Взвешенный граф (7 (а) и его матрица смежностей (б)

Второй метод представления графа (7 в виде матрицы — при помощи матрицы инциденций /((7) — в виде прямоугольной таблицы чисел с п строками и т столбцами (рис. 2.22). В клетку таблицы записывается единица, если вершина инцидентна ребру или дуге, т.е. если она имеет связь с другой вершиной. В противном случае в клетку записывается нуль. Для представления матрицы инциденций необходимо, чтобы ребра (дуги) графа были помечены (рис. 2.22).

  • 4 / 5
  • а)
  • 1

О

О

О

а

  • 2
  • 4
  • 0 1 0 0 0 1
  • 1 0 0 0 0 0
  • 11110 0 0 0 0 1 1 1
  • 0 0 10 10

Ь с ё е / g

Граф О (а) и соответствующая ему матрица инциденций (б)

Рис. 2.22. Граф О (а) и соответствующая ему матрица инциденций (б)

Каждый столбец матрицы инциденций /((7) содержит ровно две единицы, и столбцы не идентичны между собой. Количество клеток матрицы, заполненные нулями, равно (п -2)т. Такая матрица требует больше памяти ЭВМ, чем матрица смежности Д((7).

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

Таким образом, каждая строка матрицы — это вектор номеров вершин, называемый вектором смежности. Такое представление графа (7 называют представлением при помощи векторов смежности (рис. 2.23).

Количество столбцов матрицы векторов смежности определяется максимальным количеством компонент некоторого вектора смежности. В рассматриваемом случае это векторы 3 или 4.

Возможны другие представления графов, например, при помощи связных списков смежности. Это представление использу-

  • 4 5
  • а)
  • 2
  • 4
  • 2
  • 1
  • 3
  • 3
  • 3

О

О

5

О

  • 4
  • 1

О

Граф (7 (а) и матрица векторов смежности (б)

Рис. 2.23. Граф (7 (а) и матрица векторов смежности (б)

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

 
< Пред   СОДЕРЖАНИЕ     След >