Представление в ЭВМ

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

Элементы матрицы смежности определяются соотношением:

Пример №1

1 2

Матрица инциденций.

Элементы матрицы инциденции для ориентированного графа определяют по формуле

В другом изложении

Пример №2 Заданы графы. Необходимо сравнить способы задания для орграфа и неографа.

Матрицы инцидентности графов G1 и G3 приведены в табл. 6.1. В матрице инцидентности в каждом столбце толь­ко два элемента, отличных от 0 (или один, если ребро-петля).

Список ребер является более компактным описанием графа. Список ребер орграфа G₃ приведен в табл. 6.3, для неографа G1 он аналогичен, однако последовательность ука­зания вершин здесь безразлична. Матрицы смежности гра­фов G1, G₃ даны в табл. 6.2.