Processing math: 100%

34 votos

Temas interesantes y accesibles de la teoría de grafos

Este verano, impartiré un curso de introducción a la teoría de grafos a estudiantes de último año de secundaria con talento. La intención del curso no es establecer la competencia en la teoría de grafos, per se. Más bien, espero utilizar la teoría de grafos como vehículo para transmitir una sensación de desarrollo de las matemáticas "avanzadas" (recordemos que estos estudiantes habrán visto el cálculo de primer año, en el mejor de los casos).

¿Cuáles son tus fragmentos favoritos de la teoría de grafos, interesantes y accesibles?

"Interesante" puede significar que el tema tiene una aplicación especialmente útil en el mundo real o que es un resultado teórico sorprendente o elegante. Una ventaja añadida sería si el tema puede revelar lagunas en nuestro conocimiento colectivo (por ejemplo, aún no se conocen con exactitud los pequeños números de Ramsey). "Accesible" significa que un estudiante brillante y motivado sin conocimientos de combinatoria puede seguir el desarrollo del tema desde el principio, aunque le lleve varias clases.

7voto

Ronnie Brown Puntos 7852

He aquí un tema que me hizo perder (?) muchas horas: existe un teorema según el cual toda incrustación en el espacio 3 de K7 , el gráfico completo de 7 vértices, contiene un nudo. Dibuja una incrustación de este tipo y encuentra el o los nudos.

Cada incrustación de K6 contiene un enlace, pero eso suele ser mucho más fácil de encontrar.

Si encuentro la referencia, la añadiré como comentario.

7voto

Vandell Puntos 126

Los problemas de coloreado son bonitos y accesibles. Si está mencionando los números de Ramsey (¡como debería!), será fácil pasar a los problemas de coloreado (o viceversa).

Algunos temas que vale la pena incluir serían

  • Bipartito si es 2 veces coloreable
  • Teoremas de cuatro/cinco colores
  • Número cromático, límites básicos
  • Número cromático de las aristas, teorema de Vizing, teorema de König sobre el color de las líneas

Estos fueron algunos de mis resultados favoritos en mi primer curso de teoría de grafos.

6voto

K. Brian Kelley Puntos 7714

1) Como dices en la pregunta, los números de Ramsey, tanto el (fácil) límite superior -un elegante ejemplo del poder de la combinatoria- como el límite inferior, una de las raras pruebas que es fácil, corta y completamente sorprendente.

2) Teorema de Turan sobre el tamaño de los conjuntos independientes en los grafos. De nuevo, una aplicación fácil del método probabilístico (aunque ni siquiera se necesita el lenguaje de la probabilidad para enunciarlo). También es interesante que, a diferencia de los números de Ramsey, se trata de un ejemplo en el que la prueba "fácil" da realmente el mejor límite posible (para grafos generales).

Por supuesto, dada la gran variedad de problemas a los que se pueden aplicar los grafos, es útil poder detectar subgrafos estructurados, ya sean grafos completos o conjuntos independientes. Estos son también buenos ejemplos de pruebas no constructivas.

5voto

Tom R Puntos 1128

Creo que presentar la conexión entre los paseos aleatorios y las redes eléctricas (como en el texto clásico "Paseos aleatorios y redes eléctricas" de Doyle y Snell) es una idea interesante y factible. Hace apenas una semana impartí un curso de 6 días sobre esto a estudiantes de secundaria con talento y funcionó muy bien. Es una buena oportunidad para mostrarles aplicaciones interesantes de la probabilidad y darles una idea de un campo vibrante de las matemáticas. Además, hay mucho espacio para divagar sobre las cadenas de Markov, la teoría de grafos espectrales, etc.

3voto

wojo Puntos 1707

Probablemente no es lo que estás buscando, pero si yo estuviera impartiendo un curso de este tipo me centraría en la interacción entre los algoritmos para varios problemas de grafos y el enfoque matemático más tradicional de demostrar teoremas en la teoría de grafos.

Por ejemplo, se puede demostrar el teorema "flujo máximo-corte mínimo" desarrollando un algoritmo que encuentre simultáneamente un flujo máximo y un corte mínimo correspondiente.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X