Решітка (теорія графів)

Граф решітки — граф, зображення якого, вкладене в деякий евклідів простір Rⁿ, утворює ^[en]. Це означає, що група бієктивних перетворень, переводить граф в себе, є ґратами у теоретико-груповому сенсі.

Зазвичай не робиться явної відмінності між такими графами у більш абстрактному сенсі теорії графів і малюнком у просторі (часто на площині або тривимірному просторі). Цей тип графів можна коротко називати просто ґратами. Проте той же термін зазвичай використовується для кінцевих частин нескінченних графів, як, наприклад, «8×8 квадратна решітка».

Термін решітка в літературі дається для різних інших видів графів з деякою регулярною структурою, такою як прямий добуток графів деякого числа повних графів.

Графи квадратної решітки

Загальний вигляд графа решітки (відомої під різними іменами, такими як граф квадратної решітки) — це граф, вершини якого відповідають точкам на площині з різними координатами, x-координатами з діапазону 1,…, n, y-координатами з діапазону 1,…, m, і вершини якого з'єднані ребром, якщо відповідні точки знаходяться на відстані 1. Іншими словами, це граф одиничних відстаней для зазначених точок.

Властивості

Граф квадратної решітки — це прямий добуток графів, а саме двох шляхів з n — 1 і m — 1 ребрами. Оскільки шлях — це , граф квадратної решітки є також медіанним. Всі графи решіток є двочастковими.

Шлях теж можна вважати графом решітки n на 1. Граф решітки 2x2 — це 4-цикл.

Примітки

1. Weisstein, Eric W. Lattice graph(англ.) на сайті Wolfram MathWorld.
2. Weisstein, Eric W. Grid graph(англ.) на сайті Wolfram MathWorld.