Матрица инцидентности и списки ребер

Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности. Когда граф конечен для описания его вершин и ребер достаточно их занумеровать. Отношение инцидентности определяют матрицей _ij, имеющей m строк и n столбцов. Столбцы соответствуют вершинам графа, строки – ребрам графа. Если ребро е_iинцидентно вершине v_j, то _ij= 1, в противном случае _ij= 0. Это матрица инцидентности для неориентированного графа.

Пример (Задание №9)

Обозначим вершины римскими цифрами, а ребра – арабскими. Матрица инцидентности для данного графа выглядит следующим образом:

I	II	III	IV	V	VI	VII

В матрице инцидентности орграфа _ij= -1, если вершина v_j – начало дуги a_i; _ij= 1, если v_j – конец дуги a_i; если a_i – петля, а v_j – инцидентная ей вершина, то _ij= а, где а – любое число отличное от 0, 1, -1. В остальных случаях _ij= 0.

Пример (Задание №10): построим ориентированный граф и матрицу инцидентности для нее:

Из матрицы инцидентности мы видим, что в каждой строке есть только два элемента (или один, если ребро является петлей) отличных от 0. Поэтому такой способ задания графа посчитали неэкономичным. Отношение инцидентности можно задать так же с помощью списков ребер графа. Каждая строка этого списка соответствует ребру, в ней записывают номера вершин, инцидентных ему. Для неориентированного графа порядок вершин в строке произволен, а для орграфа первым записывают номер вершины начала дуги, а вторым – номер вершины конца дуги.

Составим списки ребер для данных графов:

Таб. 8 Списки ребер неориентированного графа

Таб. 9 Списки ребер орграфа

Ребра	Вершины	Ребра	Вершины
	I, II		I, II
	I, III		I, III
	II, IV		II, IV
	I, V		III, V
	II, VI		III, IV
	III, IV		III, VII
	III, V		VI, VII
	IV, VI
	V, VII
	VI, VII