ОК Математика

Графы: пути, циклы и деревья, 8 класс

Что здесь изучим? Познакомимся с графами — удобным языком для описания связей между объектами.

Объяснение

Граф — это набор точек, которые называют вершинами, соединённых линиями, которые называют рёбрами. Графы используют для описания связей: дорог между городами, дружбы между людьми, ходов в игре и так далее. Число рёбер, выходящих из вершины, называют степенью вершины.

Путь в графе — это последовательность рёбер, по которым можно пройти от одной вершины к другой, не повторяя рёбер. Цикл — это путь, который начинается и заканчивается в одной и той же вершине. Граф называют связным, если из любой его вершины можно добраться до любой другой по рёбрам графа.

Дерево — это особый вид графа: связный граф без циклов. У дерева с n вершинами всегда ровно n − 1 рёбер — на одно меньше, чем вершин. Деревья часто используют для изображения иерархий (родословные, файловая система) и для деревьев случайного эксперимента в теории вероятностей.

Правило

  1. Сумма степеней всех вершин графа равна удвоенному числу рёбер.
  2. Дерево с n вершинами имеет ровно n − 1 рёбер и не содержит циклов.

Разобранные примеры

Пример 1. В графе 5 вершин, и он является деревом. Сколько у него рёбер?

  1. У дерева рёбер на 1 меньше, чем вершин
  2. 5 − 1

Ответ: 4 ребра

Пример 2. Граф имеет 4 вершины со степенями 3, 2, 2, 1. Найдите число рёбер.

  1. Сумма степеней равна удвоенному числу рёбер
  2. 3 + 2 + 2 + 1 = 8
  3. Число рёбер: 8 ÷ 2

Ответ: 4 ребра

Пример 3. Есть ли цикл в связном графе с 6 вершинами и 5 рёбрами?

  1. У дерева с 6 вершинами было бы 6 − 1 = 5 рёбер — как раз наш случай
  2. Связный граф с n вершинами и n−1 рёбрами — это дерево, значит циклов нет

Ответ: нет, это дерево

Типичные ошибки

Число рёбер посчитали равным сумме степеней вершин

Каждое ребро добавляет по единице степени сразу двум вершинам, поэтому сумма степеней в 2 раза больше числа рёбер, а не равна ему.

Решили, что любой связный граф — это дерево

Деревом является только связный граф БЕЗ циклов. Связный граф с циклами (например, с рёбрами, образующими «треугольник») деревом не является.

Проверь себя

  1. 1. Дерево имеет 8 вершин. Сколько у него рёбер?

    Показать ответ

    7

  2. 2. Граф имеет вершины со степенями 1, 1, 2, 2, 2. Сколько у него рёбер?

    Показать ответ

    4

  3. 3. Связный граф имеет 7 вершин и 6 рёбер. Является ли он деревом?

    Показать ответ

    да