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

Граф может задаваться следующими способами:

• — аналитически с использованием теории множеств: задаются V и U;
• — в графическом виде, называемом диаграммой: вершины отображаются кругами (точками), а связи соответствующими линиями (возможно, со стрелками);
• — в матричном виде.

Матричное задание графа позволяет его анализировать с использованием СВТ. При задании графа выделяют матрицы смежности и инцидентности.

В матрице смежности А элементы равны количеству связей (односвязных), идущих из вершины и заканчивающихся в Vj. Матрица смежности является диагональной размерности п х п; если отсутствуют связи, имеющие начало и конец в одной и той же вершине, то диагональные элементы в А равны нулю. Например, матрица смежности для графа, приведенного на рис. 8.1, равна.

Сумма элементов г-й строки равна количеству дуг, исходящих их г-й вершины (полустепень исхода вершины). Сумма элементов j-ro столбца равна, количеству дуг, входящих в j-io вершину (полустепень захода вершины).

Для графа, изображенного на рис. 8.8, элементы aij матрицы смежности А² задают количество двухсвязных путей, начинающихся в вершине Vj и заканчивающихся в вершине Vj.

Рис. 8.8. Направленный граф с двухсвязными путями.

В матрице инцидентности В элементы 6^ принимают следующие значения:

• 1. bjj = 1, если вершина t>, и дуга Uj положительно инцидентны.
• 2. bij = — 1, если вершина г?, и дуга и₃ отрицательно инцидентны.
• 3. Ь^ = 0, если вершина и дуга и₃ не инцидентны.

Матрица инцидентности для графа, изображенного на рис. 8.1, равна.

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

Контрольные вопросы

• 1. Что называется графом? Из каких элементов состоит граф? Приведите примеры использования теории графов в экономической деятельности.
• 2. Что называется путем на графе? Что называется контуром?
• 3. Что называется деревом, сетью?
• 4. Каким образом можно задать граф?
• 5. Что называется матрицами смежности и инциденций для графа?

Задания для самостоятельного решения

Задание 1. Найдите матрицы смежности и инциденций для графов, изображенных на рис. 8.9.

Рис. 8.9. Графы для построения матриц.

Задание 2. Постройте графы, заданные матрицами смежности:

Задание 3. Постройте графы, заданные матрицами инцидентности:

Задание 4. Для графов, соответствующих матрицам смежности из задания 2, найдите матрицы инцидентности.

Задание 5. Для графов, соответствующих матрицам инцидентности из задания 3, найдите матрицы смежности.