Графы: матрица и списки смежности, жадные алгоритмы, остовное дерево, алгоритмы Дейкстры и Флойда — Уоршелла — тест для 9 класса

Карта метро, дороги между городами, друзья в социальной сети, компьютерная сеть — всё это графы. Тема 9 класса учит хранить граф в программе и решать на нём две классические задачи: соединить все вершины самыми дешёвыми рёбрами и найти кратчайший путь.

Что проверяется

Вершины, рёбра, степень вершины, ориентированные и взвешенные графы. Способы описания: матрица смежности и её симметричность, списки смежности, список рёбер. Жадные алгоритмы и случаи, когда жадный выбор оптимален и когда нет. Минимальное остовное дерево, число его рёбер, алгоритм Краскала. Алгоритм Дейкстры: порядок окончательной обработки вершин, ограничение на отрицательные веса. Алгоритм Флойда — Уоршелла: формула пересчёта, сложность, признак отрицательного цикла.

Задания

Пятнадцать заданий: найти степень вершины и число единиц в матрице смежности, найти кратчайший путь и порядок обработки вершин алгоритмом Дейкстры, построить остовное дерево и разделить рёбра на включённые и отброшенные, вставить пропуски в формулу Флойда, выбрать задачи, где жадный алгоритм даёт оптимум.

Разбор

Пояснения показывают, почему жадная выдача сдачи монетами 1, 3 и 4 рубля ошибается, почему Дейкстра не работает с отрицательными рёбрами, почему в остовном дереве на n вершинах ровно n − 1 рёбер и как отрицательное число на диагонали матрицы Флойда выдаёт отрицательный цикл.

Назначение

Работа рассчитана на четыре часа графов. Задачи на графы входят и в ОГЭ, и в олимпиады, а алгоритм Дейкстры встретится снова в профильных классах — в технологиях связи и маршрутизации. Девятый класс завершает трёхлетний курс «Программирование» ИТ-вертикали: тридцать четыре часа на Python, посвящённые структурам данных и классическим алгоритмам. Это материал, с которого начинаются олимпиадная информатика и профильные ИТ-классы, куда поступает большинство выпускников вертикали. Эта работа — четвёртая из 5 по курсу.

Организация тестирования

Тестирование одинаково удобно и на компьютере, и на смартфоне. Есть возможность настроить срок сдачи, что позволяет назначать комплект на дом. Чтобы снизить риск списывания, фиксируются попытки переключиться на другие вкладки браузера или другие приложения.