Miélnikov О.I. Teoría de grafos en problemas recreativos resueltos

Índice

Introducción

La matemática actual se diferencia mucho de la matemática de comienzos del siglo XX. En ella ha aparecido una gran cantidad de nuevas disciplinas que se utilizan ampliamente en la práctica. Entre ellas tenemos, por ejemplo, las que se agrupan bajo la denominación de "Matemática discreta". La Enciclopedia de las Matemáticas define la matemática discreta como una serie de teorías matemáticas no relacionadas directamente con los conceptos de límite y continuidad. La matemática discreta se desarrolla impetuosamente en la actualidad, debido ante todo a la gran difusión que han adquirido los sistemas computacionales, en cuya descripción se utiliza fundamentalmente el lenguaje de la matemática discreta. La matemática discreta es la base teórica de la informática, la cual con mayor intensidad día a día penetra no sólo en la ciencia y la técnica, sino también en la vida cotidiana.

Entre los temas de la matemática discreta la teoría de grafos ocupa un importante lugar. Esta disciplina nació a partir de los intentos de formalización de la resolución de rompecabezas y constituye actualmente un método simple, accesible y potente para resolver problemas tanto teóricos como prácticos.

Uno de los objetivos perseguidos por el autor es dar una introducción elemental a la teoría de grafos. En el libro se presenta una gran cantidad de conceptos y resultados de la misma. El deseo del autor es que su trabajo pueda ser llamado con todo derecho Teoría de grafos para escolares. Con ayuda de este libro se puede comenzar a estudiar la teoría de grafos a partir del quinto grado de educación primaria. Los conceptos principales se ilustran con ayuda de ejemplos y las demostraciones de los teoremas han sido incluidas en la resolución de los problemas. Entre estos teoremas se pueden encontrar algunos de un nivel bastante avanzado. Por esta razón, el autor considera que el libro también será de gran utilidad para los estudiantes universitarios.

En los cursos de matemática que se imparten en el marco de la educación primaria y media, la matemática discreta está representada de forma extremadamente pobre. Como resultado, surge un abismo colosal entre la educación media y la superior. Los egresados de los centros de enseñanza media comienzan la universidad con una preparación muy débil en el campo de la matemática discreta y, sobre todo en los primeros años de estudio, afrontan serias dificultades en el aprendizaje. Uno de los objetivos de este libro es ayudar a desarrollar el "pensamiento discreto" de los futuros estudiantes universitarios.

Con el objetivo de preparar especialistas de alto nivel hoy en las universidades se enseña a los estudiantes cómo pasar de las situaciones reales a los modelos matemáticos que las describen, y cómo investigar los modelos construidos con ayuda de computadoras. El autor es de la opinión que la construcción de modelos matemáticos simples se debe comenzar a enseñar en la escuela primaria. La teoría de grafos es una excelente base para esto. En forma de grafos es posible representar, por ejemplo, el esquema de las carreteras de una localidad, los circuitos eléctricos, los mapas geográficos, las moléculas de las sustancias químicas, las relaciones entre diferentes objetos y personas, etcétera. Precisamente éste es el motivo por el que la teoría de grafos es tan usada en la física, la cibernética, la química, la biología, la economía, la sociología y otras ciencias. Ella ocupa en la programación moderna un lugar particularmente importante. En este libro veremos numerosos ejemplos que muestran cómo diferentes situaciones dan lugar a modelos de la teoría de grafos.

Los problemas relacionados con grafos aparecen con frecuencia en las olimpiadas de matemática de todos los niveles. Este libro puede ser de gran ayuda para aprender a resolver este tipo de problemas y también como guía en la impartición de cursos facultativos de matemática e informática en la escuela.

En el libro se presentan 269 problemas de diferentes grados de dificultad, junto con sus respectivas soluciones. La mayoría de los problemas han sido creados o reinterpretados por el autor. Algunos de ellos (por ejemplo, el problema de las tres casas y los tres pozos, el recorrido de puentes, el problema del apretón de manos, etcétera) pertenecen al folclore matemático. Otros problemas han sido tomados de diferentes fuentes y en algunos casos se ofrece una nueva solución.

Para resolver los problemas de este libro son suficientes los conocimientos de matemática adquiridos en la escuela de enseñanza media. Sólo unos pocos problemas se resuelven con ayuda del método de inducción completa. El símbolo |X| denota el número de elementos del conjunto X. Todos los conceptos introducidos se utilizan posteriormente en la solución de los problemas. El lector puede consultar el índice de materias que se ofrece al final del libro, en el cual se indica el problema en que se introduce cada concepto.

Aparte de desarrollar la cultura matemática, el estudio de los elementos de la teoría de grafos, a opinión del autor, facilita el dominio de las técnicas computacionales y la preparación para el estudio en centros de enseñanza superior.

* * *

El autor expresa su agradecimiento a P.V.Skums por la ayuda prestada en el procesamiento del manuscrito de este libro.

Olieg Isidórovich Miélnikov

Doctor en Ciencias Físico-Matemáticas y en Pedagogía. Es profesor de la Facultad de Mecánica y Matemática de la Universidad Estatal de Bielorrusia. Es un reconocido especialista en teoría de grafos y en métodos de enseñanza de la matemática discreta en la educación media y superior.

O.I.Miélnikov es autor o coautor de los siguientes libros: Lecciones de teoría de grafos (URSS, 2009; de próxima edición en español en URSS), Aventuras en el país de los grafos (URSS, 2006), La enseñanza de la matemática discreta (URSS, 2008), Exercises in graph theory, Informática. Métodos de algoritmización, Matemática para economistas con aplicación del paquete Mathcad. Por el libro Lecciones de teoría de grafos fue galardonado con el Premio Estatal de la República de Bielorrusia.