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

Возможны следующие различные способы задания графа. 1. Указанием множества вершин и множества ребер (дуг) — аналитический способ.

Пусть граф G (V, Е), изображенный на рис. 3.14, задан списком вершин и ребер:

2. Посредством графического изображения — геометрический способ (см. рис. 3.14).

Использз’ется в случае небольшого количества ребер и вершин. При большом их числе рисунок теряет свою наглядность.

Рис. 3.14. Пример задания графа геометрическим способом.

3. При помощи матрицы смежности. Матрицей смежности ориентированного помеченного графа с вершинами называется матрица А = [a,-,], i, j = 1, …, п, строки которой соответствуют вершинам, а столбцы — ребрам, в которой:

Ujj = 1, если существует ребро (х), х,);

(ijj = 0, если вершины х, Xj не связаны ребром.

Пример 3.4. Для графа, изображенного на рис. 3.15, составим матрицу смежности (табл. 3.3).

Рис. 3.15. Граф (пример 3.4).

Таблица 3.3

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

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

• 4. При помощи матрицы инцидентности. Матрицей инцидентности для неориентированного графа с п вершинами и т ребрами называется матрица В — [ h_i;|; i = 1, …, гг, j = 1, …, т, строки которой соответствуют вершинам, а столбцы — ребрам:
  • • bjj= 1, если вершина х, инцидентна ребру и-,
  • • bjj = 0, если вершина х_; не инцидентна ребру ц,.

Матрицей инцидентности ориентированного графа с п вершинами и т ребрами называется матрица В = i=l,…, n;j = 1, …, т, строки которой соответствуют вершинам, а столбцы — ребрам:

• • bjj = +1, если вершина х, — начальная вершина ребра и-,
• • bj = -1, если вершина х₍ конечная вершина ребра и-,
• • bjj = 0, если вершинах, не инцидентна ребру Uj.

Пример 3.5. Неориентированный граф и его матрица инцидентности представлены на рис. 3.16 и в табл. 3.4.

Таблица 3.4

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

Рис. 3.16. Пример неориентированного графа (пример 3.5)

Пример 3.6. Ориентированный граф и его матрица инцидентности представлены на рис. 3.17 и в табл. 3.5.

Рис. 3.17. Пример ориентированного графа (пример 3.6)

Таблица 3.5

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

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