Gráficos y RedesGráficos Planos

Aquí hay otro rompecabezas relacionado con la teoría de grafos.

En un pequeño pueblo hay tres casas y tres plantas de servicios públicos que producen agua, electricidad y gas. Tenemos que conectar cada uno de los cursos a cada una de las plantas de servicios públicos, pero debido al diseño de la aldea, no se permite cruzar las diferentes tuberías y cables.

Intente conectar cada una de las casas a cada una de las compañías de servicios a continuación, sin que ninguna de sus líneas se crucen:

Al igual que los puentes de Königsberg, descubres rápidamente que este problema también es imposible. Parece que algunos gráficos se pueden dibujar sin bordes superpuestos, estos se llaman gráficos planos , pero otros no.

K3 es plano

K4 .

El gráfico completo K5 es el gráfico más pequeño que no es plano. Cualquier otro gráfico que contenga K5 como subgrafo de alguna manera tampoco es plano. Esto incluye K6 , K7 , y todos los gráficos completos más grandes.

El gráfico en el rompecabezas de las tres utilidades es el gráfico bipartito K3,3 . Resulta que cualquier gráfico no plano debe contener un K5 o un K3,3 (o una subdivisión de estos dos gráficos) como un subgrafo. Esto se llama teorema de Kuratowski .

Planaridad

Este es un gráfico plano, pero el ${n} vértices han sido revueltos. Reorganice los vértices para que ninguno de los bordes se superponga.

Fórmula de Euler

Todos los gráficos planos dividen el plano en el que se dibujan en varias áreas, llamadas caras .

vértices caras bordes 11 vértices + caras

vértices caras bordes 15 vértices + caras

vértices caras bordes 25 vértices + caras

Al comparar estos números, notará que el número de aristas es siempre que el número de caras más el número de vértices. En otras palabras, F + V = E + 1. Este resultado se llama ecuación de Euler y lleva el nombre del mismo matemático que resolvió el problema de los puentes de Königsberg.

Desafortunadamente, hay infinitos gráficos y no podemos verificar cada uno para ver si la ecuación de Euler funciona. En cambio, podemos intentar encontrar una prueba simple que funcione para cualquier gráfico ...

0 + 1 = 0 + 1

The simplest graph consists of a single vertex. We can easily check that Euler’s equation works.

Let us add a new vertex to our graph. We also have to add an edge, and Euler’s equation still works.

If we want to add a third vertex to the graph we have two possibilities. We could create a small triangle: this adds one vertex, one face and two edges, so Euler’s equation still works.

Instead we could simply extend the line by one: this adds one vertex and one edge, and Euler’s equation works.

Let’s keep going: if we now create a quadrilateral we add one vertex, two edges and one face. Euler’s equation still works.

Se puede construir cualquier gráfico (finito) comenzando con un vértice y agregando más vértices uno por uno. Hemos demostrado que, independientemente de la forma en que agreguemos nuevos vértices, la ecuación de Euler es válida. Por lo tanto, es válido para todos los gráficos.

El proceso que hemos usado se llama inducción matemática . Es una técnica muy útil para probar resultados en infinitos casos, simplemente comenzando con el caso más simple y mostrando que el resultado se cumple en cada paso cuando se construyen casos más complejos.

Muchos gráficos planos se parecen mucho a las redes de poliedros , formas tridimensionales con caras poligonales . Si pensamos que los poliedros están hechos de bandas elásticas, podemos imaginar estirarlos hasta que se conviertan en gráficos planos y planos:

Esto significa que podemos usar la fórmula de Euler no solo para gráficos planos sino también para todos los poliedros, con una pequeña diferencia. Al transformar los poliedros en gráficos, una de las caras desaparece: la cara superior del poliedro se convierte en el "exterior"; de los gráficos.

En otras palabras, si cuenta el número de bordes , caras y vértices de cualquier poliedro, encontrarás que F + V = E + .

Icosaedro 20 caras 12 vértices 30 bordes

Rombicosidodecaedro 62 caras 60 vértices 120 bordes

Icosaedro Truncado 32 caras (12 negras, 20 blancas) 60 vértices 90 bordes

Cambiar idioma

Iniciar sesión en Mathigon

Compartir

Restablecer progreso

Glosario

Gráficos y RedesGráficos Planos

Planaridad

Fórmula de Euler