Дискретная математика, Часть III, Теория графов, Зарипова Э.Р., Кокотчикова М.Г., 2013

Построение минимального покрывающего дерева для связного взвешенного графа по алгоритму Прима.
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году. Алгоритм очень похож на алгоритм Дейкстры. Так же этот алгоритм называется алгоритмом поиска соседа.

Будем считать, что в данном алгоритме букет будет только один, этот букет будет включать в себя вершины дерева. Вводится дополнительное множество E' (на начальном этапе совпадающее с отсортированным множеством ребер Е), из которого мы будем удалять рассмотренные ребра.

Оглавление
I. КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ
Тема 1. Графы. Неориентированные графы: основные понятия: маршруты, цепи, циклы: связность: деревья и леса
Тема 2. Ориентированные графы: основные понятия: ориентированные маршруты, пути, контуры: сильная связность. Ориентированные деревья
Тема 3. Метрические характеристики графов. Матричное представление графов: матрица инцидентности для неорграфа. матрица смежности для неорграфа. матрица инцидентности для орграфа, матрица смежности для орграфа. Список смежности
Тема 4. Построение покрывающих деревьев. Алгоритм Краскала. Построение покрывающего дерева для связного графа. Построение минимального покрывающего дерева по алгоритму Краскала. Построение максимального покрывающего дерева по алгоритму Краскала
Тема 5. Построение минимального покрывающего дерева для связного взвешенного графа по алгоритму Прима. Построение максимального покрывающего дерева по алгоритму Прима
Тема 6. Поиск пути наименьшей длины в графе. Алгоритм Дейкстры
Тема 7. Эйлеровы графы. Алгоритм поиска эйлерова цикла в графе
Тема 7. Гамильтоновы графы. Сходство и различия гамильтоновых и эйлеровых графов. Достаточные условия существования гамильтоновых циклов. Способы поиска гамильтонова цикла. Алгоритм поиска гамильтонова цикла в графе
Тема 9. Поиск расстояния между всеми парами вершин. Алгоритм Уоршалла-Флойда
Тема 10. Задача построения транзитивного замыкания бинарного отношения. Алгоритм построения транзитивного замыкания бинарного отношения
Тема 11. Потоки. Условия существования потока. Увеличивающая цепь. Алгоритм поиска увеличивающей цепи. Увеличение потока вдоль найденной цепи по правилам
Тема 12. Потоки. Поиск максимального потока. Поиск потока минимальной стоимости
Тема 13. Задача почтальона для орграфов. Алгоритм поиска оптимального маршрута почтальона для орграфов
II. ФОНДЫ ОЦЕНОЧНЫХ СРЕДСТВ
1. Словарь (глоссарий) основных терминов и понятий
2. Методические указания для преподавателя, студента, слушателя
3. Сборник задач и упражнений
4. Лабораторный практикум по дисциплине
5. Описание балльно-рейтинговой системы
б. Вопросы для самопроверки и обсуждений по темам
7. Задания для самостоятельной работы по темам
8. Перечень рефератов и/или курсовых работ по темам
9. Тестовые задания по темам (для текущего и промежуточного самоконтроля)
10. Тренинговые задания
11. Перечень вопросов итоговой аттестации по курсу
III. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ
ЛИТЕРАТУРА.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Дискретная математика, Часть III, Теория графов, Зарипова Э.Р., Кокотчикова М.Г., 2013 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать книгу Дискретная математика, Часть III, Теория графов, Зарипова Э.Р., Кокотчикова М.Г., 2013 - pdf - depositfiles.

Скачать книгу Дискретная математика, Часть III, Теория графов, Зарипова Э.Р., Кокотчикова М.Г., 2013 - pdf - Яндекс.Диск.