Решітка (теорія графів)
Граф решітки — граф, зображення якого, вкладене в деякий евклідів простір Rn, утворює регулярну мозаїку[en]. Це означає, що група бієктивних перетворень, переводить граф в себе, є ґратами у теоретико-груповому сенсі.
Зазвичай не робиться явної відмінності між такими графами у більш абстрактному сенсі теорії графів і малюнком у просторі (часто на площині або тривимірному просторі). Цей тип графів можна коротко називати просто ґратами. Проте той же термін зазвичай використовується для кінцевих частин нескінченних графів, як, наприклад, «8×8 квадратна решітка».
Термін решітка в літературі дається для різних інших видів графів з деякою регулярною структурою, такою як прямий добуток графів деякого числа повних графів[1].
Загальний вигляд графа решітки (відомої під різними іменами, такими як граф квадратної решітки) — це граф, вершини якого відповідають точкам на площині з різними координатами, x-координатами з діапазону 1,…, n, y-координатами з діапазону 1,…, m, і вершини якого з'єднані ребром, якщо відповідні точки знаходяться на відстані 1. Іншими словами, це граф одиничних відстаней для зазначених точок[2].
Граф квадратної решітки — це прямий добуток графів, а саме двох шляхів з n — 1 і m — 1 ребрами[2]. Оскільки шлях — це медіанний граф, граф квадратної решітки є також медіанним. Всі графи решіток є двочастковими.
Шлях теж можна вважати графом решітки n на 1. Граф решітки 2x2 — це 4-цикл[2].
- ↑ Weisstein, Eric W. Lattice graph(англ.) на сайті Wolfram MathWorld.
- ↑ а б в Weisstein, Eric W. Grid graph(англ.) на сайті Wolfram MathWorld.