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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

[ред. | ред. код]

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

Властивості

[ред. | ред. код]

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

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

Примітки

[ред. | ред. код]
  1. Weisstein, Eric W. Lattice graph(англ.) на сайті Wolfram MathWorld.
  2. а б в Weisstein, Eric W. Grid graph(англ.) на сайті Wolfram MathWorld.