Граф — способ записать «кто с кем связан», и почти все задачи главы решаются пересчётом рёбер и степеней. Одно соотношение закрывает половину из них.
Что нужно знать
- Граф задаётся вершинами и рёбрами; степень вершины — число рёбер, выходящих из неё.
- Сумма степеней всех вершин вдвое больше числа рёбер: каждое ребро считается с двух концов.
- Отсюда следует, что вершин нечётной степени всегда чётное число.
- Граф связен, если из любой вершины можно дойти до любой другой.
- Дерево — связный граф без циклов; в нём ровно на одно ребро меньше, чем вершин.
- Эйлеров путь (по всем рёбрам, каждому один раз) существует, если вершин нечётной степени не больше двух.
- В ориентированном графе рёбра имеют направление, и связность проверяется с его учётом.
Где чаще всего ошибаются
- Считают степенью число соседей, забывая про кратные рёбра и петли.
- Забывают, что в дереве ровно $n-1$ ребро.
- Путают эйлеров путь (по рёбрам) и гамильтонов (по вершинам).
- Проверяют связность ориентированного графа, игнорируя направления.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 30 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Вероятность и статистика · 10 класс · Высоцкий, 2025 · Глава 2 · Элементы теории графов