Кратко по теме
Сначала разберите алгоритм и пример на презентации; письменно выполните задания ниже. УМК ФГОС: данные → действие → проверка результата. Графы — это способ наглядно представить связи между объектами. В этой теме мы научимся описывать графы с помощью весовой матрицы, находить длину пути между вершинами и считать количество различных путей в направленных ациклических графах (DAG). Это основа для понимания алгоритмов поиска путей, которые используются в навигаторах, социальных сетях и интернете.
Опора
- Весовая матрица для графа с n вершинами имеет размер n×n.
- Для невзвешенного графа весовая матрица содержит 1 (если есть ребро) и 0 (если нет).
- В направленном графе матрица может быть несимметричной: вес из A в B не обязан равняться весу из B в A.
- Длина пути в взвешенном графе — это сумма весов всех рёбер пути. Например, если путь A→B (вес 3) и B→C (вес 5), то длина пути A→C равна 8.
- Количество путей в ациклическом графе можно вычислить по формуле: f(v) = сумма f(u) для всех u, из которых есть ребро в v, при этом f(начальной вершины) = 1.
- Граф — это математическая модель, состоящая из вершин и рёбер, которые соединяют пары вершин.
Задания
- 1Таблица: понятие / определение / пример — 4 строки по «Граф. Весовая матрица графа. Длина пути между вершинами графа. Вычисление количества путей в направленном ациклическом графе».
бланк · таблица
Заполните таблицу по столбцам
понятие определение - 2Игра «Найди пару»: «данные ↔ обработка», «алгоритм ↔ шаги», «ошибка ↔ проверка».
бланк · соедини карточки
Соедините пары линиями или запишите соответствия (А–1, Б–2…)
данныеалгоритмошибкаобработкашагипроверкаСоответствия: А— Б— В—