Введение
Чешский ученый и математик Отакар Борувка (10 мая 1899 года в Ухерском Острохе – 22 июля 1995 года в Брно) — чешский математик, наиболее известный сегодня своими работами в области теории графов.
Otakar Borůvka (10 May 1899 in Uherský Ostroh – 22 July 1995 in Brno) was a Czech mathematician best known today for his work in graph theory.
Образование и карьера
Родился в Ухерском Острохе, городе в Моравии (тогда в Австро-Венгрии, позже в Чехословакии, ныне в Чехии), сыном директора школы. В 1916 году, под влиянием Первой мировой войны, он перешёл в военную школу (Realschule) в Границе, а затем поступил в Императорскую и Королевскую техническую военную академию в Мёдлинге близ Вены. По предложению Чеха, Борувка посетил Эли Картана в Париже в период с 1926 по 1927 год. Борувка решил эту задачу, математически смоделировав её как задачу о минимальном остовном дереве, и описал первый известный алгоритм поиска минимального остовного дерева метрического пространства (множество городов, подлежащих соединению сетью, вместе с расстояниями между ними). Этот же алгоритм неоднократно был открыт заново. Он более пригоден для распределённых и параллельных вычислений, чем многие другие алгоритмы поиска минимального остовного дерева, может достигать линейной временной сложности на планарных графах и, в более общем случае, в семействах графов, замкнутых относительно миноров, и играет центральную роль в рандомизированном алгоритме линейного времени. С 1924 по 1935 год основным интересом Борувки была дифференциальная геометрия. Его работы в этой области касались аналитических соответствий между проективными плоскостями, нормальной кривизны поверхностей высокой размерности и формулы Френе для кривых в пространствах высокой размерности. Он также был удостоен медалей Свободного университета Брюсселя, Университета Льежа, Ягеллонского университета, Университета Комениуса, Университета Палацкого в Оломоуце, Университета Яна Евангелисты Пуркине в Усти-над-Лабем, Немецкой академии наук в Берлине, Российской академии наук, Академии наук СССР и Чехословацкой академии наук.
influenced by the ongoing World War I, he moved to the military school (Realschule) in Hranice, and later he enrolled into the Imperial and Royal Technical Military Academy in Mödling near Vienna. At Čech's suggestion, Borůvka visited Élie Cartan in Paris from 1926 to 1927. Borůvka solved this problem by modeling it mathematically as a minimum spanning tree problem, and
described the first known algorithm for finding the minimum spanning tree of a metric space (the set of cities to be connected by the network, together with their distances). The same algorithm has been rediscovered repeatedly. It is more suitable for distributed and parallel computation than many other minimum spanning tree algorithms, can achieve linear time complexity on planar graphs and more generally in minor closed graph families, and plays a central role in the randomized linear time algorithm of
From 1924 to 1935, Borůvka's primary interest was in differential geometry. His work in this area concerned analytic correspondences between projective planes, normal curvature of high dimensional surfaces, and Frenet formula for curves in high dimensional spaces. He has also been given medals by the Free University of Brussels, the University of Liège, Jagiellonian University, Comenius University, Palacký University of Olomouc, Jan Evangelista Purkyně University in Ústí nad Labem, the German Academy of Sciences at Berlin, the Russian Academy of Sciences#Academy of Sciences of the USSR, and the Czechoslovak Academy of Sciences.