Лекция от 06.04

Подфорум по дисциплине "Алгоритмы и структуры данных". Направление ПИ, КубГТУ, 1 курс
Аватара пользователя
admin
Администратор
Сообщения: 1838
Зарегистрирован: 27 июл 2018, 18:43
Откуда: apsheronsk.bozo.ru
Контактная информация:

Лекция от 06.04

Сообщение admin » 05 апр 2020, 16:02

Тема: "Графы. Прикладные функции взаимодействия с графами"

Основное направление: "Применение теории графов в прикладных задачах"

А) Остовные деревья графов. Алгоритм Прима
Б) Задача поиска кратчайшего пути
В) Сетевой график. Построение сетевого графика
Г) Критический путь сетевого графика
Д) Графы и матрицы

Варианты для реферата (применение т. графов):
0. Транспортные и технологические задачи
1. Схемы авиалиний
2. Схемы электрических сетей
3. Блок-схемы программ
4. Исследование лабиринтов
5. Репозиторий GitHub
6. Задача о 4-х красках
7. Задача о рукопожатиях

Интернет-источники:
1. История теории графов https://habr.com/ru/post/346440/
2. https://proglib.io/p/graph-theory
3. https://e-maxx.ru/algo/mst_prim

Тезисно:
- применение в транспортных задачах: вершины графа - это пункты , а ребра - дороги (авто, ж-д)
- технологические задачи: вершины - производственные элементы (заводы, цеха, станки), а дуги - потоки сырья, материалов, продукции.. Суть - в определение оптимальной загрузки производственных элементов, потоков
Вложения
graf_evsteg.jpg
Применение теории графов в программировании (1985 год)
graf_evsteg.jpg (56.18 КБ) 1272 просмотра
программисту на заметку:
За программу без багов и недоделок ты получаешь деньги единожды, а программа с багами и недоделками кормит тебя всю жизнь.
anekdot.ru

Аватара пользователя
admin
Администратор
Сообщения: 1838
Зарегистрирован: 27 июл 2018, 18:43
Откуда: apsheronsk.bozo.ru
Контактная информация:

Re: Лекция от 06.04

Сообщение admin » 05 апр 2020, 18:55

Дополнительные задачи для самопроверки:
1. Найдется ли граф с пятью вершинами, у которого одна вершина изолированная, а другая — степени 4?
2. Нарисуйте граф Г с пятью вершинами, у которого ровно две вершины имеют одинаковую степень. // Л.Ю. Березина
программисту на заметку:
За программу без багов и недоделок ты получаешь деньги единожды, а программа с багами и недоделками кормит тебя всю жизнь.
anekdot.ru

stdi
Сообщения: 3
Зарегистрирован: 15 май 2020, 16:13

Re: Лекция от 06.04

Сообщение stdi » 15 май 2020, 16:20

а как найти критический путь графа?


Вернуться в «Алгоритмы и структуры данных»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 2 гостя