Граф Яо

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

Названо на честь Ендрю Яо.

Опис

Основна ідея побудови двовимірного графа Яо полягає в оточенні кожної точки рівномірно розподіленими променями, які розбивають площину на сектори з рівними кутами, та з'єднанні кожної точки з її найближчими сусідами у кожному з цих секторів[1]. З графом Яо пов'язаний цілочисельний параметр ${\displaystyle k\geqslant 6}$, який дорівнює числу променів та секторів, описаних вище. Більше значення k дає точніше наближення до евклідової відстані[2]. Коефіцієнт розтягування не перевищує ${\displaystyle 1/(\cos \theta -\sin \theta )}$, де ${\displaystyle \theta }$ дорівнює куту секторів[3]. Цю ідею можна поширити на множини точок у розмірностях, більших від двох, але зі зростанням розмірності кількість необхідних секторів зростає експоненційно.

Ендрю Яо використав ці графи для побудови евклідових мінімальних кістякових дерев у просторах високої розмірності[3].

Програми для малювання графів Яо

• Кістяки на основі конусів у Бібліотеці алгоритмів обчислювальної геометрії (Computational Geometry Algorithms Library, CGAL)[Архівовано 27 березня 2019 у Wayback Machine.]

Див. також

• Тета-граф
• Граф напів-Яо^[en]

Примітки

1. Overlay Networks for Wireless Systems (PDF). Архів (PDF) оригіналу за 20 листопада 2021. Процитовано 27 березня 2019.
2. Simple Topologies (PDF). Архів (PDF) оригіналу за 20 листопада 2021. Процитовано 27 березня 2019.
3. Yao, 1982, с. 721–736.

Література

• On constructing minimum spanning trees in k-dimensional space and related problems // SIAM Journal on Computing. — 1982. — Т. 11, вип. 4. — DOI:10.1137/0211059.