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