Графы: пути, циклы и деревья, 8 класс
Что здесь изучим? Познакомимся с графами — удобным языком для описания связей между объектами.
Объяснение
Граф — это набор точек, которые называют вершинами, соединённых линиями, которые называют рёбрами. Графы используют для описания связей: дорог между городами, дружбы между людьми, ходов в игре и так далее. Число рёбер, выходящих из вершины, называют степенью вершины.
Путь в графе — это последовательность рёбер, по которым можно пройти от одной вершины к другой, не повторяя рёбер. Цикл — это путь, который начинается и заканчивается в одной и той же вершине. Граф называют связным, если из любой его вершины можно добраться до любой другой по рёбрам графа.
Дерево — это особый вид графа: связный граф без циклов. У дерева с n вершинами всегда ровно n − 1 рёбер — на одно меньше, чем вершин. Деревья часто используют для изображения иерархий (родословные, файловая система) и для деревьев случайного эксперимента в теории вероятностей.
Правило
- Сумма степеней всех вершин графа равна удвоенному числу рёбер.
- Дерево с n вершинами имеет ровно n − 1 рёбер и не содержит циклов.
Разобранные примеры
Пример 1. В графе 5 вершин, и он является деревом. Сколько у него рёбер?
- У дерева рёбер на 1 меньше, чем вершин
- 5 − 1
Ответ: 4 ребра
Пример 2. Граф имеет 4 вершины со степенями 3, 2, 2, 1. Найдите число рёбер.
- Сумма степеней равна удвоенному числу рёбер
- 3 + 2 + 2 + 1 = 8
- Число рёбер: 8 ÷ 2
Ответ: 4 ребра
Пример 3. Есть ли цикл в связном графе с 6 вершинами и 5 рёбрами?
- У дерева с 6 вершинами было бы 6 − 1 = 5 рёбер — как раз наш случай
- Связный граф с n вершинами и n−1 рёбрами — это дерево, значит циклов нет
Ответ: нет, это дерево
Типичные ошибки
Число рёбер посчитали равным сумме степеней вершин
Каждое ребро добавляет по единице степени сразу двум вершинам, поэтому сумма степеней в 2 раза больше числа рёбер, а не равна ему.
Решили, что любой связный граф — это дерево
Деревом является только связный граф БЕЗ циклов. Связный граф с циклами (например, с рёбрами, образующими «треугольник») деревом не является.
Проверь себя
1. Дерево имеет 8 вершин. Сколько у него рёбер?
Показать ответ
7
2. Граф имеет вершины со степенями 1, 1, 2, 2, 2. Сколько у него рёбер?
Показать ответ
4
3. Связный граф имеет 7 вершин и 6 рёбер. Является ли он деревом?
Показать ответ
да