Граф Яо

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

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

Опис

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

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

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

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

Див. також

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

Література

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