Yao gróf

A Yao gráf a geometriai átívelő , súlyozott irányítatlan gráf  egy fajtája, amely geometriai pontok halmazát köti össze azzal a tulajdonsággal, hogy a gráf bármely pontpárja esetén a köztük lévő legrövidebb út hossza nem haladja meg az euklideszi távolságukat állandó tényezővel .

Andrew Yao után nevezték el .

Leírás

A kétdimenziós Yao-gráf megalkotásának fő gondolata az, hogy minden pontot egyenletesen eloszló sugarakkal vesznek körül , a síkot egyenlő szögű szektorokra osztják, és minden pontot összekötnek a legközelebbi szomszédaival ezekben a szektorokban [1] . A Yao gráfhoz egy egész paraméter van társítva , amely megegyezik a fent leírt sugarak és szektorok számával. Nagyobb k értéke pontosabb közelítést ad az euklideszi távolságra [2] . A nyújtási tényező nem haladja meg a , ahol egyenlő a szektorok szögével [3] . Ugyanez az ötlet kiterjeszthető kettőnél nagyobb dimenziójú ponthalmazokra is, de a szükséges szektorok száma exponenciálisan nő a dimenzióval.

Andrew Yao ezeket a gráfokat arra használta, hogy euklideszi minimális feszítőfákat építsen fel nagy dimenziós terekben [3] .

Yao gráfrajzoló programok

Lásd még

Jegyzetek

  1. ↑ Átfedő hálózatok vezeték nélküli rendszerekhez . Letöltve: 2019. március 27. Az eredetiből archiválva : 2021. november 20.
  2. ↑ Egyszerű topológiák . Letöltve: 2019. március 27. Az eredetiből archiválva : 2021. november 20.
  3. ↑ 1 2 Yao, 1982 , p. 721–736.

Irodalom