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

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

Надалі будемо розглядати тільки скінченні графи, у яких множини вершин 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

	І	ІІ	ІІІ	IV	V	VI	VII	VIII	IX

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

Таблиця 4

	І	ІІ	ІІІ	IV	V	VI	VII	VIII	IX
І
ІІ
ІІІ
IV
V
VI
VII
VIII
IX

Дата добавления: 2014-11-29