Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 88, §20
№135. Укажите, какие графы на рисунке 32 содержат цикл.
Дано:
рисунок 32: девять графов
Найти:
номера графов, содержащих цикл
Граф содержит цикл, если в нём можно, идя по рёбрам, выйти из некоторой вершины и вернуться в неё, не повторяя ни рёбер, ни промежуточных вершин (п. 20). Такой замкнутый обход и есть цикл; он может быть всем графом или только его частью. Рисунок 32 — тот же, что в №134; точки пересечения линий вершинами не считаем.
Просмотрим все девять графов:
| Граф | Есть цикл | Что в нём |
|---|---|---|
| 1 | нет | нет циклов: это цепь — из любой вершины нельзя вернуться в неё же, не повторяя рёбер |
| 2 | да | цикл — весь граф (пять вершин, пять рёбер) |
| 3 | да | два цикла: внешний (четыре вершины) и внутренний треугольник |
| 4 | да | цикл — весь граф (восемь вершин, две линии пересекаются вне вершин) |
| 5 | нет | нет циклов: это цепь |
| 6 | да | три цикла: два треугольника (диагональ делит квадрат пополам) и сам квадрат |
| 7 | да | два цикла — оба четырёхугольника (у них общая вершина) |
| 8 | нет | нет циклов: это одно ребро |
| 9 | да | два цикла: внутренний (четыре вершины) и внешний (шесть вершин), у них общая вершина |
Итак, цикл содержат графы 2, 3, 4, 6, 7 и 9. Графы 1, 5 и 8 — цепи, циклов в них нет.
Замечание. В ответе учебника названы только графы 3, 6, 7 и 9: в них цикл — лишь часть графа. Графы 2 и 4 сами являются циклами (мы их выписали в №134, б), так что цикл в них тоже есть.
Ответ: Графы 2, 3, 4, 6, 7, 9 (в ответе учебника названы графы 3, 6, 7, 9 — те, у которых цикл составляет лишь часть графа; графы 2 и 4 сами являются циклами, см. №134, б).
