Otakar Borůvka (10 de mayo de 1899 – 22 de julio de 1995) fue un matemático checo . Es más conocido por su trabajo en teoría de grafos . [1] [2]
Borůvka nació en Uherský Ostroh , una ciudad en Moravia , Austria-Hungría (hoy en la República Checa ), hijo de un director de escuela. [2] Asistió a la escuela secundaria en Uherské Hradiště a partir de 1910. [1] En 1916, influenciado por la Primera Guerra Mundial en curso , se trasladó a la escuela militar (Realschule) en Hranice , y más tarde se inscribió en la Academia Técnica Militar Imperial y Real en Mödling cerca de Viena . [1] [2]
Cuando terminó la guerra, Borůvka regresó a Uherské Hradiště, terminó sus estudios en 1918 en el Gymnasium de allí y se convirtió en estudiante de la Universidad Técnica Imperial Checa de Francisco José , en Brno , estudiando inicialmente ingeniería civil . [1] [2] En 1920, se inauguró la Universidad Masaryk en Brno, y Borůvka también comenzó a tomar cursos allí. [1] Se convirtió en asistente de Mathias Lerch en Masaryk en 1921, pero Lerch murió en 1922; su puesto en Masaryk fue ocupado por Eduard Čech , a quien Borůvka también ayudó, obteniendo su doctorado en 1923. [3]
Por sugerencia de Čech, Borůvka visitó a Élie Cartan en París de 1926 a 1927. [1] [2] Obtuvo su habilitación en la Universidad de Masaryk en 1927 y (rechazando una oferta de la Universidad de Zagreb ) se convirtió en docente allí en 1928. [1] [2] Continuó viajando al extranjero a fines de la década de 1920 y principios de la de 1930, nuevamente a Cartan en París, así como a Wilhelm Blaschke en Hamburgo . [1] [2] Fue ascendido a profesor asistente en Masaryk en 1934, se le dio una cátedra en 1940 y se convirtió en profesor ordinario en 1946. [1] [2]
En 1965 fundó la nueva revista Archivum Mathematicum y en 1969 se convirtió en miembro fundador del Instituto de Matemáticas de la Academia Checoslovaca de Ciencias , dividiendo su tiempo entre el Instituto y su cátedra en Masaryk. [2]
El problema de diseñar redes de distribución eléctrica eficientes había sido sugerido a Borůvka por su amigo Jindřich Saxel, un empleado de la Compañía de Energía de Moravia Occidental, durante la Primera Guerra Mundial. En su artículo de 1926 O jistém problému minimálním (en inglés ) , [4] Borůvka resolvió este problema modelándolo matemáticamente como un problema de árbol de expansión mínimo , y describió el primer algoritmo conocido para encontrar el árbol de expansión mínimo de un espacio métrico (el conjunto de ciudades que se conectarán por la red, junto con sus distancias). [1] Ahora llamado algoritmo de Borůvka , su método funciona agregando repetidamente conexiones entre cada subárbol del árbol de expansión mínimo encontrado hasta ahora y su subárbol vecino más cercano. [5] El mismo algoritmo ha sido redescubierto repetidamente. [6] [7] [8] Es más adecuado para el cálculo distribuido y paralelo que muchos otros algoritmos de árbol de expansión mínimo, puede lograr una complejidad de tiempo lineal en gráficos planares y, de manera más general, en familias de gráficos menores cerrados, [9] y juega un papel central en el algoritmo de tiempo lineal aleatorio de Karger, Klein y Tarjan (1995). [10]
Entre 1924 y 1935, el principal interés de Borůvka fue la geometría diferencial . Su trabajo en esta área se centró en las correspondencias analíticas entre planos proyectivos , la curvatura normal de superficies de alta dimensión y la fórmula de Frenet para curvas en espacios de alta dimensión. [2]
A partir de la década de 1930, los intereses de Borůvka se orientaron hacia el álgebra abstracta y, en particular, hacia la teoría de grupos . También fue uno de los primeros en estudiar una generalización de grupos, a los que llamó «grupoides», pero que ahora se conocen más comúnmente como magmas . [2] Un libro de texto suyo sobre grupos y grupoides, publicado originalmente en checo en 1944, pasó por varias ampliaciones y traducciones, incluida una edición en inglés en 1976. [1]
Después de la guerra, Borůvka cambió de rumbo y pasó del álgebra a la teoría de ecuaciones diferenciales . Publicó varios artículos de investigación sobre este tema, así como una monografía sobre ecuaciones diferenciales de segundo orden que publicó en 1971. [1]
Borůvka se convirtió en miembro correspondiente de la Academia Checoslovaca de Ciencias en su creación en 1953, y en miembro ordinario en 1965. En 1969, la Universidad Comenius de Bratislava le otorgó un doctorado honorario, y en 1994 recibió un segundo doctorado honorario de la Universidad Masaryk de Brno . [1] [11]
También ha recibido medallas de la Universidad Libre de Bruselas , la Universidad de Lieja , la Universidad Jagellónica , la Universidad Comenius, la Universidad Palacký de Olomouc , la Universidad Jan Evangelista Purkyně en Ústí nad Labem , la Academia Alemana de Ciencias de Berlín , la Academia de Ciencias de Rusia#Academia de Ciencias de la URSS y la Academia de Ciencias de Checoslovaquia. [12]