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

В общем виде задать граф – значит описать множества его вершин и ребер, а также отношения инцидентности. Для описания вершин и ребер, достаточно их занумеровать: u₁ … u_n и ℓ₁…ℓ _m.

Отношение инцидентности задается:

1. Матрицей инцидентности (ε_ij)_{m x n}

для н-графа:

0, в противном случае,

а в случае орграфа: -1 – если вершина является началом ребра. 1 – конец, 0 – нет инцидентности; если вершина содержит петлю – то проставляется 2:

-1 - u_j начало ℓ_i,

2 - если ℓ_i – петля,

0 в остальных случаях.

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

3. Матрицей смежности (δ_ке).

Перечисляются вершины, на пересечении к и е – число ребер соединяющих элементы, для орграфа – число ребер с началом в к и концом в е.

Если два графа равны, то их матрицы смежности совпадают.

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

Пример 4. Задать графы из примера 3 с помощью перечисленных спообов.

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

список ребер: матрицы смежности:

Пример 5. Рассмотрим примеры задания графов(рисунок 12). На рисунке изображен сетевой граф (модель) выполнения комплекса операций некоторой программы, где → операции, а ○ - события, характеризующие окончание одних работ и начало других

направленность стрелок отражает последовательность наступления этих событий

Рисунок 12.

1) графически

2) с помощью задания двух множеств

V = {1, 2. …, 6} E = {(1, 2), …, (5, 6)}

3) матрица инцидентности матрица смежности

Пример 6. Задать различными способами G₁ и G₂(рисунок 13). Как вычислить число вершин и число ребер по матрицам и списку ребер?

Рисунок 13.