С помощью списка ребер

Для ориентированного графа.

Для неориентированного графа.

С помощью матрицы инцидентности.

Рис.21. Неориентированный граф Рис.22. Ориентированный граф

Пусть V₁, V₂,…V_n – вершины графа G. Отношение инцидентности задается матрицей / ξ_ij /, имеющая m – строк и n – столбцов.

Столбцы соответствуют вершинам графа, а строки – ребрам.

Если ребро е_i инцидентно вершине V_j, то ξ_ij = 1.

В противном случае ξ_ij = 0.

Если вершина V_j – начало ребра е_i, то ξ_ij = -1. Если вершина V_j – конец ребра е_i, то ξ_ij = 1.

Если - е_i петля, а V_j - инцидентная вершина, то ξ_ij = α, где α – любое число отличное от 0, 1 и -1.

Во всех остальных случаях ξ_ij = 0.

Для неориентированного графа: Для ориентированного графа:

Таблица 15 Матрица инцидентности Таблица16 Матрица инцидентности

неориентированного графа ориентированного графа

Каждая строка списка соответствует ребру, в ней записаны номера вершин, инцидентных этому ребру. Для неориентированного графа порядок вершин произволен; Для ориентированного графа – первым стоит номер начала ребра, а вторым – номер его конца.

Для неориентированного графа: Для ориентированного графа:

Таблица 17 Список рёберТаблица 18 Список рёбер

для неориентированного графа для ориентированного графа

Дата добавления: 2015-06-27