Номер 16, часть 2 — ГДЗ Вероятность и статистика 8 класс Высоцкий, Ященко
Учебник «Вероятность и статистика. 7–9 классы», часть 2, с. 9, §47*
№16. Будет ли связным граф, который получится из дерева, если из него удалить:
а) ребро, связывающее две неконцевые вершины;
б) концевую вершину вместе с выходящим из неё ребром?
✎ Запись в тетрадь
Дано:
дерево
Найти:
связность после удаления а) ребра между неконцевыми; б) конца с ребром
Дерево связно: любые две вершины соединены единственной цепью.1
а) убрали ребро ⇒ единственная цепь оборвана ⇒ 2 части, не связен.2
б) убрали конец с ребром ⇒ остальные соединены как раньше, связен.3
Ответ: а) нет; б) да.
Пояснение
Идея. В дереве любые две вершины соединены единственной цепью (теорема §47*). Поэтому каждое ребро — единственный мост между своими частями, а концевая вершина ни одну цепь между других вершин не проводит.
1Опорный факт — теорема §47*: между двумя вершинами дерева ровно одна цепь. Любое удаление нужно сравнить с этим фактом.
2Ребро между двумя неконцевыми вершинами лежит на единственной цепи между тем, что с одной стороны, и тем, что с другой. После удаления пройти из одной части в другую нельзя — граф распадается на две части (по свойству 1 из §47*: без ребра дерево перестаёт быть связным).
3Концевая вершина — «конец» цепей, никакая цепь между остальными вершинами через неё не идёт. Остальные цепи остаются, граф связен (и по-прежнему дерево).
