Тема 10 · Вероятность и статистика
Пути, циклы и эйлеров обход
Цепи и циклы, эйлеров путь, ориентированные графы, деревья. 100 заданий на отработку.
Простыми словами
Можно ли нарисовать «конверт», не отрывая карандаша от бумаги и не проводя линию дважды? Это задача об эйлеровом пути: пройти по всем рёбрам графа ровно по одному разу. Ответ даёт простое правило про степени вершин.
Цепь (путь) — последовательность рёбер, где каждое следующее начинается там, где закончилось предыдущее.
Цикл — замкнутая цепь без повторения рёбер: начало и конец совпадают.
Граф-цикл
Если вершин соединены «по кругу», получается цикл из вершин.
В цикле из вершин ровно рёбер, и степень каждой вершины равна 2.
Цикл из 7 вершин: рёбер 7, степень каждой вершины 2 (сумма степеней ✓).
Эйлеров путь и цикл
Эйлеров путь проходит по каждому ребру ровно один раз. Если он ещё и возвращается в начальную вершину — это эйлеров цикл.
Для связного графа считаем вершины нечётной степени:
• нечётных вершин — есть эйлеров цикл (начать можно где угодно);
• нечётные вершины — есть эйлеров путь, он начинается в одной нечётной вершине и кончается в другой;
• больше двух — обойти все рёбра по одному разу нельзя.
Можно ли нарисовать «конверт» одним росчерком?
- Степени: 3, 3, 4, 4, 2.
- Нечётных вершин две (нижние) — эйлеров путь есть.
- Начинать нужно в нижней вершине, закончим в другой нижней.
Почему так: проходя через вершину, мы «входим и выходим» — тратим 2 ребра. Нечётное число рёбер может остаться только у начала и конца пути.
Задача о семи мостах Кёнигсберга: обойти город, пройдя по каждому мосту один раз. Л. Эйлер в 1736 году показал, что это невозможно: в соответствующем графе все четыре вершины нечётные.
Деревья и ориентированные графы
Дерево — связный граф без циклов.
В дереве с вершинами ровно ребро, а путь между любыми двумя вершинами единственный. Удалите любое ребро — дерево распадётся на две части.
В дереве 12 вершин. Сколько рёбер? .
Ориентированный граф — граф, у рёбер которого есть направление (стрелки), как улицы с односторонним движением. Двигаться по ребру можно только по стрелке.
Не путайте: в цикле рёбер столько же, сколько вершин (), а в дереве — на одно меньше ().
Ещё задачи о графах
- Полный граф («каждая вершина соединена с каждой»): степень каждой вершины , рёбер ; при — 3 ребра, при степени по 4.
- Дерево: в дереве с вершинами не меньше двух висячих вершин (степени 1). Если к дереву добавить одно ребро, появится ровно один цикл; если из цикла удалить одно ребро, получится дерево (цепь). Связный граф с 7 вершинами и 6 рёбрами — дерево, циклов нет; связный граф с 3 вершинами и 3 рёбрами — один цикл. Дерево из 4 вершин в виде цепи превращается в цикл добавлением одного ребра.
- Пути по циклу: между двумя вершинами цикла ровно два пути без повторов рёбер — по часовой стрелке и против; к соседней вершине по часовой стрелке — одно ребро. Самый длинный путь без повторов рёбер в цикле из 7 вершин — 7 рёбер (весь цикл); обойти все 8 рёбер цикла и вернуться — 8 рёбер.
- Не в любом связном графе есть эйлеров цикл; если все степени чётны — есть (а значит, и эйлеров путь). При ровно двух нечётных вершинах эйлеров путь есть, но цикла нет.
Готовые работы по теме
Собраны заранее — одним нажатием: распечатать с ключом, раздать ученикам ссылкой или QR-кодом, поменять настройки. Номер набора постоянный: по этой ссылке всегда та же работа.
теория этой темы, 8 заданий по подтемам и ключ — файлом DOCX, который можно править под себя.
Прохождение онлайн
Имя ученика никуда не отправляется: он вводит только номер по списку, а таблицу «номер → фамилия» видите только вы.
Классы, выданные работы и результаты учеников по кодам — в журнале учителя: без регистрации, хранится только на этом компьютере.