Графы: вершины, рёбра, степень вершины, путь, цикл
Графы: вершины и рёбра
1. Зачем учить эту тему
Кто с кем дружит в соцсети, какие города связаны дорогами, какие команды уже сыграли между собой — во всех этих задачах важны не расстояния и размеры, а только связи. Такие связи удобно рисовать точками и линиями. Этот рисунок называют графом, и с ним многие задачи решаются почти без вычислений.
2. Объяснение
Граф — набор точек, некоторые из которых соединены линиями. Точки называют вершинами, линии — рёбрами. Ребро соединяет две вершины. Как нарисованы линии — прямо или дугой, длинные или короткие — не важно: важно только, какие вершины соединены.
Степень вершины — число рёбер, которые из неё выходят. Вершина, из которой не выходит ни одного ребра, имеет степень 0.
Сумма степеней всех вершин равна удвоенному числу рёбер.
Почему это так. У каждого ребра два конца. Когда мы считаем степени всех вершин, каждое ребро попадает в подсчёт дважды — один раз у каждого из своих концов.
Отсюда следствие: сумма степеней всегда чётная, поэтому вершин нечётной степени всегда чётное число.
Путь — последовательность вершин, в которой каждые две соседние соединены ребром. Граф называют связным, если из любой его вершины можно по рёбрам дойти до любой другой.
Пример: 5 друзей — Аня (A), Борис (B), Вика (C), Гоша (D), Даша (E). Переписываются A и B, A и C, B и C, B и D, D и E.
| вершина | A | B | C | D | E | сумма |
|---|---|---|---|---|---|---|
| степень | 2 | 3 | 2 | 2 | 1 | 10 |
Рёбер 5, сумма степеней 10 = 2 · 5.
Рисунок.
Подпись: «Степени вершин: A — 2, B — 3, C — 2, D — 2, E — 1; сумма 10 = 2 · 5».
3. Разберём примеры
Пример 1. По графу из объяснения найди степень B и проверь, можно ли от E дойти до C.
- Из B выходят рёбра B–A, B–C, B–D — степень 3.
- Путь: E → D → B → C. Все соседние вершины соединены рёбрами.
Ответ: степень B равна 3; от E до C дойти можно.
Пример 2. В классе 5 учеников. Может ли быть так, что каждый дружит ровно с тремя одноклассниками?
- Строим граф: ученики — вершины, дружба — рёбра. Каждая степень равна 3.
- Сумма степеней: 5 · 3 = 15 — нечётное число.
- Но сумма степеней всегда чётная (равна удвоенному числу рёбер).
Ответ: не может.
Пример 3 (обратный ход). В графе 4 вершины, и степень каждой равна 2. Сколько в нём рёбер? Нарисуй такой граф.
- Сумма степеней 4 · 2 = 8, значит, рёбер 8 : 2 = 4.
- Подходит «квадрат»: вершины по кругу, каждая соединена с двумя соседними.
Ответ: 4 ребра, граф — замкнутая цепочка из 4 вершин (цикл).
4. Типичные ошибки
- ✗ «Рёбер столько же, сколько сумма степеней». Каждое ребро посчитано дважды. Правильно: рёбер = сумма степеней : 2.
- ✗ Место, где на рисунке пересеклись два ребра, считают вершиной. Вершины — только отмеченные точки. Правильно: пересечение линий — не вершина, если там нет точки.
- ✗ Вершину без рёбер забыли в таблице степеней. Она тоже вершина графа. Правильно: её степень 0, и её учитывают.
Задача из жизни, история темы и «Проверь себя» с ответами — в кабинете ученика. Там же урок можно послушать.
Уроки: Вероятность и статистика 7 класс
- Таблицы и диаграммы — Представление данных: таблицы и диаграммы
- Среднее арифметическое и медиана — Описательная статистика: среднее, медиана, наибольшее и наименьшее значения, размах
- Наибольшее и наименьшее значения. Размах — Описательная статистика: среднее, медиана, наибольшее и наименьшее значения, размах
- Случайные события. Частота и вероятность — Вероятность и частота случайного события
- Случайная изменчивость. Таблица частот и гистограмма — Случайная изменчивость