Графы: вершины и рёбра — Вероятность и статистика, 7 класс

Степень вершины, число рёбер, связность графа. 100 заданий на отработку.

Простыми словами

Схема метро, карта дорог между городами, список «кто с кем дружит» — всё это можно нарисовать точками и линиями. Точки — объекты, линии — связи между ними. Такой рисунок называют графом.

Граф — набор точек (вершин) и линий, соединяющих некоторые пары вершин (рёбер). Важно только, какие вершины соединены; длина и форма линий значения не имеют.

Степень вершины

Степень вершины — число рёбер, выходящих из неё. Вершина степени 0 — изолированная.

6 вершин, 7 рёбер; сумма степеней

2 + 3 + 3 + 2 + 3 + 1 = 14 = 2 \cdot 7

d_{1} + d_{2} + \dots + d_{n} = 2 m

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

Здесь $d_{1}, \dots, d_{n}$ — степени вершин, $m$ — число рёбер. Причина: каждое ребро имеет два конца и потому учтено в степенях двух вершин.

Следствия: сумма степеней всегда чётна; число вершин нечётной степени чётно.

Как считать вершины и рёбра

У графа 5 вершин, степень каждой равна 4. Сколько рёбер?

Сумма степеней: $5 \cdot 4 = 20$ .
Рёбер вдвое меньше: $m = 20 : 2 = 10$ .

Может ли быть граф со степенями вершин 3, 3, 2, 1?

Сумма: $3 + 3 + 2 + 1 = 9$ — нечётна.
А должна быть $2 m$ — чётной. Такого графа нет.

Считая рёбра по рисунку, отмечайте каждое посчитанное ребро галочкой — иначе легко посчитать одно дважды. Для проверки сложите степени и разделите на 2.

Пересечение двух линий на рисунке — ещё не вершина. Вершины обычно обозначены жирными точками.

Связность

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

Чтобы связать $n$ вершин, нужно не меньше $n - 1$ рёбер. Связный граф ровно с $n - 1$ ребром не имеет циклов — это дерево.

Нужно соединить дорогами 8 деревень так, чтобы из любой можно было доехать в любую. Наименьшее число дорог: $8 - 1 = 7$ .

Равенство «сумма степеней $= 2 m$ » называют леммой о рукопожатиях: если каждый гость сосчитает свои рукопожатия, в сумме получится удвоенное число рукопожатий.

Примеры заданий

Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.

Чему равна сумма степеней вершин графа с 6 рёбрами?

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

Ответ: 12
Решение. Каждое ребро добавляет по единице к двум вершинам.

В графе 6 рёбер. Сколько рёбер нужно убрать, чтобы осталось 4?

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

Ответ: 2
Решение. Простое вычитание.

Может ли сумма степеней вершин графа быть нечётной?

да
нет

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

Ответ: нет
Решение. Она всегда вдвое больше числа рёбер, то есть чётна.

Что называют степенью вершины?

количество циклов через неё
число выходящих из неё рёбер
число вершин рядом с ней
длину пути до соседней вершины

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

Ответ: число выходящих из неё рёбер
Решение. Петля при этом считается дважды.

Граф называют связным, если…

у него нет циклов
из любой вершины можно добраться до любой другой
число рёбер больше числа вершин
все степени вершин равны

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

Ответ: из любой вершины можно добраться до любой другой
Решение. Связность — про достижимость по рёбрам.

Сколько рёбер минимум нужно, чтобы связать 7 вершин?

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

Ответ: 6
Решение. Дерево на 7 вершинах имеет 6 ребро.

Верно ли, что в графе с 5 вершинами всегда ровно 5 рёбер?

да
нет

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

Ответ: нет
Решение. Число рёбер может быть любым: на рисунке их 5.

Ученик посчитал сумму степеней вершин и получил нечётное число. О чём это говорит?

граф несвязный
в подсчёте есть ошибка
всё верно
в графе есть петля

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

Ответ: в подсчёте есть ошибка
Решение. Сумма степеней всегда чётна.