Chamtivé vkládání - Greedy embedding
V teorii distribuovaných počítačů a geometrických grafů je chamtivé vkládání proces přiřazování souřadnic uzlům telekomunikační sítě , aby bylo možné směrovat zprávy v rámci sítě pomocí chamtivého geografického směrování . Ačkoli bylo pro použití v bezdrátových senzorových sítích navrženo chamtivé vkládání , ve kterých uzly již mají pozice ve fyzickém prostoru, tyto stávající polohy se mohou lišit od pozic, které jim byly dány chamtivým vkládáním, což v některých případech mohou být body ve virtuálním prostoru ve vyšší dimenzi nebo v neeuklidovské geometrii . V tomto smyslu může být chamtivé vkládání chápáno jako forma kresby grafu , ve které je abstraktní graf (komunikační síť) vložen do geometrického prostoru.
Myšlenka provádět geografické směrování pomocí souřadnic ve virtuálním prostoru namísto použití fyzických souřadnic je dána Rao et al. Následný vývoj ukázal, že každá síť má chamtivé vkládání se stručnými souřadnicemi vrcholů v hyperbolické rovině , že určité grafy včetně polyedrických grafů mají chamtivé vložení do euklidovské roviny a že grafy jednotkových disků mají chamtivé vložení do euklidovských prostor mírných rozměrů s nízké napínací faktory.
Definice
Při chamtivém směrování zpráva ze zdrojového uzlu s do cílového uzlu t cestuje do svého cíle sledem kroků mezi uzly, z nichž každý předá zprávu sousednímu uzlu, který je blíže t . Pokud zpráva dosáhne na mezilehlý uzel x, který nemá souseda blíže k t , pak nemůže dosáhnout pokroku a proces chamtivého směrování selže. Chamtivé vkládání je vložení daného grafu s vlastností, že selhání tohoto typu není možné. Lze jej tedy charakterizovat jako vložení grafu s vlastností, že pro každé dva uzly x a t existuje soused y z x takový, že d ( x , t )> d ( y , t ), kde d označuje vzdálenost ve vloženém prostoru.
Grafy bez chamtivého vkládání
Ne každý graf má chamtivé začlenění do euklidovské roviny ; jednoduchý protipříklad je dán hvězdou K 1,6 , stromem s jedním vnitřním uzlem a šesti listy. Kdykoli je tento graf vložen do roviny, některé dva jeho listy musí svírat úhel 60 stupňů nebo menší, z čehož vyplývá, že alespoň jeden z těchto dvou listů nemá souseda, který je blíže druhému listu.
V euklidovských prostorech vyšších dimenzí může mít více grafů chamtivé vložení; například K 1,6 má chamtivé začlenění do trojrozměrného euklidovského prostoru, ve kterém je vnitřní uzel hvězdy na počátku a listy jsou vzdáleny o jednotku dál podél každé souřadnicové osy. Pro každý euklidovský prostor s pevnou dimenzí však existují grafy, které nelze vložit chamtivě: kdykoli je číslo n větší než líbající se číslo prostoru, graf K 1, n nemá chamtivé vkládání.
Hyperbolické a stručné vložení
Na rozdíl od případu v euklidovském letadle má každá síť chamtivé začlenění do hyperbolické roviny . Původní důkaz tohoto výsledku od Roberta Kleinberga vyžadoval, aby byly polohy uzlů specifikovány s vysokou přesností, ale následně se ukázalo, že pomocí dekompozice rozsáhlého stromu spanningového stromu v síti je možné reprezentovat každý uzel stručně, s použitím pouze logaritmického počtu bitů na bod. Naproti tomu existují grafy, které mají chamtivé vložení do euklidovské roviny, ale u nichž takovéto vložení vyžaduje polynomický počet bitů pro karteziánské souřadnice každého bodu.
Speciální třídy grafů
Stromy
Třída stromů, které připouštějí chamtivé začlenění do euklidovské roviny, byla zcela charakterizována a chamtivé zakotvení stromu lze nalézt v lineárním čase, pokud existuje.
U obecnějších grafů začínají některé chamtivé vkládací algoritmy, jako je Kleinbergův, vyhledáním kostry daného grafu a poté sestavením chamtivého vložení překlenovacího stromu. Výsledkem je nutně také chamtivé vložení celého grafu. Existují však grafy, které mají chamtivé vložení do euklidovské roviny, ale pro které žádný klenutý strom chamtivé vložení nemá.
Rovinné grafy
Má každý mnohostěnný graf planární chamtivé vložení s konvexními tvářemi?
Papadimitriou & Ratajczak (2005) se domnívali, že každý polyedrický graf ( rovinný graf spojený se 3 vrcholy nebo Steinitzovou větou graf konvexního mnohostěnu ) má chamtivé zakotvení v euklidovské rovině. Tím, že využívá vlastnosti kaktusu grafů , Leighton a Moitra (2010) prokázal domněnek; chamtivé vložení těchto grafů lze definovat stručně, logaritmicky mnoho bitů na souřadnici. Chamtivé vložení konstruované podle tohoto důkazu však nemusí být nutně planární, protože mohou zahrnovat křížení mezi dvojicemi hran. Pro maximální rovinné grafy , ve kterých je každá plocha trojúhelník, lze chamtivé planární vkládání najít aplikací Knaster – Kuratowski – Mazurkiewiczova lemmatu na váženou verzi algoritmu přímého vkládání Schnydera. Silný Papadimitriou-Ratajczak domněnka , že každý polyhedrálních graf má rovinnou chamtivý vkládání, ve které jsou všechny plochy jsou konvexní, podložena.
Grafy diskových jednotek
Sítě bezdrátových senzorů, které jsou cílem chamtivých algoritmů vkládání, jsou často modelovány jako grafy jednotkových disků, grafy , ve kterých je každý uzel reprezentován jako jednotkový disk a každý okraj odpovídá dvojici disků s neprázdným průnikem. Pro tuto speciální třídu grafů je možné najít stručné chamtivé vložení do euklidovského prostoru polylogaritmické dimenze s další vlastností, že vzdálenosti v grafu jsou přesně aproximovány vzdálenostmi při vkládání, takže cesty následované chamtivým směrováním jsou krátký.
