Граф решетки: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Граф решетки''' (''Lattice graph'') - граф, вершины которого суть пары натуральных ч...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Граф решетки''' (''Lattice graph'') | '''Граф решетки''' (''[[Lattice graph]]'') — [[граф]], [[вершина|вершины]] которого суть пары натуральных чисел <math>(x,y), 1 \leq x \leq m, 1 \leq y \leq n</math>, и две вершины <math>a = (x,y)</math> и <math>b = (z,t)</math> [[смежные вершины|смежны]] тогда и только тогда, когда <math>|x-z| = 1</math> или <math>|y-t| = 1</math>. | ||
граф, вершины которого суть пары натуральных чисел <math>(x,y), 1 \leq x | |||
\leq m, 1 \leq y \leq n</math>, и две вершины <math>a = (x,y)</math> и <math>b = (z,t)</math> | |||
смежны тогда и только тогда, когда <math>|x-z| = 1</math> или <math>|y-t| = 1</math>. | |||
Иногда такой граф называют ''графом двумерной целочисленной | Иногда такой граф называют ''[[граф двумерной целочисленной решетки|графом двумерной целочисленной решетки]]'' или просто ''[[двумерная целочисленная решетка|двумерной целочисленной решеткой]]''. | ||
решетки'' или просто ''двумерной целочисленной решеткой''. | |||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
Текущая версия от 16:54, 1 февраля 2011
Граф решетки (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].
Иногда такой граф называют графом двумерной целочисленной решетки или просто двумерной целочисленной решеткой.
Литература
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.