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

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

6.2.1. Матрица смежности графа

• Определение. Матрицей смежности ориентированного помеченного графа с вершинами называется матрица

Матрица смежности однозначно определяет структуру графа. Примеры орграфа и его матрицы смежности приведены соответственно на рис. 6.10 и рис. 6.11. Отметим, что петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1, но это не принято, обычно же представляют каждый элемент матрицы одним двоичным разрядом.

Рис. 6.10. Ориентированный граф

Рис. 6.11. Матрица смежности ориентированного графа рис. 6.10

6.2.2. Матрица инцидентности графа

• Определение. Матрицей инцидентности для неориентированного графа с вершинами и ребрами называется матрица строки которой соответствуют вершинам, а столбцы — ребрам. Элементы

• Определение. Матрицей инцидентности для ориентированного графа с вершинами и ребрами называется матрица

строки которой соответствуют вершинам, а столбцы — ребрам. Элементы

Матрица инцидентности однозначно определяет структуру графа. На рис. 6.12 представлена такая матрица для орграфа на рис. 6.10.

Рис. 6.12. Матрица инцидентности ориентированного графа

6.2.3. Матрица весов графа

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

6.2.4. Список ребер графа

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

• Интересно, что данное представление позволяет легко описать петли и кратные ребра.

6.2.5. Структура смежности графа

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

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