Повторить перед темойГрафы Что дальшеОперации над событиями

Деревья и правило умножения: онлайн-тренажёр для 8 класса

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

УровниРазминкаОсновнойСложный

Решить 3 задачи бесплатно ↓ Весь тренажёр — 14 дней бесплатно

Глава «Деревья и правило умножения»6 уроков

3 задачи по теме — реши здесь без регистрации

Решено 0 из 3

Разминка3 задания

здесьздесь

Основной5 заданий

здесь

Сложный4 задания

Ещё 9 заданий ждут в тренажёре

3 из 12решаются на этой странице

Подсказка и пошаговое решение каждой задачи
6 уроков с теорией и чертежами
Отчёт для родителя: что решено и где ошибки

Открыть все — 14 дней бесплатно

Пробуйте. Условия — для родителей

Уровни сложности

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

РазминкаВспомнить и разогреться · 3 задания

Пример условия

В дереве 18 вершин. Сколько в нём рёбер? Ответ запишите числом.

2 задачи этого уровня — выше, бесплатно Ещё 1 —в полном тренажёре

ОсновнойТо, что спросят в школе · 5 заданий

Пример условия

Код состоит из двух гласных букв (из пяти: А, Е, И, О, У, повторы разрешены) и двух цифр от 0 до 9. Сколько существует таких кодов? Ответ запишите числом.

1 задача этого уровня — выше, бесплатно Ещё 4 —в полном тренажёре

СложныйС подвохом, но по силам · 4 задания

Пример условия

Сколько нечётных четырёхзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, если цифры в числе не повторяются? Ответ запишите числом.

Все 4 задания — в полном тренажёре 14 дней бесплатно →

Коротко о теме

Сеть водопровода, схема папок в компьютере, родословная — графы особого вида: в них всё связано, но нет ни одного цикла. Такие графы называют деревьями.

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

У дерева с семью вершинами шесть рёбер, у дерева с восемью — семь. Докажем, что у любого дерева рёбер на одно меньше, чем вершин, и научимся пользоваться этим в задачах.

Определение
Дерево — связный граф, в котором нет циклов. Вершину степени 1 в графе называют висячей: из неё выходит ровно одно ребро.
Свойство
1) Если из дерева удалить любое ребро, граф перестанет быть связным. 2) Между любыми двумя вершинами дерева есть ровно одна цепь. 3) В дереве, где не меньше двух вершин, есть хотя бы две висячие вершины.

Разобранный пример

Условие. Какие из графов — деревья? Граф 1: рёбра P — Q, Q — R, Q — S, S — T. Граф 2: рёбра P — Q, Q — R, R — P, R — S. Граф 3: вершины P, Q, R, S, рёбра P — Q и R — S.

Ответ. Дерево — только граф 1.

Как к этому прийти — по шагам

3 шага с пояснениями — в полном тренажёре, в уроке «Дерево — граф без циклов».

Открыть разбор →

Частые ошибки

Ошибка 1
Граф из двух отдельных деревьев — например, рёбра K — L и M — N — O — назвали деревом, потому что в нём нет циклов. Неверно: из K не дойти до M. Дерево обязано быть связным.
Ошибка 2
Вершину, из которой не выходит ни одного ребра, назвали висячей. Висячая вершина — степени 1: она «висит» на одном ребре. Вершина степени 0 в дереве с двумя и более вершинами не встречается — дерево связное.
Ошибка 3
«У любого графа есть висячие вершины» — неверно: в графе-треугольнике K — L — M — K у всех вершин степень 2. Свойство 3 — про деревья: там нет циклов, и самая длинная цепь кончается висячей вершиной.