Элементы теории графов, 10 класс — тест по главе 2

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

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

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

Одинаковое число вершин и рёбер изоморфизма не доказывает

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

Планарный и плоский — не синонимы

Планарный граф допускает изображение без пересечения рёбер, а плоский — это уже такое изображение. Один и тот же граф можно нарисовать и с пересечениями, и без них; планарность от рисунка не зависит. Различение проверяется отдельным заданием.

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

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

Как проходит работа

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