graph - Quali sono le differenze tra Embedded e Topological in Graph?

Question

In Algorithm Design Manual, pagina 178 descrive alcune proprietà di grafico, e uno di loro è incorporato e topologica:

di Embedded vs. topologico

Un grafico è incorporato se i vertici e bordi vengono assegnate posizioni geometriche . Pertanto, qualsiasi disegno di un grafico è un incorporamento, che può avere o meno un significato algoritmico.

Occasionalmente, la struttura di un grafico è completamente definita dalla geometria di incorporamento. Ad esempio, se viene assegnata una raccolta di punti nell'aereo e si cerca il tour a costo minimo visitando tutti i (ovvero il problema del commesso viaggiatore), la topologia sottostante è il grafico completo che collega ciascuna coppia di vertici. I pesi sono in genere definiti dalla distanza euclidea tra ogni coppia di punti .

Le griglie di punti sono un altro esempio di topologia dalla geometria. Molti problemi su una griglia n × m implicano il camminare tra i punti vicini , in modo che i bordi siano definiti implicitamente dalla geometria.

ho abbastanza non lo capisco:

1. Prima di tutto, che cosa esattamente vuol dire embedded qui? Finché i vertici hanno le loro posizioni geometriche, posso chiamare il grafico incorporato?
2. Che cosa significa any drawing of a graph is an embedding? Significa ciò che ho detto al punto 1?
3. Che cosa significa Topological? Non penso che sia spiegato in questa descrizione.
4. Gli esempi in questa descrizione mi hanno davvero confuso molto. Qualcuno potrebbe usare le parole più semplici per farmi capire questi due termini per il grafico?
5. È davvero importante comprendere questi due termini?

Grazie

Answer 1

1. Vi ricordo che un grafico è solo un insieme di vertici e un insieme di bordi definiti su di loro, in modo che i vertici non hanno una posizione geometrica dei loro propri. Un disegno di un grafo è chiamato embedding, un grafo disegnato è chiamato embedded.
2. Significa che qualsiasi modo di disegnare un grafico è chiamato incorporamento di quel grafico.
3. Un grafico topologico è un grafico i cui vertici e bordi sono rispettivamente punti e archi.

Answer 2

Skiena utilizza un grafico di amicizia geografica come esempio per il grafico incorporato poiché ogni vertice è associato a un punto geografico in questo mondo in cui vivono gli amici.

Estratto dal libro - I miei amici vivono vicino a me? - I social network non sono separati dalla geografia. Molti dei tuoi amici sono tuoi amici solo perché vivono vicino a te (ad es. Vicini) o abituati a vivere vicino a te (ad es. Compagni di stanza al college).

Quindi, una piena comprensione dei social network richiede un grafo incorporato, in cui ogni vertice è associato al punto in questo mondo in cui vivono. Queste informazioni geografiche potrebbero non essere codificate esplicitamente, ma il fatto che il grafico sia intrinsecamente incorporato nel piano modella la nostra interpretazione di qualsiasi analisi.

Answer 3

Oltre alla risposta di msj.

Graph = G(V, E), dove V è impostato su vertice ed e E è impostata la coppia di vertici da V. Questa è la definizione di grafico come per Skiena. Si noti come non si faccia menzione di come questo grafico appare visivamente (non si fa menzione della sua topologia).

Esempio (si noti che non definisce dove a, b si trovano a dire X, Y sistema di coordinate)

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

Per 'disegnare' un grafico si assegna posizioni geometriche esempio in sistemi di coordinate X, Y.

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

figura 1 è semplicemente un'immersione dove stiamo disegnando coppie di vertici specificati E

Differenza tra incorporato e grafico topologico è come fa il "topologia" viene ad essere. In qualsiasi "incorporamento" si assegnano manualmente posizioni geometriche come spiegato sopra, ma nel grafico topologico si definisce una "regola" in base alla quale la topologia di un grafico si definisce. per esempio. si specifica un G(V,E) e si definisce una regola, ad esempio "visita ogni nodo esattamente una volta" definisce la topologia che si chiama "grafico completo".