Otakar Boruvka
Encyclopedia
Otakar Borůvka was a Czech
mathematician
best known today for his work in graph theory
, long before this was an established mathematical discipline.
He was born in Uherský Ostroh
, a town in Moravia
(then in Austria-Hungary
, later Czechoslovakia
; today Czech Republic
), and he attended the grammar school in Uherské Hradiště
, before changing in 1916 to the military school in Hranice and later enrolling into the military technical academy in Mödling
near Vienna
. After the end of World War I
, he graduated in 1918 back at the grammar school in Uherské Hradiště.
In his 1926 paper O jistém problému minimálním (English On a certain minimal problem), Borůvka described an algorithm
for finding the minimum spanning tree
of an electrical network
, now called Borůvka's algorithm
. His results were later discovered by the theoretical computer science
community.
Czech people
Czechs, or Czech people are a western Slavic people of Central Europe, living predominantly in the Czech Republic. Small populations of Czechs also live in Slovakia, Austria, the United States, the United Kingdom, Chile, Argentina, Canada, Germany, Russia and other countries...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
best known today for his work in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, long before this was an established mathematical discipline.
He was born in Uherský Ostroh
Uherský Ostroh
Uherský Ostroh is a town in the Uherské Hradiště District, Zlín Region, Czech Republic, located about 11 km southwest of Uherské Hradiště. It lies in the ethnographic Slovácko region....
, a town in Moravia
Moravia
Moravia is a historical region in Central Europe in the east of the Czech Republic, and one of the former Czech lands, together with Bohemia and Silesia. It takes its name from the Morava River which rises in the northwest of the region...
(then in Austria-Hungary
Austria-Hungary
Austria-Hungary , more formally known as the Kingdoms and Lands Represented in the Imperial Council and the Lands of the Holy Hungarian Crown of Saint Stephen, was a constitutional monarchic union between the crowns of the Austrian Empire and the Kingdom of Hungary in...
, later Czechoslovakia
Czechoslovakia
Czechoslovakia or Czecho-Slovakia was a sovereign state in Central Europe which existed from October 1918, when it declared its independence from the Austro-Hungarian Empire, until 1992...
; today Czech Republic
Czech Republic
The Czech Republic is a landlocked country in Central Europe. The country is bordered by Poland to the northeast, Slovakia to the east, Austria to the south, and Germany to the west and northwest....
), and he attended the grammar school in Uherské Hradiště
Uherské Hradište
Uherské Hradiště is a town in the Zlín Region of the Czech Republic. It lies on the Morava river and is the seat of the Uherské Hradiště District.- History :...
, before changing in 1916 to the military school in Hranice and later enrolling into the military technical academy in Mödling
Mödling
Mödling is the capital of the Austrian district of the same name located approximately 14 km south of Vienna.The settlement dates back to the Neolithic. In medieval times, the town was the residence of a branch of the Babenberger family, as a result of which it received the nickname...
near Vienna
Vienna
Vienna is the capital and largest city of the Republic of Austria and one of the nine states of Austria. Vienna is Austria's primary city, with a population of about 1.723 million , and is by far the largest city in Austria, as well as its cultural, economic, and political centre...
. After the end of World War I
World War I
World War I , which was predominantly called the World War or the Great War from its occurrence until 1939, and the First World War or World War I thereafter, was a major war centred in Europe that began on 28 July 1914 and lasted until 11 November 1918...
, he graduated in 1918 back at the grammar school in Uherské Hradiště.
In his 1926 paper O jistém problému minimálním (English On a certain minimal problem), Borůvka described an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for finding the minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
of an electrical network
Electrical network
An electrical network is an interconnection of electrical elements such as resistors, inductors, capacitors, transmission lines, voltage sources, current sources and switches. An electrical circuit is a special type of network, one that has a closed loop giving a return path for the current...
, now called Borůvka's algorithm
Boruvka's algorithm
Borůvka's algorithm is an algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct.It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia....
. His results were later discovered by the theoretical computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
community.