Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 87, §20
№133. Найдите на рисунке 31 три разных цикла.
Дано:
граф на рисунке 31: вершины A, B, C, D, E, F
Найти:
три разных цикла
Цикл — это замкнутый путь: он начинается и заканчивается в одной вершине, а рёбра и промежуточные вершины не повторяются (п. 20). Рёбра графа на рисунке 31: AC, CD, DE, AF, FB, DF, EB, а также AD и FE. Будем искать замкнутые «обходы» из нескольких рёбер.
1) Обойдём левый квадрат: A → C → D → F → A. Рёбра AC, CD, DF и FA есть, вершины не повторяются. Цикл ACDF (четыре вершины).
2) Обойдём «параллелограмм» с двумя диагоналями: A → D → E → F → A. Рёбра AD, DE, EF и FA есть. Цикл ADEF.
3) Самый короткий цикл — треугольник A → C → D → A: рёбра AC, CD и DA. Цикл ACD.
Все три цикла разные (у них разные наборы рёбер). Начальной вершиной цикла можно считать любую, поэтому цикл ACD можно записать и как CDA, и как DAC — это один и тот же цикл. Ответ не единственный: всего в этом графе 10 циклов (4 треугольника, 3 четырёхугольника, 2 пятиугольника и 1 шестиугольник — проверено перебором).
Ответ: Например, ACDF, ADEF, ACD.
