Граф Яо

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

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

Опис

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

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

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

• Кістяки на основі конусів у Бібліотеці алгоритмів обчислювальної геометрії (Computational Geometry Algorithms Library, CGAL)Шаблон:Webarchive

Див. також

• Тета-граф
• Шаблон:Не перекладено

Література

• Шаблон:Стаття