Cuánto topología de la teoría de grafos?

Question

Estoy escribiendo una tesis en el contexto de la descriptiva de la complejidad en la ciencia computacional teórica y por lo tanto es necesario estudiar un poco de la teoría de grafos. Mi fondo no es matemática, sino de ciencias de la computación con un fuerte interés en las matemáticas (lo que significa que no he escuchado avanzado conferencias pero se siente cómodo aprender más). Aquí el enfoque está en la base teórica de grafos planares. Mi punto de partida es la grafos planares capítulo en Diestel de 2005.

Una superficie es un compacto conectado Hausdorf espacio topológico $S$ en el que cada punto tiene una vecindad homeomórficos el plano Euclídeo $\mathbb{R}^2$. Un arco, un círculo y un disco en $S$ son subconjuntos que son homeomórficos en el subespacio de la topología para el verdadero intervalo de $[0,1]$, para el círculo unidad $S^1 = \{ x \in \mathbb{R}^2 \mid \|x\|=1\}$, y a la unidad de disco $\{ x \in \mathbb{R} \mid \|x\| \leq 1\}$, respectivamente.

Estas definiciones se utilizan posteriormente para definir grafos planares, plano de gráficos. Otros conceptos topológicos isomorphisms también se utilizan.

He encontrado todas las definiciones en Wikipedia y sé lo que digo. Lamentablemente no tengo la intuición de lo que significan. Por ejemplo, supongo que un arco es una curva continua que no se cruzan con él. Mi pregunta no es ¿cuál de las definiciones, sino más bien, lo que es un buen punto de partida para aprender acerca de la topología de un equipo de la perspectiva de la ciencia (con un poco de conocimiento de fondo) en el contexto de la teoría de grafos y cuánto es realmente necesario? Es posible tomar estos topología cosas como cajas negras o es importante entender?

Answer 1

Parece que lo que te estás metiendo es topológico de la teoría de grafos, que se refiere principalmente a la incrustación de gráficos en las superficies. El estudio de los grafos planares es un caso especial de este, donde los gráficos se están incrustados en el avión. Así, en topológica de la teoría de grafos, por ejemplo, es posible que también el estudio de los gráficos de lo que podría ser linklessly incrustado en un toro.

Yo soy de ninguna manera un experto en este tema, pero apuesto a que si se coge la Topología de las Superficies (que es bastante suave para una topología libro), puede obtener un buen asidero en la topológico lado de las cosas para volver a Diestel y recoger donde lo dejó.

Answer 2

He encontrado Jeff Erickson Computacional de la Topología de notas muy útil cuando empecé con el requisito similar de aprendizaje acerca de la topología de un equipo de la perspectiva de la ciencia.

Answer 3

Si realmente tienes una buena idea de lo que es un homeomorphism es, se puede entender la mayoría de estas definiciones con bastante facilidad. Un homeomorphism es el equivalente de un isomorfismo de espacios topológicos: si dos espacios de $X$ $Y$ son homeomórficos, entonces, esencialmente, "el mismo aspecto." Por ejemplo, cualquier intervalo cerrado $[a,b]$ es homeomórficos a la unidad de intervalo de $[0,1]$, y una plaza cerrada de cualquier tamaño en $\Bbb R^2$ es homeomórficos a la unidad de disco. Homeomorphisms recuerde propiedades esenciales de los espacios, como los "agujeros" y "dimensión", pero se olvidan de las cosas como si es o no un espacio de "esquinas" (en general, la "forma" no es recordado por homeomorphism).

Así que cuando usted piensa en el último par de definiciones que usted da, usted puede pensar de arcos, los discos, y los círculos como incrustaciones de la unidad de intervalo, unidad de disco, y el círculo unidad en otros de dimensiones superiores Euclidiana espacios, permitiendo a los objetos ser estirado y retorcido y deformado sin rasgadura o de lo contrario, esencialmente, la alteración de la estructura de los espacios originales (es de suponer que usted va a estar trabajando en Euclidiana espacios, pero si no, se aplica la misma idea).

Como para superficies, se desea que algunos ejemplos en mente. Esferas, elipsoides, y los cubos (sin interiores) son todas las superficies por esta definición. Una superficie (al menos en $\Bbb R^n$ va a ser cerrado, delimitado (esto es equivalente a compacto en $\Bbb R^n$) del objeto que es "de dos dimensiones," lo que significa que si usted elige un punto y zoom, es básicamente ver como $\Bbb R^2$ (aka, cada punto tiene una vecindad homeomórficos a $\Bbb R^2$).

Las cosas pueden ponerse un poco más raro en no-euclidiana espacios, pero si usted sigue los ejemplos en la mente y el seguimiento de sus definiciones, usted no puede ir mal. Buena suerte!