Граф решетки

Материал из WikiGrapp
Перейти к:навигация, поиск

Граф решетки (Lattice graph) — граф, вершины которого суть пары натуральных чисел (x,y), 1 \leq x \leq m, 1 \leq y \leq n, и две вершины a = (x,y) и b = (z,t) смежны тогда и только тогда, когда |x-z| = 1 или |y-t| = 1.

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

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.