Кіріспе
Чех ғалымы және математигі Отакар Борувка (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.