B f c b d e d b f d

Здесь с помощью стрелок изображены ссылки на элементы массива B, с которых начинаются вхождения списков L (v ₁) - L (v _n).

ИЗОМОРФИЗМ ГРАФОВ

Рассмотрим графы, изображенные на рис. 5.4.

a b 1 2

e f 3 4

G ₂

g h 5 6

G ₁ 7 8

C d

Рис. 5.4

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

Графы G ₁ и G ₂ называются изоморфными графами. Приведем точное определение понятия изоморфизма.