4511
правок
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Перейти к навигации
Перейти к поиску
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:28, 16 апреля 2016
, 16 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) м (Irina переименовал страницу Рандомизированное минимальное остовное дерево в [[Рандомизированный алгоритм нахождения минимального осто…) |
Irina (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
На входе имеется связный неориентированный граф G = (V, E) с весом w(e) каждого ребра e | На входе имеется связный неориентированный граф G = (V, E) с весом w(e) каждого ребра <math>e \in E \;</math>. Задача заключается в нахождении [[остовное дерево|остовного дерева]] с минимальным весом, где для любого подмножества ребер <math>E' \subseteq E \;</math> [[вес]] E' определяется как <math>w(E') = \sum_{e \in E'} w(e) \;</math>. | ||
Если граф G не является связным, задача заключается в нахождении минимального остовного леса, который определяется как совокупность минимальных остовных деревьев для каждой связной компоненты G. Обе задачи будут обозначаться как MST (minimum spanning tree). | Если граф G не является [[связный граф|связным]], задача заключается в нахождении [[минимальный остовный лес|минимального остовного леса]], который определяется как совокупность минимальных остовных деревьев для каждой связной компоненты G. Обе задачи будут обозначаться как MST (minimum spanning tree). | ||