3.1. Fórmula de Euler

1. Fórmula de Euler para poliedros convexos

Poliedro

Un poliedro es la representación de una región acotada del espacio, la cual está delimitada exclusivamente por polígonos planos.

Los poliedros se clasifican en convexos o cóncavos.

Poliedros convexos. Un poliedro se considera convexo si cumple con la siguiente propiedad: para cualquier par de puntos dentro del poliedro, el segmento de línea que los conecta nunca sale del poliedro.

Poliedro convexo
Imagen de elaboración propia. Poliedro convexo. (CC BY-NC-SA)

Poliedros cóncavos. Un poliedro se considera cóncavo si existe al menos un par de puntos dentro del poliedro tal que el segmento de línea que los conecta sale del poliedro en algún punto de su trayecto.

Poliedro cóncavo
Imagen de elaboración propia. Poliedro cóncavo. (CC BY-NC-SA)

Teorema de Euler (para poliedros)

El teorema de Euler para poliedros convexos, también conocido como la fórmula de Euler, es un teorema fundamental en la geometría de los poliedros. Establece una relación entre el número de vértices (V), el número de aristas (A) y el número de caras (C) de un poliedro convexo. La fórmula se expresa como sigue:

$V+C−A=2$

Esta relación es notable porque, sin importar la complejidad del poliedro convexo, siempre se cumple que la suma de los vértices y las caras, menos el número de aristas, es igual a 2. Este teorema es aplicable a cualquier poliedro convexo, incluyendo los sólidos platónicos (tetraedro, cubo, octaedro, dodecaedro, icosaedro) y otros más complejos.

Poliedros Regulares (Sólidos Platónicos)
Los poliedros regulares, también conocidos como sólidos platónicos, son aquellos en los que todas las caras son polígonos regulares congruentes (es decir, todos los lados y ángulos son iguales) y el mismo número de caras se unen en cada vértice. Solo existen cinco sólidos platónicos:

Tetraedro (4 caras triangulares)
Cubo o Hexaedro (6 caras cuadradas)
Octaedro (8 caras triangulares)
Dodecaedro (12 caras pentagonales)
Icosaedro (20 caras triangulares)
Estos poliedros son convexos y se caracterizan por su alta simetría y belleza geométrica.

Poliedros regulares
Imagen de Arturo Mandly en Flickr. Poliedros regulares.
(CC BY-NC-SA)

2. Fórmula de Euler para grafos planos

Grafos poliédricos

Los grafos poliédricos son los que se obtienen a partir de los poliedros mediante un proceso que implica proyectar o mapear las caras, aristas y vértices de un poliedro en una superficie plana sin perder la información esencial del poliedro.

Los poliedros regulares, como los sólidos platónicos, son candidatos ideales para obtener grafos poliédricos debido a su alta simetría y estructura regular, pero cualquier poliedro puede utilizarse.

Para obtener el grafo correspondiente a un poliedro debemos, en primer lugar, identificar todas las caras, aristas y vértices del poliedro. Estos elementos son fundamentales, ya que en el grafo resultante, los vértices representarán los vértices del poliedro, y las aristas del grafo representarán las aristas del poliedro.

Después, el poliedro se "abre" o se proyecta sobre una superficie plana. Así, cada vértice del poliedro se convierte en un vértice del grafo y cada arista del poliedro se convierte en una arista del grafo, conectando los vértices correspondientes.

El grafo obtenido debe ser plano, lo que significa que se puede dibujar en un plano sin que sus aristas se crucen. Todos los grafos derivados de poliedros son planos debido a la naturaleza tridimensional y conexa de los poliedros.

A continuación se muestran los grafos planos correspondientes a los poliedros regulares y a la pirámide de base cuadrada.

Grafos poliédricos
Imagen de Stannered en Wikimedia Commons. Grafos poliédricos (CC BY-NC-SA)

Este proceso permite representar la estructura tridimensional de un poliedro en un formato bidimensional, preservando la información sobre cómo los elementos del poliedro están conectados entre sí.

¿Qué son las caras de un grafo?

Las caras de un grafo se refieren a las regiones delimitadas por las aristas de un grafo cuando este se dibuja en un plano sin que sus aristas se crucen, es decir, en el contexto de grafos planos.

Las caras son, por tanto, las áreas cerradas por las aristas de un grafo plano, incluyendo tanto las regiones finitas (interiores) como la región infinita (exterior) que rodea al grafo.

La siguiente imagen muestra el grafo del cubo, identificando tanto las caras internas como la cara externa.

Caras de un grafo
Imagen de elaboración propia. Caras de un grafo. (CC BY-NC-SA)

Podemos comprobar que se sigue cumpliendo que  $C+V-A=2$, pues $6+8-12=2$

Teorema de Euler para grafos planos

Teorema de Euler para grafos planos establece que el número de caras, más el de vértices, menos el número de aristas es siempre 2. No debemos olvidar la cara externa en el cómputo total de las caras.

$C+V-A=2$

3. Aplicaciones reales

Resuelve los siguiente problemas aplicando el Teorema de Euler para grafos planos y completa los huecos.

Problema 1. Diseño de un Parque

Se está diseñando un parque que tendrá áreas de juegos, jardines y estanques, representados por vértices en un grafo plano. Si hay 9 áreas en total, conectadas por 14 senderos, y se planea construir un nuevo estanque que agregará 2 senderos adicionales, ¿cuántas regiones distintas (incluyendo el exterior del parque) habrá en total?

Habrá regiones (incluyendo la región exterior del parque).

Problema 2. Red de Ordenadores

En una red de ordenadores, hay 8 nodos conectados por 12 enlaces. Si se quiere agregar un nuevo ordenador conectado a 4 nodos existentes, ¿cuál será el número total de caras en la red, asumiendo que la red forma un grafo plano?.

En total habrá caras total en la red.

Problema 3. Diseño de un Jardín Botánico

Un jardín botánico está siendo rediseñado para incluir senderos que conecten diferentes secciones de plantas, flores y árboles. El diseño propuesto, que forma un grafo plano, consta de 10 regiones (caras), incluyendo el espacio exterior, y hay 22 senderos (aristas) planeados. ¿Cuántas secciones diferentes (vértices) se planean para el jardín botánico?

Se planean secciones diferentes (vértices) para el jardín botánico.

Habilitar JavaScript

4. Un Proyecto de Infraestructura Regional

Problema

Tres ciudades, A, B y C, planean un proyecto de infraestructura para mejorar la comunicación y el transporte entre ellas y otras tres áreas de desarrollo económico, X, Y y Z. El plan es construir carreteras que conecten directamente cada ciudad con cada área de desarrollo sin cruzar otras carreteras. ¿Es posible diseñar este sistema de carreteras sin intersecciones, considerando que las carreteras deben trazarse en una superficie plana?

Proyecto de infraestructura
Imagen de elaboración propia. Proyecto de infraestructura. (CC BY-NC-SA)

Ayuda

Puedes explorar de manera intuitiva si esta configuración es posible, mediante la utilización de este grafo bipartito \(K_{3,3}\) interactivo.

Este recurso permite manipular los vértices y las aristas del grafo. A través de la interacción con el grafo, se puede intentar diversas configuraciones en un esfuerzo por conectar las ciudades con las áreas de desarrollo sin cruzar las carreteras.

Autor: Antonio Ruiz Murcia. Grafo K3_3 interactivo. (CC BY-NC-SA)

Respuesta

Este problema cuestiona si es posible diseñar un sistema de carreteras que conecte tres ciudades, \(A\), \(B\), y \(C\), con tres áreas de desarrollo, \(X\), \(Y\), y \(Z\), sin que ninguna de las carreteras se cruce, siguiendo el modelo de un grafo bipartito completo \(K_{3,3}\).

La respuesta a este problema, basada en las propiedades fundamentales de los grafos, es no.

Aquí se justifica esta conclusión: Para demostrar que \(K_{3,3}\) no es plano, podemos usar el teorema de Euler para grafos planos. El teorema de Euler para un grafo plano conectado dice que \(C + V - A = 2\), donde \(V\) es el número de vértices, \(A\) es el número de aristas, y \(C\) es el número de caras (incluyendo la región exterior).

En \(K_{3,3}\), tenemos \(V = 6\) (3 vértices en cada una de las dos particiones) y \(A = 9\) (cada vértice de una partición se conecta con todos los vértices de la otra partición). Si fuera posible dibujar \(K_{3,3}\) en el plano, podríamos  calcular el número de caras \(C\) usando el teorema de Euler.

Reemplazando \(V = 6\) y \(A = 9\) en la fórmula de Euler \(C + V - A = 2\), obtenemos:
\[C  + 6 - 9 = 2\]      \(C = 5\)

Sin embargo, para grafos planos, cada cara debe estar delimitada por al menos 3 aristas (en el caso de grafos simples). Dado que \(K_{3,3}\) es bipartito y no contiene ciclos de longitud 3 (triángulos), la menor longitud de ciclo posible es 4, lo que significa que cada cara debería estar delimitada por al menos 4 aristas. Esto nos lleva a una contradicción cuando intentamos aplicar la fórmula de Euler junto con la condición de que cada cara debe ser un ciclo de al menos 4 aristas, lo que requeriría más aristas de las que \(K_{3,3}\) posee para satisfacer la cantidad de caras calculadas.

5. ¿Cómo podemos saber si un grafo es plano?

El Teorema de Kuratowski es un resultado fundamental en la teoría de grafos, especialmente en lo que respecta a la caracterización de grafos planos. Este teorema proporciona una condición necesaria y suficiente para determinar si un grafo es plano, es decir, si se puede dibujar en el plano sin que sus aristas se crucen. El teorema se enuncia de la siguiente manera:

Teorema de Kuratowski: un grafo es plano si y solo si no contiene una subdivisión de $K_{5}$ (el grafo completo de cinco vértices) o $K_{3,3}$ (el grafo bipartito completo con dos conjuntos de tres vértices) como subgrafos.


Concepto básico de subdivisión:

  1. Grafo Original: considera un grafo $G$ formado por un conjunto de vértices $V$ y un conjunto de aristas $A$ que conectan estos vértices.
  2. Subdivisión: realizar una subdivisión sobre $G$ consiste en seleccionar una arista $a$ que conecta dos vértices $u$ y $v$, eliminar esta arista $a$ del grafo, y luego añadir un nuevo vértice $w$ junto con dos nuevas aristas $a_1$ y $a_2$. La arista $a_1$ conectará $u$ con $w$, y la arista $a_2$ conectará $w$ con $v$.


$K_{5}$ es el grafo completo de cinco vértices, lo que significa que hay una arista entre cada par de vértices.

Grafo K_5
Imagen de elaboración propia. Grafo K_5. (CC BY-NC-SA)

$K_{3,3}$ es un grafo bipartito completo, lo que significa que los vértices se pueden dividir en dos conjuntos de tres vértices cada uno, y hay una arista entre cada par de vértices de diferentes conjuntos. 

Grafo K3,3
Imagen de elaboración propia. Grafo K3,3 (CC BY-NC-SA)


El Teorema de Kuratowski es una herramienta esencial para demostrar que un grafo dado no es plano, mostrando la existencia de una subdivisión de $K_{5}$ o $K_{3,3}$ dentro de él.

En el siguiente video se presenta un ejercicio concreto que explica como aplicar el teorema de Kuratowski para detectar un grafo que no es planar:

Carlos Fuentes. Grafo Planar Teorema de Kuratowski (Licencia estándar de YouTube)

Página 5 de 12

Obra publicada con Licencia Creative Commons Reconocimiento No comercial Compartir igual 4.0

Creado con eXeLearning (Ventana nueva)