Материал: способы задания графов

1. Матрица инцидентности

Рассмотрим конечный граф G = (V, E) , V -

множество вершин, E - множество ребер.

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

ориентированного графа G с числом вершин n

и числом ребер m называется матрица B

размерности n x m с элементами:

1. Матрица инцидентности

Для ориентированного графа без петель каждый столбец матрицы инцидентности содержит 1 и −1, соответствующие началу и концу данного ребра. Если ориентированный граф содержит петли, то в столбцах матрицы, соответствующих петлям, имеется только одно число α , отличное от 1, −1 и 0.

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

Рассмотрим конечный граф G = (V, E) , V -

множество вершин, E - множество ребер.

Матрицей смежности неориентированного графа G с числом вершин n называется

квадратная матрица А порядка n с элементами:

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

-Матрица смежности неориентированного

графа в силу симметричности отношения смежности является симметрической

относительно главной диагонали.

-Матрица смежности нулевого графа есть

нулевая матрица.

-Полный простой граф будет иметь матрицу

смежности, у которой на главной диагонали

стоят 0, а в остальных местах 1, так как

каждая вершина должна быть соединена с

любой другой вершиной только один раз.

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

Рассмотрим конечный граф G = (V, E) , V -

множество вершин, E - множество ребер.

Матрицей смежности ориентированного графа G с числом вершин n называется

квадратная матрица А порядка n с элементами:

Для ориентированного графа матрица смежности в общем случае симметрической не

является.