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

Учебник «Вероятность и статистика. 7–9 классы», часть 2, с. 6, §46

№4. В графе рёбрами соединены вершины $A$ и $B$ , $B$ и $C$ , $A$ и $C$ . Является ли этот граф деревом?

✎ Запись в тетрадь

Дано:

рёбра

A B

BC

A C

Найти:

является ли граф деревом

Связный: любая вершина соединена с любой.1

Есть цикл:

A \to B \to C \to A

Рёбер 3, вершин 3, а у дерева рёбер на 1 меньше.3

Ответ: нет, граф содержит цикл

A \to B \to C \to A

Идея. Дерево — связный граф без циклов (§46). Рисуем граф по описанию и ищем замкнутый путь.

1Любые две вершины соединены ребром, значит, граф связный. Но связность — только половина определения.
2Из A можно пройти в B, из B в C, из C обратно в A, не повторяя рёбра: получили цикл. Одного цикла хватает, чтобы дерева не было.
3То же видно подсчётом: у дерева с тремя вершинами должно быть два ребра (число рёбер на 1 меньше числа вершин). Здесь лишнее третье ребро замыкает цикл.

Частая ошибка. Решить, что раз граф связный, то он дерево. Нужны оба условия: связность и отсутствие циклов.