logo search
Лекции ДМ

3. Способы задания графов

Один из способов задания графа уже рассмотрен – это геометрическое изображение, т.е. диаграмма.

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

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

Пусть задан граф G(V, X), где V ={v1, v2, …, vn}, X = {x1, x2,…, xm}.

Матрицей инцидентности графа G(V, X) называется матрица размера m n, элементы которой определяются следующим образом:

В любой строке матрицы инцидентности два или один элемент не равны нулю, т.к. каждое ребро соединяет две вершины, а если ребро – петля, то вершину саму с собой.

Матрица инцидентности однозначно определяет структуру графа, что позволяет читать всю необходимую информацию о графе. Например, выявлять изолированные и висячие вершины, петли; определять степени вершин. Информация о ребрах считывается по строкам, о вершинах – по столбцам.

Составим матрицу инцидентности для графа 13.1. Это матрица размера 7 7:

В первом и четвертом столбцах по одной единице, следовательно первая и четвертая вершины – висячие; в седьмом столбце все элементы равны нулю, значит седьмая вершина изолированная.

В третьей строке только один элемент не равен нулю, следовательно третье ребро- петля.

Суммируя элементы по столбцам с учетом того, что вклад петли равен двум, можно определить степень каждой вершины.

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

Пусть задан граф G(V, X), где V ={v1, v2, …, vn}, X = {x1, x2,…, xm}.

Матрицей смежности графа G(V, X) называется квадратная матрица n n, элементы которой определяются следующим образом:

k – количество ребер, соединяющих вершины vi и vj .

Составим матрицу смежности для графа 13.1. Это квадратная матрица размера 7 7:

Матрица смежности неориентированного графа симметрична относительно главной диагонали.

Если есть не равные нулю элементы главной диагонали, то это означает наличие петель в графе. Читать информацию о графе можно и по столбцам и по строкам.

Сумма элементов верхнего или нижнего треугольника вместе с главной диагональю равна количеству ребер в графе. Для нашего графа сумма равна (учитывая только элементы не равные нулю): 1+1+1+2+1+1=7.

Далее рассматривая некоторые задачи теории графов будем использовать именно такой способ задания графа.

  1.