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≤3V−6 .
Dado que un gráfico y su complemento se suman al gráfico completo con n(n−1)2 aristas, si se elige un gráfico no plano con menos de 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 K5 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:
