4.2: Gráficas Planares

Última actualización
Guardar como PDF

Page ID: 115811

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Template:MathJaxLevin

Cuando una gráfica conectada se puede dibujar sin que ningún borde se cruce, se llama planar. Cuando una gráfica plana se dibuja de esta manera, divide el plano en regiones llamadas caras.

Dibuje, si es posible, dos gráficas planas diferentes con el mismo número de vértices, aristas y caras.
Dibuje, si es posible, dos gráficas planas diferentes con el mismo número de vértices y aristas, pero un número diferente de caras.

¿Cuándo es posible dibujar una gráfica para que ninguno de los bordes se cruce? Si esto es posible, decimos que la gráfica es plana (ya que la puedes dibujar en el plano).

Observe que la definición de planar incluye la frase “es posible”. Esto quiere decir que aunque una gráfica no parezca plana, aún así podría serlo. Quizás puedas redibujarlo de una manera en la que no se crucen bordes. Por ejemplo, esta es una gráfica plana:

$image-101.svg$

Eso es porque podemos redibujarlo así:

$image-102.svg$

Las gráficas son las mismas, así que si una es plana, la otra debe serlo también. Sin embargo, el dibujo original de la gráfica no era una representación plana de la gráfica.

Cuando se dibuja una gráfica plana sin que los bordes se crucen, los bordes y vértices de la gráfica dividen el plano en regiones. Llamaremos cara a cada región. La gráfica anterior tiene 3 caras (sí, sí incluimos la región “exterior” como cara). El número de caras no cambia independientemente de cómo dibuje la gráfica (siempre y cuando lo haga sin que los bordes se crucen), por lo que tiene sentido atribuir el número de caras como una propiedad de la gráfica plana.

ADVERTENCIA: solo se pueden contar las caras cuando la gráfica se dibuja de manera plana. Por ejemplo, considere estas dos representaciones de la misma gráfica:

$image-103.svg$ $image-104.svg$

Si intentas contar caras usando la gráfica de la izquierda, podrías decir que hay 5 caras (incluyendo el exterior). Pero dibujar la gráfica con una representación plana muestra que de hecho sólo hay 4 caras.

Existe una conexión entre el número de vértices ($v$), el número de aristas ($e$) y el número de caras ($f$) en cualquier gráfica plana conectada. Esta relación se llama fórmula de Euler.

Definición: Fórmula de Euler para Gráficas Planares

Para cualquier gráfico plano (conectado) con$v$ vértices,$e$ aristas y$f$ caras, tenemos

\ start {ecuación*} v-e + f = 2\ end {ecuación*}

¿Por qué es cierta la fórmula de Euler? Una forma de convencerse de su validez es dibujar una gráfica plana paso a paso. Empezar con la gráfica$P_2\text{:}$

$image-105.svg$

Cualquier gráfica conectada (además de un solo vértice aislado) debe contener este subgrafo. Ahora construye tu gráfica agregando bordes y vértices. Cada paso consistirá en agregar un nuevo vértice conectado por un nuevo borde a parte de tu gráfica (así crear un nuevo “pico”) o conectando dos vértices que ya están en la gráfica con un nuevo borde (completando un circuito).

$image-106.svg$ $image-107.svg$

¿Qué hacen estos “movimientos”? Al sumar el pico, el número de aristas aumenta en 1, el número de vértices aumenta en uno, y el número de caras sigue siendo el mismo. Pero esto significa que eso$v - e + f$ no cambia. Completar un circuito agrega un borde, agrega una cara y mantiene el número de vértices igual. Así que de nuevo,$v - e + f$ no cambia.

Ya que podemos construir cualquier gráfica usando una combinación de estos dos movimientos, y hacerlo nunca cambia la cantidad$v - e + f\text{,}$ esa cantidad será la misma para todas las gráficas. Pero fíjense que nuestra gráfica de partida$P_2$ tiene$v = 2\text{,}$$e = 1$ y$f = 1\text{,}$ así$v - e + f = 2\text{.}$ Este argumento es esencialmente una prueba por inducción. Un buen ejercicio sería reescribirlo como prueba formal de inducción.

Gráficas no planas

Para las gráficas completas$K_n\text{,}$ nos gustaría poder decir algo sobre el número de vértices, aristas y (si la gráfica es plana) caras. Primero consideremos$K_3\text{:}$

¿Cuántos vértices$K_3$ tiene? ¿Cuántos bordes?
Si$K_3$ es plano, ¿cuántas caras debería tener?

Repita las partes (1) y (2) para$K_4\text{,}$$K_5\text{,}$ y$K_{23}\text{.}$

¿Qué pasa con las gráficas bipartitas completas? ¿Cuántos vértices, aristas y caras (si fuera plano)$K_{7,4}$ tiene? ¿Para qué valores de$m$ y$n$ son$K_n$ y$K_{m,n}$ planos?

No todas las gráficas son planas. Si hay demasiados bordes y muy pocos vértices, entonces algunos de los bordes necesitarán cruzarse. La primera vez que esto sucede es en$K_5\text{.}$

$image-108.svg$

Si intentas redibujar esto sin que los bordes se crucen, rápidamente te metes en problemas. Parece que hay una ventaja demasiadas. De hecho, podemos demostrar que no importa cómo lo dibujes, siempre$K_5$ tendrá bordes cruzando.

Teorema$\PageIndex{1}$

$K_5$no es plano.

Prueba

La prueba es por contradicción. Entonces, supongamos que$K_5$ es plano. Entonces la gráfica debe satisfacer la fórmula de Euler para gráficas planas. $K_5$tiene 5 vértices y 10 aristas, por lo que obtenemos

\ begin {ecuación*} 5 - 10 + f = 2\ end {ecuación*}

que dice que si se dibuja la gráfica sin que ningún borde se cruce, habría$f = 7$ caras.

Ahora considere cuántos bordes rodean cada cara. Cada cara debe estar rodeada por al menos 3 bordes. Dejar$B$ ser el número total de límites alrededor de todas las caras en la gráfica. Así tenemos eso$B \ge 3f\text{.}$ Pero también$B = 2e\text{,}$ ya que cada borde se usa como límite exactamente dos veces. Armando esto obtenemos

\ start {ecuación*} 3f\ le 2e\ end {ecuación*}

Pero esto es imposible, ya que ya lo hemos determinado$f = 7$ y$e = 10\text{,}$ y$21 \not\le 20\text{.}$ Esto es una contradicción por lo que de hecho no$K_5$ es planar.

$\square$

La otra gráfica más simple que no es plana es$K_{3,3}$

$image-109.svg$

Demostrar que no$K_{3,3}$ es planar responde al rompecabezas de casas y servicios públicos: no es posible conectar cada una de las tres casas a cada una de las tres utilidades sin que las líneas se crucen.

Teorema$\PageIndex{2}$

$K_{3,3}$no es plano.

Prueba

Nuevamente, procedemos por contradicción. Supongamos que$K_{3,3}$ eran planos. Entonces por la fórmula de Euler habrá 5 caras, desde$v = 6\text{,}$$e = 9\text{,}$ y$6 - 9 + f = 2\text{.}$

¿Cuántos límites rodean estas 5 caras? $B$Sea este número. Dado que cada arista se usa como límite dos veces, tenemos$B = 2e\text{.}$ También,$B \ge 4f$ ya que cada cara está rodeada por 4 o más límites. Sabemos que esto es cierto porque$K_{3,3}$ es bipartito, por lo que no contiene ningún ciclo de 3 bordes. Así

\ begin {ecuación*} 4f\ le 2e. \ end {ecuación*}

Pero esto diría$20 \le 18\text{,}$ lo que es claramente falso. Por lo tanto, no$K_{3,3}$ es plano.

$\square$

Obsérvese las similitudes y diferencias en estas pruebas. Ambas son pruebas por contradicción, y ambas comienzan con el uso de la fórmula de Euler para derivar el (supuesto) número de caras en la gráfica. Entonces encontramos una relación entre el número de caras y el número de aristas en función del número de aristas que rodean cada cara. Esta es la única diferencia. En la prueba para$K_5\text{,}$ conseguimos$3f \le 2e$ y para$K_{3,3}$ nosotros vamos$4f \le 2e\text{.}$ El coeficiente de$f$ es la clave. Es el menor número de aristas que podrían rodear cualquier cara. Si cierto número de aristas rodean una cara, entonces estas aristas forman un ciclo. Entonces ese número es el tamaño del ciclo más pequeño en la gráfica.

En general, si dejamos$g$ ser el tamaño del ciclo más pequeño en una gráfica ($g$significa circunferencia, que es el término técnico para esto) entonces para cualquier gráfica plana que tengamos$gf \le 2e\text{.}$ Cuando esto no está de acuerdo con la fórmula de Euler, sabemos con certeza que la gráfica no puede ser plana.

Poliedros

¡Investiga!

Un cubo es un ejemplo de un poliedro convexo. Contiene 6 cuadrados idénticos para sus caras, 8 vértices y 12 aristas. El cubo es un poliedro regular (también conocido como sólido platónico) porque cada cara es un polígono regular idéntico y cada vértice une un número igual de caras.

Hay exactamente otros cuatro poliedros regulares: el tetraedro, octaedro, dodecaedro e icosaedro con 4, 8, 12 y 20 caras respectivamente. ¿Cuántos vértices y aristas tiene cada uno de estos?

Otra área de las matemáticas donde es posible que hayas escuchado los términos “vértice”, “borde” y “cara” es la geometría. Un poliedro es un sólido geométrico formado por caras poligonales planas unidas en aristas y vértices. Estamos especialmente interesados en los poliedros convexos, lo que significa que cualquier segmento de línea que conecte dos puntos en el interior del poliedro debe estar completamente contenido dentro del poliedro. ²

Una definición alternativa para convexo es que el ángulo interno formado por dos caras cualesquiera debe ser menor que$180 ^o$.

Observe que dado que$8 - 12 + 6 = 2\text{,}$ los vértices, aristas y caras de un cubo satisfacen la fórmula de Euler para gráficos planos. Esto no es una coincidencia.

Podemos representar un cubo como un gráfico plano proyectando los vértices y bordes sobre el plano. Una de esas proyecciones se ve así:

$image-110.svg$

De hecho, cada poliedro convexo puede proyectarse sobre el plano sin que los bordes se crucen. Piensa en colocar el poliedro dentro de una esfera, con una luz en el centro de la esfera. Los bordes y vértices del poliedro proyectan una sombra sobre el interior de la esfera. Luego se puede cortar un agujero en la esfera en medio de una de las caras proyectadas y “estirar” la esfera para que quede plana sobre el plano. La cara que fue perforada se convierte en la cara “exterior” de la gráfica plana.

El punto es, podemos aplicar lo que sabemos de las gráficas (en particular las gráficas planas) a los poliedros convexos. Dado que cada poliedro convexo se puede representar como un gráfico plano, vemos que la fórmula de Euler para gráficos planos también se mantiene para todos los poliedros convexos. También podemos aplicar el mismo tipo de razonamiento que usamos para gráficas en otros contextos a poliedros convexos. Por ejemplo, sabemos que no hay poliedro convexo con 11 vértices todos de grado 3, ya que esto haría 33/2 aristas.

Ejemplo$\PageIndex{3}$

¿Existe un poliedro convexo que consta de tres triángulos y seis pentágonos? ¿Y tres triángulos, seis pentágonos y cinco heptágonos (polígonos de 7 lados)?

Solución

¿Cuántos bordes tendrían esos poliedros? Para el primer poliedro propuesto, los triángulos aportarían un total de 9 aristas, y los pentágonos aportarían 30. Sin embargo, esto cuenta cada borde dos veces (ya que cada borde bordea exactamente dos caras), dando 39/2 aristas, una imposibilidad. No existe tal poliedro.

El segundo poliedro no tiene este obstáculo. Los 35 bordes adicionales aportados por los heptágonos dan un total de 74/2 = 37 bordes. Hasta el momento tan bueno. Ahora, ¿cuántos vértices tiene este supuesto poliedro? Podemos usar la fórmula de Euler. Hay 14 caras, así que tenemos$v - 37 + 14 = 2$ or equivalently $v = 25\text{.}$ But now use the vertices to count the edges again. Each vertex must have degree at least three (that is, each vertex joins at least three faces since the interior angle of all the polygons must be less that $180^\circ$), so the sum of the degrees of vertices is at least 75. Since the sum of the degrees must be exactly twice the number of edges, this says that there are strictly more than 37 edges. Again, there is no such polyhedron.

Para concluir esta aplicación de las gráficas planas, considere los poliedros regulares. Arriba afirmamos sólo hay cinco. ¿Cómo sabemos que esto es cierto? Podemos demostrarlo usando la teoría gráfica.

Teorema$\PageIndex{3}$: regular polyhedra

Hay exactamente cinco poliedros regulares.

Prueba

Recordemos que un poliedro regular tiene todas sus caras polígonos regulares idénticos, y que cada vértice tiene el mismo grado. Considera los casos, desglosados por lo que podría ser el polígono regular.

Caso 1: Cada cara es un triángulo. $f$Sea el número de caras. Luego hay$3f/2$ bordes. Usando la fórmula de Euler tenemos$v - 3f/2 + f = 2$ así$v = 2 + f/2\text{.}$ Ahora cada vértice tiene el mismo grado, digamos$k\text{.}$ Así que el número de aristas también está$kv/2\text{.}$ Armando esto da

\ begin {ecuación*} e =\ frac {3f} {2} =\ frac {k (2+f/2)} {2}\ final {ecuación*}

que dice

\ comenzar {ecuación*} k =\ frac {6f} {4+f}\ final {ecuación*}

Necesitamos$k$ y$f$ que ambos sean enteros positivos. Tenga en cuenta que$\frac{6f}{4+f}$ es una función creciente para positivo$f\text{,}$ y tiene una asíntota horizontal en 6. Así, los únicos valores posibles para$k$ son 3, 4 y 5. Cada uno de estos son posibles. Para conseguir$k = 3\text{,}$ necesitamos$f = 4$ (este es el tetraedro). Para$k = 4$ nosotros tomamos$f = 8$ (el octaedro). Para$k = 5$ llevar$f = 20$ (el icosaedro). De esta manera hay exactamente tres poliedros regulares con triángulos para caras.

Caso 2: Cada cara es un cuadrado. Ahora tenemos$e = 4f/2 = 2f\text{.}$ Usando la fórmula de Euler obtenemos$v = 2 + f\text{,}$ y contando bordes usando el grado$k$ de cada vértice nos da

\ begin {ecuación*} e = 2f =\ frac {k (2+f)} {2}\ final {ecuación*}

Resolviendo para$k$ da

\ comenzar {ecuación*} k =\ frac {4f} {2+f} =\ frac {8f} {4+2f}\ final {ecuación*}

Esta es nuevamente una función creciente, pero esta vez la asíntota horizontal está en$k = 4\text{,}$ así que el único valor posible que$k$ podría tomar es 3. Esto produce 6 caras, y tenemos un cubo. Solo hay un poliedro regular con caras cuadradas.

Caso 3: Cada cara es un pentágono. Realizamos el mismo cálculo que el anterior, esta vez consiguiendo$e = 5f/2$ así$v = 2 + 3f/2\text{.}$ Entonces

\ begin {ecuación*} e =\ frac {5f} {2} =\ frac {k (2+3f/2)} {2}\ end {ecuación*}

por lo

\ comenzar {ecuación*} k =\ frac {10f} {4+3f}\ final {ecuación*}

Ahora la asíntota horizontal está en$\frac{10}{3}\text{.}$ Esto es menos de 4, así que solo podemos esperar hacer$k = 3\text{.}$ Podemos hacerlo usando 12 pentágonos, obteniendo el dodecaedro. Este es el único poliedro regular con pentágonos como caras.

Caso 4: Cada cara es un$n$ -gon con$n \ge 6\text{.}$ Siguiendo el mismo procedimiento anterior, deducimos que

\ begin {ecuación*} k =\ frac {2nf} {4+ (n-2) f}\ final {ecuación*}

que se incrementará a una asíntota horizontal de$\frac{2n}{n-2}\text{.}$ Cuando$n = 6\text{,}$ esta asíntota está en$k = 3\text{.}$ Cualquier valor mayor de$n$ dará una asíntota aún más pequeña. Por lo tanto, no existen poliedros regulares con caras más grandes que los pentágonos. ³ Observe que puede enmarcar el plano con hexágonos. Esta es una gráfica plana infinita; cada vértice tiene grado 3. Estos infinitamente muchos hexágonos corresponden al límite como$f \to \infty$ to make $k = 3\text{.}$

$\square$