Graph - Was sind die Unterschiede zwischen eingebetteten und topologischen Graphen?

Question

In Algorithm Design Manual, Seite 178 beschreibt einige Eigenschaften von Graph, und einer von ihnen ist eingebettet und Topologische:

gegen Topologische Embedded

Ein Graph eingebettet ist, wenn die Ecken und Kanten geometrischen Positionen zugeordnet sind, . Somit ist jede Zeichnung eines Graphen eine Einbettung, die algorithmische Bedeutung haben kann oder nicht.

Gelegentlich ist die Struktur eines Graphen vollständig durch die Geometrie seiner Einbettung definiert. Zum Beispiel, wenn wir eine Sammlung von Punkten in der Ebene erhalten und die Minimalkosten-Tour suchen, die alle von ihnen besucht (d. H. Das Problem des reisenden Verkäufers), ist die zugrundeliegende Topologie der vollständige Graph, der jedes Paar von Ecken verbindet. Die Gewichte werden typischerweise durch den euklidischen Abstand zwischen jedem Paar von Punkten definiert.

Gitterpunkte sind ein weiteres Beispiel für Topologie aus Geometrie. Bei vielen Problemen in einem n × m-Gitter wird zwischen benachbarten Punkten gesprungen, sodass die Kanten implizit aus der Geometrie definiert werden.

ich recht verstehe es nicht:

1. Zunächst einmal, was genau embedded hier bedeutet? Solange die Eckpunkte ihre eigenen geometrischen Positionen haben, kann ich den eingebetteten Graphen aufrufen?
2. Was bedeutet any drawing of a graph is an embedding? Bedeutet es, was ich in Punkt 1 gesagt habe?
3. Was bedeutet Topological? Ich denke nicht, dass es in dieser Beschreibung erklärt wird.
4. Die Beispiele in dieser Beschreibung haben mich wirklich sehr verwirrt. Könnte jemand bitte die einfachsten Wörter verwenden, um mir diese beiden Begriffe für das Diagramm zu erklären?
5. Ist es wirklich wichtig, diese beiden Begriffe verstanden zu bekommen?

Dank

Answer 1

1. ich Sie daran erinnern, dass ein Graph nur eine Reihe von Eckpunkten ist und eine Reihe von Kanten auf ihnen definiert, so dass die Ecken nicht eine geometrische Position ihrer eigenen. Eine Zeichnung eines Graphen wird Einbettung genannt, ein gezogener Graph wird als eingebettet bezeichnet.
2. Es bedeutet, dass jede Art des Zeichnens eines Graphen eine Einbettung dieses Graphen genannt wird.
3. Ein topologischer Graph ist ein Graph, dessen Ecken und Kanten Punkte bzw. Bögen sind.

Answer 2

Skiena verwendet geographische Freundschaft Graph als ein Beispiel für eingebettete Grafik, da jeder Scheitelpunkt mit einem geografischen Punkt in dieser Welt verbunden ist, wo 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 gewohnt sind, in deiner Nähe zu leben (z. B. College-Mitbewohner).

Ein vollständiges Verständnis von sozialen Netzwerken erfordert daher ein eingebettetes Diagramm, in dem jeder Scheitelpunkt mit dem Punkt in dieser Welt verbunden ist, in dem sie leben. Diese geografische Information wird möglicherweise nicht explizit kodiert, aber die Tatsache, dass der Graph inhärent in die Ebene eingebettet ist, prägt unsere Interpretation jeder Analyse.

Answer 3

Zusätzlich zu msjs Antwort.

Graph = G(V, E), wo V von Vertex gesetzt ist, und und E gesetzt Paar von Eckpunkten von V. Diese Definition der Graph gemäß Skiena ist. Beachten Sie, wie nicht erwähnt wird, wie dieses Diagramm visuell erscheint (d. H. Keine Erwähnung seiner Topologie).

Beispiel (beachten Sie, dass es wird nicht definiert, wo a, b befinden sich in sagen X, Y-Koordinatensystem)

V = { a, b, c, d, e, f } und E = { (a,b), (b,c), (a,e) }

To 'zeichnen' ein Diagramm man es geometrische Positionen zuweisen z.B. in X-, Y-Koordinatensystemen.

| 
|   b (2,3) 
| a(1,2) 
| 
| 
|____________________________ 
Fig 1 

Figur 1 ist lediglich eine Einbettung wo wir Knotenpaare in E angegeben Zeichnung

Unterschied zwischen eingebettet und topologischen Graphen wie funktioniert die „Topologie“ zu sein, kommt. In jeder "Einbettung" ordnen Sie geometrische Positionen manuell wie oben beschrieben zu, aber im topologischen Diagramm definieren Sie eine "Regel", basierend darauf, welche Topologie eines Graphen sich selbst definiert. z.B. Sie geben eine G(V,E) an und definieren eine Regel, z. B. "besuche jeden Knoten genau einmal" definiert die Topologie, die als "vollständiger Graph" bezeichnet wird.