Im Algorithm Design Manual , Seite 178 werden einige Eigenschaften von Graph beschrieben, und einer davon ist eingebettet und topologisch:
Eingebettet vs. topologisch
Ein Graph ist eingebettet, wenn die Scheitelpunkte und Kanten werden geometrische Positionen zugewiesen. Also, jede Zeichnung eines Graphen ist eine Einbettung, die algorithmische Bedeutung haben kann oder auch nicht.
Gelegentlich wird die Struktur eines Graphen vollständig durch die definiert Geometrie seiner Einbettung. Zum Beispiel, wenn wir eine Sammlung erhalten der Punkte im Flugzeug, und suchen Sie die minimale Kostenreise, die alle besucht sie (d. h. das Problem des reisenden Verkäufers), die zugrundeliegende Topologie ist der vollständige Graph, der jedes Scheitelpunktpaar verbindet. Die Gewichte sind typischerweise durch den euklidischen Abstand zwischen jedem Paar definiert Punkte.
Rasterpunkte sind ein weiteres Beispiel für Topologie aus Geometrie. Viele Probleme in einem n × m-Gitter beinhalten das Gehen zwischen benachbarten Punkte, also sind die Kanten implizit aus der Geometrie definiert.
Ich verstehe es ganz und gar nicht:
embedded hier? Solange die Scheitelpunkte ihre eigenen geometrischen Positionen haben, kann ich dann den eingebetteten Graphen aufrufen? any drawing of a graph is an embedding ? Bedeutet das, was ich in Punkt 1 gesagt habe? Topological ? Ich denke nicht, dass es in dieser Beschreibung erklärt wird. Danke
Skiena verwendet den geografischen Freundschaftsgraph als Beispiel für ein eingebettetes Diagramm, da jeder Scheitelpunkt einem geografischen Punkt in dieser Welt zugeordnet ist, in dem Freunde leben.
Auszug aus dem Buch - Leben meine Freunde in meiner Nähe? - Soziale Netzwerke sind nicht von der Geographie getrennt. Viele deiner Freunde sind nur deine Freunde, weil sie zufällig in deiner Nähe leben (z. B. Nachbarn) oder in deiner Nähe leben (z. B. Mitbewohner im College).
Ein vollständiges Verständnis von sozialen Netzwerken erfordert also ein eingebettetes Diagramm, in dem jeder Knoten mit dem Punkt in dieser Welt verbunden ist, in dem er lebt. Diese geografische Information ist möglicherweise nicht explizit kodiert, aber die Tatsache, dass der Graph inhärent in die Ebene eingebettet ist, prägt unsere Interpretation jeder Analyse.
Zusätzlich zu msjs Antwort.
Graph = G(V, E) , wobei V eine Menge von Vertex und E ein Paar von Vertices von V ist. Dies ist eine Definition von Graphen nach Skiena. Beachten Sie, wie nicht erwähnt wird, wie dieses Diagramm visuell erscheint (d. H. Keine Erwähnung seiner Topologie).
Beispiel (beachten Sie, dass nicht definiert wird, wo sich a , b im X, Y-Koordinatensystem befinden)
V = { a, b, c, d, e, f } und E = { (a,b), (b,c), (a,e) }
Um ein Diagramm zu zeichnen, weisen Sie ihm geometrische Positionen zu, z. in X-, Y-Koordinatensystemen.
%Vor% Abb. 1 ist einfach eine Einbettung, bei der wir Eckpunktepaare in E
Der Unterschied zwischen eingebettetem und topologischem Graphen ist, wie die "Topologie" aussieht. In jeder "Einbettung" weisen Sie geometrische Positionen wie oben beschrieben manuell zu, aber im topologischen Diagramm definieren Sie eine "Regel", basierend darauf, welche Topologie eines Graphen sich selbst definiert. z.B. Sie geben ein G(V,E) an und definieren eine Regel, z. B. "besuche jeden Knoten genau einmal" definiert die Topologie, die als "vollständiges Diagramm" bezeichnet wird.
Tags und Links algorithm data-structures graph topology