"Чистая"
и прикладная математика

Структуры данных для представления графа в памяти ЭВМ

Матрицы смежности

Матрицы инцидентности

Списки инцидентности

Преимущества и недостатки каждого способа

Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.

В связи с широким применением графов в программировании и информационных технологиях вообще возникает вопрос о представлении графа в виде структуры данных. Различные способы представления графов в памяти компьютера отличаются объёмом занимаемой памяти и скоростью выполнения операций над графами.

Наиболее часто используются три такие структуры данных - матрица смежности, матрица инцидентности и список инцидентности.

Матрицы смежности

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

Матрица смежности S - это квадратная матрица, в которой и число строк, и число столбцов равно n - числу вершин графа. В ячейки матрицы смежности записываются некоторые числа в зависимости от того, соединены соответствующие вершины рёбрами или нет, и от типа графа.

Матрица смежности для неориентированного графа

Элемент матрицы смежности sij неориентированного графа определяется следующим образом:

- равен единице, если вершины vi и vj смежны;

- равен нулю, если вершины vi и vj не смежны.

Если для элемента матрицы vij имеет место i = j, то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.

Пример 1. Составить матрицу смежности для графа, представленного на рисунке ниже.

неориентированный граф, для которого требуется составить матрицу смежности

Ответ.

V12345
101100
210011
310001
401000
501100

Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.

Матрица смежности для ориентированного графа

Элемент матрицы смежности sij ориентированного графа определяется следующим образом:

- равен единице, если из вершины vi в вершину vj входит дуга;

- равен нулю, если из вершины vi в вершину vj дуга не входит.

Как и для неориентированных графов, так и для ориентированных, если для элемента матрицы vij имеет место i = j, то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.

Пример 2. Составить матрицу смежности для графа, представленного на рисунке ниже.

ориентированный граф, для которого требуется составить матрицу смежности

Ответ.

V12345
101000
201000
310000
401000
501100

Таким образом, матрица смежности ориентированного графа не симметрична.

Матрица смежности для графа с кратными рёбрами

Если в графе есть вершины, соединённые между собой несколькими рёбрами, то элемент матрицы смежности sij равен числу рёбер, соединяющих вершины vi и vj. Из этого следует, что если вершины vi и vj не соединены рёбрами, то элемент матрицы смежности sij равен нулю.

Пример 3. Составить матрицу смежности для графа, представленного на рисунке ниже.

граф с кратными рёбрами, для которого требуется составить матрицу смежности

Ответ.

V12345
103200
230011
320001
401000
501100

Матрица смежности для взвешенного графа

В случае взвешенного графа элемент матрицы смежности sij равен числу w, если существует ребро между вершинами vi и vj с весом w. Элемент sij равен нулю, если рёбер между вершинами vi и vj не существует.

Пример 4. Составить матрицу смежности для графа, представленного на рисунке ниже.

взвешенный граф, для которого требуется составить матрицу смежности

Ответ.

V12345
1011900
2110058
390002
405000
508200

Матрицы инцидентности

Матрица инцидентности H - это матрица размера n x m, где n - число вершин графа, m - число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы - рёбрам графа.

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

Элемент матрицы инцидентности для неориентированного графа hij определяется следующим образом:

- равен единице, если вершина vi инцидентна ребру ej;

- равен нулю, если вершина vi не инцидентна ребру ej.

Пример 5. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

неориентированный граф, для которого требуется составить матрицу инцидентности

Ответ.

V1-21-32-42-53-5
111000
210110
301001
400100
500011

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

Элемент матрицы инцидентности для ориентированного графа hij определяется следующим образом:

- равен минус единице, если вершина vi является началом ребра ej;

- равен единице, если вершина vi является концом ребра ej;

- равен нулю, если вершина vi не инцидентна ребру ej.

Пример 6. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

ориентированный граф, для которого требуется составить матрицу инцидентности

Ответ.

V1-21-32-42-53-5
11-1000
2-10-1-10
30100-1
400100
500011

На сайте есть пример реализации на языке программирования С++ алгоритма обхода в глубину графа, представленного матрицей инцидентности.

Списки инцидентности

Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.

Список инцидентности одной вершины графа включает номера вершин, смежных с ней.

Ссылки на начало этих списков образуют одномерный массив, индексами которого служат номера вершин графа.

Пример 7. Составить списки инцидентности для графа, представленного на рисунке ниже.

граф, для которого требуется составить списки инцидентности

Ответ.

1:2→3
2:1→4→5
3:1→5
4:2
5:2→3

Преимущества и недостатки каждого способа

Матрицы смежности и инцидентности целесообразнее использовать когда:

  • число вершин графа невелико;
  • число рёбер графа относительно большое;
  • в алгоритме часто требуется проверять, соединены ли между собой две вершины;
  • в алгоритме используются фундаментальные понятия теории графов, например, связность графа.

Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях графов.

Списки инцидентности целесообразнее использовать когда:

  • число вершин графа велико;
  • число рёбер графа относительно невелико;
  • граф формируется по какой-либо модели;
  • во время действия алгоритма часто требуется модифицировать граф;
  • в алгоритме часто используются локальные свойства вершин, например, например, окрестности вершин.

На практике списки чаще используются в прикладных целях.

Весь блок "Теория графов"