В формуле Эйлера В − Р + Г = 2 чаще всего теряют внешнюю грань — ту бесконечную область, что осталась снаружи рисунка. Её считают тоже.
Что нужно знать
- Дерево — связный граф без циклов; в нём рёбер ровно на одно меньше, чем вершин.
- Между любыми двумя вершинами дерева существует РОВНО ОДИН путь.
- Добавление любого ребра к дереву создаёт ровно один цикл, удаление любого — разрывает связность.
- Плоским называют граф, который можно нарисовать без пересечения рёбер.
- Для связного плоского графа В − Р + Г = 2, где Г — число граней ВМЕСТЕ с внешней.
- Не всякий граф плоский: полный граф на пяти вершинах нарисовать без пересечений нельзя.
- Деревья используют для упорядоченного перебора вариантов: каждая ветвь — один вариант.
Где чаще всего ошибаются
- Забывают внешнюю грань и получают В − Р + Г = 1.
- Считают, что любой граф можно нарисовать без пересечений.
- Называют деревом связный граф с циклом.
- Применяют формулу Эйлера к несвязному графу.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Вероятность и статистика · 8 класс · Высоцкий, 2025 · Глава 10 · Деревья и плоские графы