Me he estado enseñando a mí mismo la teoría de los gráficos. Estoy atascado en la resolución de este problema por mi cuenta.
Por favor, proporcione un ejemplo de dicho gráfico.
¿Qué enfoque adoptarías para dibujar un gráfico de este tipo?
Respuestas
¿Demasiados anuncios?
Max
Puntos
16
Una forma de pensar en los grafos no planos son los grafos con demasiadas aristas. Se puede utilizar la fórmula del poliedro de Euler $V - E + F = 2$ para cuantificar esto en base a los vértices $V$ , bordes $E$ y caras $F$ de un gráfico, y se obtiene que si un gráfico es plano entonces $E \leq 3V-6$ .
Dado que un gráfico y su complemento se suman al gráfico completo con $\frac{n(n-1)}{2}$ aristas, si se elige un gráfico no plano con menos de $\frac{n(n-1)}{2} - (3n-6)$ aristas, el complemento tiene demasiadas aristas y ambos no son planos.
Así, por ejemplo, tomemos un gráfico sobre $10$ vértices y conectar $5$ de ellos en $K_5$ mientras que los demás quedan desconectados. En el complemento, los vértices desconectados forman otro $K_5$ por lo que ambas son no planas.
Kevin Moore
Puntos
376
Los grafos no planos incluyen (en cierto sentido) el grafo completo $K_5$ o el grafo bipartito completo $K_{33}$ . A mí me parece que esto último es más fácil de trabajar. Ahora, si tomamos $K_{33}$ su complemento no es no-planar. Pero si tomamos $K_{33}$ y añadimos una segunda componente formada por tres vértices, entonces cuando tomemos el complemento esta componente formará un $K_{33}$ con cada uno de los componentes existentes, por lo que el gráfico resultante también será no plano.
Podemos conectar los tres nuevos vértices entre sí como queramos sin que ello afecte al resultado, y si queremos un gráfico conectado podemos conectarlos a una de las partes existentes del $K_{33}$ -en el gráfico del complemento seguirán formando un $K_{33}$ con el otro componente.
He aquí un ejemplo de este tipo de gráfico:
