Учебная работа № 3563. «Курсовая Алгоритм построения дерева минимального веса в неориентированом графе
Учебная работа № 3563. «Курсовая Алгоритм построения дерева минимального веса в неориентированом графе
Содержание:
«ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ ……………………………………………………………………………………………….3
ГЛАВА 1 Основные понятия и определения теории графов ………………………..5
1.1 Основные термины теории графов …………………………………………………5
1.2 Виды и характеристики графов ……………………………………………………..9
ГЛАВА 2 ПРАКТИЧЕСКИЕ ПРИЛОЖЕНИЯ ГРАФОВ …………………………..16
2.1 Алгоритм Краскала нахождения остова минимального веса ….17
2.1 Алгоритм Прима нахождения остова минимального веса ……..17
2.3 Построение остовного дерева минимальной стоимости (алгоритм Прима)…………………………………………………..……………21
2.4 Примеры применения программы ……………………………..
ЗАКЛЮЧЕНИЕ ……………………………………………………………………………………….24
СПИСОК ИСПОЛЬЗОВАНЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ……………25
ПРИЛОЖЕНИЕ А ……………………………………………………………………………………26
»
Выдержка из похожей работы
том числе несвязный) граф без циклов
называетсяациклическим ,
Несвязный граф, каждая компонента
связности которого является деревом,
называется лесом, Можно сказать, что
деревья являются компонентами леса, На
рис, 6,1 изображены два дереваG1,G2и лесG3,Рис, 6,1
Сформулируем
основные свойства деревьев, Сделаем
это в виде совокупности
утверждений, которые эквивалентны между
собой (т,е, из любого утверждения следует
любое другое) ,Теорема 6,1,
ПустьG(X,E) – неориентированный
граф сpвершинами иqребрами, Тогда следующие утверждения
эквивалентны,1,Gесть дерево,2,
Любые две различные вершиныxиyграфаGсоединены единственной
простой цепью
