Greve Yao

Graph Yao  är en typ av geometriskt spännande , viktad oriktad graf , som förbinder en uppsättning geometriska punkter med egenskapen att för alla par av punkter i grafen har den kortaste vägen mellan dem en längd som inte överstiger deras euklidiska avstånd med en konstant faktor .

Uppkallad efter Andrew Yao .

Beskrivning

Huvudidén med att konstruera en tvådimensionell Yao-graf är att omge varje punkt med jämnt fördelade strålar , dela upp planet i sektorer med lika vinklar och förbinda varje punkt med sina närmaste grannar i var och en av dessa sektorer [1] . En heltalsparameter är associerad med Yao-grafen , som är lika med antalet strålar och sektorer som beskrivs ovan. Ett större värde på k ger en mer exakt approximation till det euklidiska avståndet [2] . Sträckningsfaktorn överstiger inte , där är lika med vinkeln på sektorerna [3] . Samma idé kan utökas till uppsättningar av punkter i dimensioner större än två, men antalet nödvändiga sektorer växer exponentiellt med dimensionen.

Andrew Yao använde dessa grafer för att bygga euklidiska minimumspännande träd i högdimensionella utrymmen [3] .

Yao grafritprogram

Se även

Anteckningar

  1. ↑ Överläggsnätverk för trådlösa system . Hämtad 27 mars 2019. Arkiverad från originalet 20 november 2021.
  2. ↑ Enkla topologier . Hämtad 27 mars 2019. Arkiverad från originalet 20 november 2021.
  3. ↑ 1 2 Yao, 1982 , sid. 721–736.

Litteratur