Аннотация:
В 1925 г. в Чехословакии встала задача соединения отдельных электрических сетей в одну с минимальной стоимостью прокладки. Решение было найдено практически сразу математиком Отакаром Борувкой (1899–1995), но его обоснование заняло почти год. Через 4 года (1930) более простой алгоритм на языке теории графов нашел Войтек Ярник (1897–1970). Через четверть века оба эти алгоритма на языке теории графов переоткрыли американцы из лаборатории Bell: Краскал (Joseph Bernard Kruskal, Jr., 1956) и Прим (Robert Clay Prim, 1957).
Эти алгоритмы принесли компаниям, строившим сети (телефонные, электрические, оптико-волоконные и др.) миллиарды долларов дохода.
Рассмотрим предметы живописи. Даже в известных музеях (в том числе и в Эрмитаже) немало полотен, автор которых неизвестен. Но оказалось, что на языке теории графов, правда, с помощью компьютеров, во многих случаях удается решать проблему атрибуции (определения авторства) и датировки.
