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

ДИСКРЕТНАЯ МАТЕМАТИКА

ГРУППЫ 1/42, 1/147, 1/184

Ксенофонтова Ольга Леонидовна

ТЕОРИЯ ГРАФОВ

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

лекция

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

Задать граф – значит описать множества его вершин и ребер, а также отношение

Граф задают:

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

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

3)Списком ребер

4)Рисунком

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

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

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

Матрицей инцидентности неориентированного графа G с числом

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

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

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

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