Gierige Einbettung - Greedy embedding
In der Theorie des verteilten Rechnens und der geometrischen Graphen ist die gierige Einbettung ein Prozess des Zuweisens von Koordinaten zu den Knoten eines Telekommunikationsnetzes, um zu ermöglichen, dass gieriges geografisches Routing verwendet wird, um Nachrichten innerhalb des Netzes zu routen. Obwohl Greedy Embedding für die Verwendung in drahtlosen Sensornetzwerken vorgeschlagen wurde , in denen die Knoten bereits Positionen im physischen Raum haben, können diese vorhandenen Positionen von den Positionen abweichen, die ihnen durch Greedy Embedding gegeben werden, die in einigen Fällen Punkte in einem virtuellen Raum sein können einer höheren Dimension oder in einer nichteuklidischen Geometrie . In diesem Sinne kann gierige Einbettung als eine Form der Graphzeichnung angesehen werden , bei der ein abstrakter Graph (das Kommunikationsnetz) in einen geometrischen Raum eingebettet wird.
Die Idee, geographisches Routing unter Verwendung von Koordinaten in einem virtuellen Raum durchzuführen, anstatt physische Koordinaten zu verwenden, stammt von Rao et al. Spätere Entwicklungen haben gezeigt , dass jedes Netzwerk eine gierige Einbettung mit prägnanten Scheitelkoordinaten in der hyperbolischen Ebene hat , dass bestimmte Graphen einschließlich der polyedrischen Graphen gierige Einbettungen in die euklidische Ebene haben und dass Einheitsscheibengraphen gierige Einbettungen in euklidische Räume mit moderaten Dimensionen mit niedrige Dehnungsfaktoren.
Definitionen
Beim gierigen Routing wandert eine Nachricht von einem Quellknoten s zu einem Zielknoten t zu ihrem Ziel durch eine Folge von Schritten durch Zwischenknoten, von denen jeder die Nachricht an einen benachbarten Knoten weiterleitet, der näher an t liegt . Wenn die Nachricht einen Zwischenknoten x erreicht , der keinen Nachbarn näher an t hat , kann sie nicht weiterkommen und der gierige Routing-Prozess schlägt fehl. Eine gierige Einbettung ist eine Einbettung des gegebenen Graphen mit der Eigenschaft, dass ein solcher Fehler unmöglich ist. Somit kann er als Einbettung des Graphen mit der Eigenschaft charakterisiert werden, dass für je zwei Knoten x und t ein Nachbar y von x existiert, so dass d ( x , t ) > d ( y , t ), wobei d bezeichnet der Abstand im eingebetteten Raum.
Grafiken ohne gierige Einbettung
Nicht jeder Graph hat eine gierige Einbettung in die euklidische Ebene ; ein einfaches Gegenbeispiel ist der Stern K 1,6 , ein Baum mit einem inneren Knoten und sechs Blättern. Immer wenn dieser Graph in die Ebene eingebettet ist, müssen zwei seiner Blätter einen Winkel von 60 Grad oder weniger bilden, woraus folgt, dass mindestens eines dieser beiden Blätter keinen Nachbarn hat, der näher am anderen Blatt liegt.
In euklidischen Räumen höherer Dimensionen können mehr Graphen gierige Einbettungen aufweisen; zum Beispiel hat K 1,6 eine gierige Einbettung in den dreidimensionalen euklidischen Raum, in dem der innere Knoten des Sterns im Ursprung liegt und die Blätter entlang jeder Koordinatenachse eine Einheitsentfernung entfernt sind. Für jeden euklidischen Raum fester Dimension gibt es jedoch Graphen, die nicht gierig eingebettet werden können: Immer wenn die Zahl n größer ist als die Kissing-Zahl des Raums, hat der Graph K 1, n keine gierige Einbettung.
Hyperbolische und prägnante Einbettungen
Im Gegensatz zur euklidischen Ebene hat jedes Netzwerk eine gierige Einbettung in die hyperbolische Ebene . Der ursprüngliche Beweis dieses Ergebnisses durch Robert Kleinberg erforderte die genaue Angabe der Knotenpositionen, aber anschließend wurde gezeigt, dass es möglich ist, durch Verwendung einer schweren Pfadzerlegung eines Spannbaums des Netzwerks jeden Knoten darzustellen kurz und bündig, wobei nur eine logarithmische Anzahl von Bits pro Punkt verwendet wird. Im Gegensatz dazu gibt es Graphen mit gierigen Einbettungen in die euklidische Ebene, für die eine solche Einbettung jedoch eine polynomielle Anzahl von Bits für die kartesischen Koordinaten jedes Punktes erfordert.
Spezielle Klassen von Graphen
Bäume
Die Klasse von Bäumen , die gierige Einbettungen in die euklidische Ebene zulassen, wurde vollständig charakterisiert, und eine gierige Einbettung eines Baumes kann in linearer Zeit gefunden werden, wenn sie existiert.
Für allgemeinere Graphen beginnen einige gierige Einbettungsalgorithmen wie der von Kleinberg damit, einen Spannbaum des gegebenen Graphen zu finden und dann eine gierige Einbettung des Spannbaums zu konstruieren. Das Ergebnis ist zwangsläufig auch eine gierige Einbettung des gesamten Graphen. Es gibt jedoch Graphen, die eine gierige Einbettung in die euklidische Ebene aufweisen, für die jedoch kein aufspannender Baum eine gierige Einbettung aufweist.
Planare Grafiken
Hat jeder polyedrische Graph eine planare gierige Einbettung mit konvexen Flächen?
Papadimitriou & Ratajczak (2005) vermuteten, dass jeder polyedrische Graph (ein mit 3 Ecken verbundener planarer Graph oder äquivalent nach dem Satz von Steinitz der Graph eines konvexen Polyeders ) eine gierige Einbettung in die euklidische Ebene hat. Durch die Ausnutzung der Eigenschaften von Kakteen Graphen , Leighton & Moitra (2010) erwies sich die Vermutung; die gierigen Einbettungen dieser Graphen lassen sich prägnant definieren, mit logarithmisch vielen Bits pro Koordinate. Die nach diesem Beweis konstruierten gierigen Einbettungen sind jedoch nicht unbedingt planare Einbettungen, da sie Kreuzungen zwischen Kantenpaaren enthalten können. Für maximal planare Graphen , in denen jede Fläche ein Dreieck ist, kann eine gierige planare Einbettung gefunden werden, indem das Knaster–Kuratowski–Mazurkiewicz-Lemma auf eine gewichtete Version eines geradlinigen Einbettungsalgorithmus von Schnyder angewendet wird. Die starke Papadimitriou-Ratajczak-Vermutung , dass jeder polyedrische Graph eine planare gierige Einbettung hat, in der alle Flächen konvex sind, bleibt unbewiesen.
Einheitsdatenträgerdiagramme
Die drahtlosen Sensornetzwerke, die das Ziel von gierigen Einbettungsalgorithmen sind, werden häufig als Einheitsscheibengraphen modelliert , Graphen, in denen jeder Knoten als eine Einheitsscheibe dargestellt wird und jede Kante einem Paar von Scheiben mit nichtleerem Schnittpunkt entspricht. Für diese spezielle Klasse von Graphen ist es möglich, prägnante gierige Einbettungen in einen euklidischen Raum polylogarithmischer Dimension zu finden, mit der zusätzlichen Eigenschaft, dass Distanzen im Graphen durch Distanzen in der Einbettung genau approximiert werden, so dass die Pfade, denen gieriges Routing folgt, kurz.
