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

1. Графический.

2. В виде множеств вершин V и ребер Е, когда каждое ребро е Е, определенно парой инцидентных ему концевых вершин (ν΄ и ν˝).

3. Матрицей инцидентности Еij размера m x n: по вертикали и горизонтали указываются вершины и ребра соответственно, а на пересечении i-ой вершины и j-ого ребра в случае н-графа проставляется 1, если они инцидентны, и 0 – в противном случае:

Для орграфа:

4. Списком ребер графа, представленным двумя столбцами: в левом перечисляются все ребра еi Е, а в правом – инцидентные ему вершины νj΄, νj˝, для н-графа порядок вершин в строке произволен, для орграфа первым стоит номер начала ребра.

5. Матрицей смежности δij – квадратной матрицей размера n x n: по вертикали и горизонтали перечисляются все вершины νj V, а на пересечении к-ой и i-ой вершин в случае н-графа проставляется число, равное числу рёбер, соединяющих эти вершины.

Для орграфа проставляется число, равное числу рёбер с началом к-ой вершине и концом в i-ой.

- Графы G₁ и G₂ равны, т.е. G₁ = G₂, если их множества вершин и ребер, выраженных через пары инцидентных им вершин, совпадают: V₁ = V₂, E₁ = E₂.

Пример:

	Рис. 6.1		Рис. 6.2

	Рис. 6.3

G₅:

G₁, G₄, G₅ (рис. 6.1, 6.4, 6.5)– н-граф, G₂, G₃ (рис. 6.2, 6.3)– орграф

В G₂ ребро d – петля, ребро k– дуга (рис. 6.2).

В G₃ ребра c и d исходят из одних и тех же вершин и одинаково ориентированные. Такие ребра называют кратными, а граф – мультиграфом (рис. 6.3).

G₄ и G₅ являются дополнением друг другу (рис. 6.4, 6.5).

Пример:

G₁:

Для G₁:

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

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

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

Для G₂:

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

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

Пример:

G₃:

Для G₃:

ρ(1) = 4, ρ(2) = 5, ρ(3) = 3, ρ(4) = 4, ρ(5) = 6

m – число ребер графа G3.

Для G₄:

ρ₁(1) = 0, ρ₁(2) = 2, ρ₁(3) = 4, ρ₁(4) = 2

ρ₂(1) = 3, ρ₂(2) = 2, ρ₂(3) = 1, ρ₂(4) = 2

m – число ребер графа G₄.