Analizando Gráficas Sin Enlaces en Superficies de Donut

Los gráficos son como puntos conectados por líneas. Puedes pensar en ellos como dibujos hechos de puntos y caminos. Algunos de estos dibujos pueden girar y retorcerse sin enredarse y se llaman libre de enlaces. Ahora, imagina que quieres dibujar estos gráficos en una superficie con forma de dona. Parece simple, pero hay un giro (juego de palabras intencionado). Si el gráfico se enreda mientras lo dibujas en la dona, se convierte en un gráfico enlazado. Este estudio trata de averiguar cuáles gráficos se pueden dibujar en una dona sin enredarse, especialmente cuando los gráficos no están enlazados entre sí.

#Antecedentes: Gráficos y sus tipos

Para entender lo que está pasando, necesitamos hablar de algunos términos básicos.

• Gráficos planarios: Estos son gráficos que se pueden dibujar en una superficie plana sin que las líneas se crucen. Piensa en dibujar con crayones en papel.

• Gráficos toroidales: Estos son gráficos que se pueden dibujar en una superficie con forma de dona sin que las líneas se crucen. Es como intentar hacer tu arte con crayón en un juguete inflable de piscina.

• Gráficos libre de enlaces: Imagina dos líneas que pueden girar una alrededor de la otra sin hacer un nudo. Esto es lo que queremos decir con libre de enlaces. Es importante porque queremos que nuestros dibujos de gráficos eviten enredarse.

En el mundo de los gráficos, algunos son naturalmente más complejos, mientras que otros son simples. Si un gráfico se puede dibujar en una dona sin que se crucen las líneas, se llama toroidal. Si se puede dibujar en esa dona sin que las líneas se líen entre sí, se llama libre de enlaces o no intrínsecamente enlazado (nIL, por su abreviatura).

#La gran pregunta

La pregunta que queremos responder es: si tenemos un gráfico que se puede dibujar en una dona y también es libre de enlaces, ¿podemos garantizar que podemos dibujarlo sin enredos en una forma estándar de dona?

Hasta ahora, sabemos que para gráficos más pequeños (con hasta 9 puntos), si se pueden dibujar en la dona y evitar enredos, podemos decir con confianza que también se pueden dibujar en una forma estándar de dona. Pero, ¿qué pasa con los gráficos más grandes?

#Enlaces en la dona

Tomemos un momento para hablar sobre los enlaces. Los enlaces son como esos momentos molestos cuando dos personas intentan pasarse en un pasillo y terminan enredadas.

• Número de enlace: Hay una manera de medir cuán enredados están dos caminos. Podemos contar cuántas veces estos caminos se cruzan entre sí. Si se cruzan y giran de cierta manera, les asignamos valores. Al final del día, si el valor total no es cero, están enredados.

#Explorando familias de gráficos

Podemos agrupar gráficos juntos según características comunes, como un club de amigos con hobbies similares.

• Familias cerradas menores: Estos son grupos de gráficos que no cambian su naturaleza cuando eliminas o reduces algunas de sus partes. Si eres parte de este club, no puedes ser parte de otro club que no permite ciertos miembros.

Tenemos dos clubes principales en nuestro estudio: el club de gráficos toroidales y el club de gráficos libres de enlaces. Todos los gráficos libres de enlaces también son gráficos toroidales, pero no todos los gráficos toroidales son libres de enlaces. Piensa en ello como ser amante de los gatos; a todos los amantes de los gatos les encantan las mascotas, pero no todos los amantes de las mascotas prefieren los gatos.

#Gráficos maxnIL y su importancia

A veces, encontramos gráficos especiales que están en la cima de la cadena. Estos se llaman gráficos maxnIL. Son libres de enlaces y no se les pueden agregar bordes extra sin volverse enlazados. Son como los jefes en la comunidad de gráficos libres de enlaces.

La mayor parte de nuestro estudio se centra en estos gráficos maxnIL porque si podemos averiguar cómo dibujarlos de manera libre de enlaces en una dona, también podemos trabajar hacia atrás para ver si se cumple para todos los demás gráficos.

#Obstrucciones toroidales

Al explorar el mundo de los gráficos toroidales, encontramos algunos que no encajan en la descripción de libre de enlaces. Estos se llaman obstrucciones toroidales, y son como los desafortunados intrusos que arruinan la diversión.

Hasta ahora, hemos descubierto algunas obstrucciones toroidales que no se pueden dibujar libremente sin retorcerse. La más pequeña tiene 8 puntos y es la primera que necesitamos sacar del club de libre de enlaces.

#Encontrando gráficos MTN

Para responder a la gran pregunta, necesitamos averiguar qué gráficos se pueden dibujar libremente en una dona sin enredarse. Comenzamos con gráficos más pequeños y trabajamos hacia arriba.

Para los gráficos más pequeños (como los de 6 o 7 puntos), podemos decir con confianza que son libres de enlaces. A medida que subimos, el desafío se vuelve más complejo, especialmente cuando encontramos gráficos de orden 9.

#La búsqueda de la libre de enlaces

Cuando profundizamos en gráficos de orden 9, utilizamos una variedad de técnicas y observaciones. Tenemos un entendimiento previo de que ciertos gráficos son no enlazables.

A través de una serie de deducciones ingeniosas, podemos determinar que de los veinte gráficos maxnIL de orden 9, solo cuatro no se pueden dibujar en la dona sin enredarse. Estos cuatro problemáticos hacen que nuestras vidas sean más interesantes, pero también complican nuestra investigación.

#Herramientas del oficio

A lo largo de este viaje, usamos varios algoritmos para ayudarnos a hacer un seguimiento de qué gráficos estamos tratando. Al aplicar estos algoritmos, podemos esbozar condiciones que determinan si un gráfico se puede dibujar libremente o no.

Un algoritmo útil nos ayuda a identificar gráficos libres de enlaces según sus cruces de caminos. Esto es crucial porque nos ahorra tener que dibujar cada gráfico a mano. Después de todo, ¿quién tiene tiempo para eso?

#Demostrando la libre de enlaces

Ahora que tenemos un entendimiento sólido de los gráficos con los que estamos trabajando, es hora de demostrar que un gráfico es libre de enlaces. Usamos nuestra definición anterior de pendientes y cruces, y podemos establecer una pequeña prueba. Si la lista devuelta por nuestro algoritmo no muestra conflictos ni enredos, podemos decir con confianza que el gráfico es libre de enlaces.

#Los resultados

Después de horas y horas de dibujo, examinación y pruebas, hemos reunido una colección completa de gráficos MTN para órdenes que van del 6 al 9. Los hallazgos indican que todos estos gráficos se pueden dibujar en una dona sin enredarse, ¡así que a seguir la fiesta!

#Direcciones futuras

Habiendo abordado los gráficos más pequeños, ahora queremos ver si podemos extender este trabajo a gráficos más grandes. Creemos que hay una buena posibilidad de que todos los gráficos toroidales y nIL se puedan dibujar libremente en una dona.

Hemos hecho grandes progresos, pero el futuro requerirá mucho trabajo. Entender los menores prohibidos para estos tipos de gráficos podría eventualmente llevarnos a conclusiones más sólidas sobre su comportamiento libre de enlaces.

#Conclusión

En resumen, hemos hecho una inmersión divertida en el mundo de los gráficos en donas, descubriendo cómo estas formas matemáticas pueden existir sin enredarse. Con nuestros hallazgos, ahora tenemos una mejor comprensión de cómo funcionan estos gráficos en una superficie toroidal, y aunque todavía hay más por investigar, estamos felices de haber demostrado una cosa: no todos los gráficos les gusta enredarse, y eso es un alivio.