erick viera dijo:

mi hermano pan comido ahi t dejo la imagen

Click para expandir ...

Grafos planos
Artículo principal: Grafo plano
Un grafo es plano si se puede dibujar sin cruces de aristas. El problema de las tres casas y los tres pozos tiene solución sobre el toro, pero no en el plano.

Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.

Un juego muy conocido es el siguiente: Se dibujan tres casas y tres pozos. Todos los vecinos de las casas tienen el derecho de utilizar los tres pozos. Como no se llevan bien en absoluto, no quieren cruzarse jamás. ¿Es posible trazar los nueve caminos que juntan las tres casas con los tres pozos sin que haya cruces?

Cualquier disposición de las casas, los pozos y los caminos implica la presencia de al menos un cruce.

Sea Kn el grafo completo con n vértices, Kn, p es el grafo bipartito de n y p vértices.

El juego anterior equivale a descubrir si el grafo bipartito completo K3,3 es plano, es decir, si se puede dibujar en un plano sin que haya cruces, siendo la respuesta que no. En general, puede determinarse que un grafo no es plano, si en su diseño puede encontrase una estructura análoga (conocida como menor) a K5 o a K3,3.

Establecer qué grafos son planos no es obvio, y es un problema que tiene que ver con topología.

Click para expandir ...