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

Графічний опис графів є незручним для їх аналізу на ЕОМ. Тому розглянемо табличні способи задання графів.

Надалі будемо розглядати тільки скінченні графи, у яких множини вершин V = {v₁, …, v_n} і ребер E = {e₁, …, e_m} є скінченними.

Визначення. Матриця суміжності вершин графу G(V) (позначається M(G) = {M_ij}) - це квадратна матриця розміру n´n, в якій M_ij - кількість ребер, які з’єднують V_i з V_j в графі G. Якщо граф G неорієнтований, то

M_ij = M_ji,

тобто матриця М є симетричною.

На рис.2 зображений деякий неорієнтований граф; відповідна матриця суміжності вершин приведена в табл.1.

Рис.2	Таблиця 1

Граф також може бути описаний за допомогою матриці інцидентності (позначається N(G) = {N_ij}), яка має n рядків (вершини) і m стовпців (ребра). Для неорієнтованого графу N_ij = 1, якщо вершина v_i інцидентна ребру e_j; в протилежному випадку - N_ij = 0.

Для орієнтованого графу N_ij = 1, якщо v_i - початкова вершина ребра e_j; N_ij = ‑1, якщо v_i - кінцева вершина ребра e_j; N_ij = 0, якщо вершина v_i не інцидентна ребру e_j.

У табл. 2 наведена матриця інцидентності для неорієнтованого графу, зображеного на рис. 2.

На рис. 3 зображений орієнтований граф, матриця інцидентності для якого наведена в табл. 3.

Неорієнтований граф без петель G може бути також описаний квадратною матрицею суміжності ребер (позначається I(G) = {I_ij}) розміром m´m, причому I_ij = 1, якщо i ¹ j і у ребер e_i і e_j є спільна вершина. В протилежному випаду - I_ij = 0.

Для графу, зображеного на рис. 2, відповідна матриця суміжності ребер приведена в табл. 4.

Таблиця 2

Рис. 3	Таблиця 3
	І	ІІ	ІІІ	IV	V	VI
	-1	-1
			-1
				-1	-1	-1

Таблиця 4