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

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

Зазвичай не робиться явної відмінності між такими графами у більш абстрактному сенсі теорії графів і малюнком у просторі (часто на площині або тривимірному просторі). Цей тип графів можна коротко називати просто ґратами. Проте той же термін зазвичай використовується для кінцевих частин нескінченних графів, як, наприклад, «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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.