Граф решетки

Материал из WEGA
Версия от 16:04, 8 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Граф решетки''' (''Lattice graph'') - граф, вершины которого суть пары натуральных ч...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

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

Литература

[Лекции]