Граф решетки

Граф решетки (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].