Деревья и плоские графы, 8 класс — тест по главе 10

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

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

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

У дерева рёбер ровно на одно меньше, чем вершин

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

Дерево эксперимента не даёт потерять исход

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

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

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

Где и как проходить тест

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