Половина задач этой главы закрывается одним соотношением: сумма степеней вершин вдвое больше числа рёбер. Отсюда сразу следует, что вершин нечётной степени не может быть нечётное число.
Что нужно знать
- Граф задают вершинами и рёбрами; степень вершины — число рёбер, выходящих из неё.
- Сумма степеней всех вершин равна удвоенному числу рёбер: каждое ребро считается с обоих концов.
- Следствие («лемма о рукопожатиях»): вершин нечётной степени всегда ЧЁТНОЕ число.
- Путь — последовательность рёбер без повторов, цикл — замкнутый путь.
- Граф связен, если из любой вершины достижима любая; иначе он распадается на компоненты связности.
- В полном графе соединены все пары вершин; в двудольном вершины делятся на две группы, и рёбра идут только между группами.
- Один и тот же граф можно нарисовать по-разному: важны связи, а не расположение точек на бумаге.
Где чаще всего ошибаются
- Рисуют граф, в котором нечётных вершин нечётное число, — такого не бывает.
- Считают разные рисунки одного графа разными графами.
- Путают ребро (одно соединение) и путь (цепочку рёбер).
- Забывают про петли и кратные рёбра при подсчёте степени.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Вероятность и статистика · 7 класс · Высоцкий, 2025 · Глава 4 · Графы