algorithm - graphs - graph-¿Cuáles son las diferencias entre Embedded y Topological en Graph?

graph representations

Question

En Algorithm Design Manual , la página 178 describe algunas propiedades de Graph, y una de ellas está incrustada y Topological:

Integrado vs. Topológico

Un gráfico está incrustado si los vértices y los bordes tienen asignadas posiciones geométricas. Por lo tanto, cualquier dibujo de un gráfico es una incrustación, que puede tener o no significado algorítmico.

Ocasionalmente, la estructura de un gráfico está completamente definida por la geometría de su incrustación. Por ejemplo, si se nos da una colección de puntos en el plano y buscamos el recorrido de costo mínimo que los visita a todos (es decir, el problema del vendedor ambulante), la topología subyacente es el gráfico completo que conecta cada par de vértices. Los pesos están típicamente definidos por la distancia euclidiana entre cada par de puntos.

Las grillas de puntos son otro ejemplo de topología de geometría. Muchos problemas en una cuadrícula n × m implican caminar entre puntos vecinos, por lo que los bordes están implícitamente definidos a partir de la geometría.

Yo no lo entiendo completamente

1. Antes que nada, ¿qué significa exactamente embedded aquí? Mientras los vértices tengan sus propias posiciones geométricas, ¿puedo llamar al gráfico incrustado?
2. ¿Qué significa any drawing of a graph is an embedding ? ¿Significa lo que dije en el punto 1?
3. ¿Qué significa Topological ? No creo que se explique en esta descripción.
4. Los ejemplos en esta descripción realmente me confundieron mucho. ¿Podría alguien usar las palabras más simples para dejarme entender estos dos términos para el gráfico?
5. ¿Es realmente importante entender estos dos términos?

Gracias

Answer 1

1. Les recuerdo que un gráfico es solo un conjunto de vértices y un conjunto de bordes definidos en ellos, por lo que los vértices no tienen una posición geométrica propia. Un dibujo de un gráfico se llama incrustación, un gráfico dibujado se llama incrustado.
2. Significa que cualquier forma de dibujar un gráfico se llama incrustación de ese gráfico.
3. Un gráfico topológico es un gráfico cuyos vértices y bordes son puntos y arcos, respectivamente.

Answer 2

Skiena usa el gráfico de amistad geográfica como un ejemplo para el gráfico incrustado porque cada vértice está asociado con un punto geográfico en este mundo en el que viven amigos.

Extracto del libro: ¿viven mis amigos cerca de mí? - Las redes sociales no están divorciadas de la geografía. Muchos de tus amigos son tus amigos solo porque viven cerca de ti (por ejemplo, vecinos) o solían vivir cerca de ti (por ejemplo, compañeros de cuarto en la universidad).

Por lo tanto, una comprensión completa de las redes sociales requiere un gráfico incrustado, donde cada vértice se asocia con el punto en este mundo donde viven. Esta información geográfica puede no estar codificada explícitamente, pero el hecho de que el gráfico esté intrínsecamente incrustado en el plano configura nuestra interpretación de cualquier análisis.

Answer 3

Además de la respuesta de msj.

Graph = G(V, E) , donde V se establece de vértice yy E se establece par de vértices de V. Esta es la definición de gráfico según Skiena. Tenga en cuenta que no se menciona cómo aparece visualmente este gráfico (es decir, no se menciona su topología).

Ejemplo (tenga en cuenta que no define dónde se encuentran a, b en el sistema de coordenadas X, Y)

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

Para ''dibujar'' un gráfico, se le asignan posiciones geométricas, por ejemplo, en sistemas de coordenadas X e Y.

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

La figura 1 es simplemente una incrustación en la que estamos dibujando pares de vértices especificados en E

La diferencia entre el gráfico incrustado y topológico es cómo viene a ser la "topología". En cualquier "incrustación" asigna manualmente las ubicaciones geométricas como se explicó anteriormente, pero en el gráfico topológico define una "regla" en función de qué topología de un gráfico se define a sí misma. por ejemplo, especifica un G(V,E) y define una regla, por ejemplo, "visita cada nodo exactamente una vez", define la topología que se llama "gráfico completo".