#Алгоритмические вопросы теории графовАлгоритмические вопросы теории графовИсследуйте Области знанийУ нас представлены тысячи статейТегАлгоритмические вопросы теории графовАлгоритмические вопросы теории графовНайденo 4 статьиТерминыТермины Минимальное остовное деревоМинима́льное осто́вное де́рево, в связном неориентированном графе со взвешенными рёбрами – дерево, являющееся подграфом множество вершин которого совпадает со множеством вершин графа (т. е. являющееся остовным деревом), а суммарный вес рёбер минимален. Веса рёбер могут быть любыми действительными числами, и никакие ограничения, например, неотрицательность или неравенство треугольника, на них не накладываются.Алгоритмы Алгоритм ПримаАлгори́тм При́ма, алгоритм построения минимального остовного дерева во взвешенном связном неориентированном графе. Впервые предложен в 1930 г. В. Ярником и позднее переоткрыт Р. Примом. Алгоритм является жадным.Алгоритмы Алгоритм БорувкиАлгори́тм Бору́вки, алгоритм построения минимального остовного дерева во взвешенном связном неориентированном графе. Предложен в 1926 г. в работах чешского математика О. Борувки, тогда же первым опубликовавшего саму постановку задачи.Алгоритмы Алгоритм КраскалаАлгори́тм Кра́скала, алгоритм построения минимального остовного дерева во взвешенном связном неориентированном графе. Предложен Дж. Краскалом в 1956 г. Алгоритм является жадным.
