Номер 136, часть 1 — ГДЗ Вероятность и статистика 7 класс Высоцкий, Ященко

Длина цикла — число его рёбер. Цикл — замкнутый путь без повторений (п. 20). Как придумать граф с нужными циклами? Возьмём две вершины и соединим их тремя разными путями, у которых нет общих вершин, кроме концов. Любые два из этих путей вместе образуют цикл, поэтому в таком графе три цикла. Если длины путей $a$, $b$ и $c$ (в рёбрах), то длины циклов будут $a+b$, $a+c$ и $b+c$.

а) Нужны длины циклов 3, 4 и 5: $a+b=3$, $a+c=4$, $b+c=5$. Подойдёт $a=1$, $b=2$, $c=3$ (проверьте: $1+2=3$, $1+3=4$, $2+3=5$). Значит, между вершинами А и Б проводим три пути: прямое ребро АБ (длина 1), путь АВБ через одну вершину (длина 2) и путь АГДБ через две вершины (длина 3).

Циклы получаются такие: АВБ (ребро АБ и путь АВБ — 3 ребра: АВ, ВБ, БА), АГДБ (ребро АБ и путь АГДБ — 4 ребра) и АВБДГ (путь АВБ и путь АГДБ — 5 рёбер: АВ, ВБ, БД, ДГ, ГА).

б) Нужны длины 4, 4 и 6: $a+b=4$, $a+c=4$, $b+c=6$. Подойдёт $a=1$, $b=3$, $c=3$. Получается «домино» — два квадрата с общей стороной БД: в нём шесть вершин и семь рёбер. Циклы: квадрат АБДГ (4 ребра), квадрат БВЕД (4 ребра) и внешний контур АБВЕДГ (6 рёбер).

Проверка. Мы перебрали все циклы построенных графов: в графе а) их ровно три (длины 3, 4, 5), в графе б) тоже три (длины 4, 4, 6), других циклов нет.

Замечание. Задача имеет много ответов. Например, для а) подойдёт и граф из трёх отдельных частей — треугольника, четырёхугольника и пятиугольника.