Тема 11. Матрица смежности, матрица инцидентности. Операции над графами. Представление графов в ЭВМ.

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

Определение 11.1. Представление графа с помощью квадратной матрицы, отражающей смежность вершин М:array [1..p,l..p] of [0..1] называется матрицей смежности, где

М[i ,j] =

Определение 11.2. Представление графа с помощью матрицы H:array [1..p, 1..q] of [0..1], отражающей инцидентность вершин и ребер, называется матрицей инциденций.

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

H [i, j] =

Для ориентированного графа используют матрицу Н:array [1..p, 1..p] of [-1..1]

H [i ,j] =

Операции над графами позволяют образовывать новые графы из нескольких более простых. В этом параграфе будут рассмотрены операции на графах без параллельных ребер (дуг).

Операции над графами: