3.3Матричная форма записи графа

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

Граф можно задать матрицей смежности

V = ||v_ij||, где (3.2)

v_ij = 1, если граф содержит ребро (i, j);

v_ij = 0, в противном случае.

Например, граф структурной схемы системы менеджмента качества, изображенный на рис.3.2 можно представить в виде следующей матрицы смежности.

			О	Р	Ц	И	Т	У	П
		О	0	1	0	0	0	0	0
		Р	0	0	1	0	0	0	0
		Ц	0	0	0	1	0	1	0
V	=	И	1	0	0	0	0	0	0	(3.3)
		Т	0	0	1	0	0	0	0
		У	0	0	0	0	0	0	1
		П	0	0	0	0	1	0	0

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

Используются и другие формы матричной записи графов. Например, в виде матрицы инциденций

W = ||w_ij||, где (3.4)

1, если i – начальная вершина ребра (i, j);

w_ij = -1, если i – конечная вершина ребра (i, j);

0. в остальных случаях.

Например, для графа на рис.3.2 матрица инциденций будет выглядеть следующим образом.

			(О,Р)	(Р,Ц)	(Ц,И)	(И,О)	(Т,Ц)	(Ц,У)	(У,П)	(П,Т)
		О	1			-1
		Р	-1	1
		Ц		-1	1		-1	1
W	=	И			-1	1
		Т					1			-1
		У						-1	1
		П							-1	1

Если граф не ориентирован, то матрица инциденций содержит только 0 и 1.

w_ij = 1, если имеется ребро (i, j);

w_ij = 0 в обратном случае.