Графы, 7 класс — тест по главе 4

Схема метро, список знакомств в классе и сеть дорог между городами устроены по-разному, но у всех трёх одна и та же математическая суть: точки и связи между ними. Граф — это язык, на котором такие задачи перестают быть головоломками и становятся вычислениями.

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

Устройство графа: вершины, рёбра, изображение отношения между объектами в виде схемы. Степень вершины и подсчёт степеней по рисунку или описанию. Связь между суммой степеней всех вершин и числом рёбер. Пути в графе, связный граф и распадающийся на части. Задача о кёнигсбергских мостах и её решение: условие существования эйлерова пути и эйлерова цикла через число нечётных вершин. Ориентированные графы, где у ребра есть направление, и разница между входящей и исходящей степенью. Перевод условия задачи со словами о знакомствах, рукопожатиях или дорогах на язык вершин и рёбер.

Сумма степеней вдвое больше числа рёбер

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

Кёнигсбергские мосты — не про мосты

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

Как устроена работа

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

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

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