ТехноФорум

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

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

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

Варианты для реферата (применение т. графов):
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

Тезисно:
- применение в транспортных задачах: вершины графа - это пункты , а ребра - дороги (авто, ж-д)
- технологические задачи: вершины - производственные элементы (заводы, цеха, станки), а дуги - потоки сырья, материалов, продукции.. Суть - в определение оптимальной загрузки производственных элементов, потоков

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

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