Contele Yao

Graph Yao  este un tip de grafic nedirecționat ponderat, cu acoperire geometrică , care conectează un set de puncte geometrice cu proprietatea că, pentru orice pereche de puncte din grafic, calea cea mai scurtă dintre ele are o lungime care nu depășește distanța lor euclidiană cu un factor constant .

Numit după Andrew Yao .

Descriere

Ideea principală a construirii unui grafic Yao bidimensional este de a înconjura fiecare punct cu raze distribuite uniform , împărțind planul în sectoare cu unghiuri egale și conectând fiecare punct cu vecinii săi cei mai apropiați în fiecare dintre aceste sectoare [1] . Un parametru întreg este asociat cu graficul Yao , care este egal cu numărul de raze și sectoare descrise mai sus. O valoare mai mare a lui k oferă o aproximare mai precisă a distanței euclidiene [2] . Factorul de întindere nu depășește , unde este egal cu unghiul sectoarelor [3] . Aceeași idee poate fi extinsă la seturi de puncte cu dimensiuni mai mari de două, dar numărul de sectoare necesare crește exponențial odată cu dimensiunea.

Andrew Yao a folosit aceste grafice pentru a construi arbori de întindere minim euclidien în spații cu dimensiuni mari [3] .

Programe de desenare a graficelor Yao

Vezi și

Note

  1. ↑ Rețele de suprapunere pentru sisteme fără fir . Preluat la 27 martie 2019. Arhivat din original la 20 noiembrie 2021.
  2. ↑ Topologii simple . Preluat la 27 martie 2019. Arhivat din original la 20 noiembrie 2021.
  3. ↑ 1 2 Yao, 1982 , p. 721–736.

Literatură