Остовное дерево графа. Теорема Прима о минимальном остовном дереве (МОД)
ДОБАВИТЬ В КОНСПЕКТ
НАВИГАЦИЯ ПО СТРАНИЦЕ
ПОЛНЫЙ ОТВЕТ
БЕЗ ВОДЫ
Без воды — краткий вариант ответа,
легко понять и запомнить
легко понять и запомнить
Остовное дерево – суграф связного графа со свойствами дерева.
Минимальное остовное дерево – остовное дерево взвешенного графа с минимальным суммарным весом.
Теорема Прима. Если для уже известно некоторое поддерево – поддерево МОД то присоединив к нему новое ребро где – поддерево МОД
Полезные ссылки:
