Занятия online

Графы: вершины, рёбра, степень вершины, путь, цикл

Графы: вершины и рёбра

1. Зачем учить эту тему

Кто с кем дружит в соцсети, какие города связаны дорогами, какие команды уже сыграли между собой — во всех этих задачах важны не расстояния и размеры, а только связи. Такие связи удобно рисовать точками и линиями. Этот рисунок называют графом, и с ним многие задачи решаются почти без вычислений.

2. Объяснение

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

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

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

Почему это так. У каждого ребра два конца. Когда мы считаем степени всех вершин, каждое ребро попадает в подсчёт дважды — один раз у каждого из своих концов.

Отсюда следствие: сумма степеней всегда чётная, поэтому вершин нечётной степени всегда чётное число.

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

Пример: 5 друзей — Аня (A), Борис (B), Вика (C), Гоша (D), Даша (E). Переписываются A и B, A и C, B и C, B и D, D и E.

вершинаABCDEсумма
степень2322110

Рёбер 5, сумма степеней 10 = 2 · 5.

Рисунок.

ABCDE

Подпись: «Степени вершин: A — 2, B — 3, C — 2, D — 2, E — 1; сумма 10 = 2 · 5».

3. Разберём примеры

Пример 1. По графу из объяснения найди степень B и проверь, можно ли от E дойти до C.

  1. Из B выходят рёбра B–A, B–C, B–D — степень 3.
  2. Путь: E → D → B → C. Все соседние вершины соединены рёбрами.

Ответ: степень B равна 3; от E до C дойти можно.

Пример 2. В классе 5 учеников. Может ли быть так, что каждый дружит ровно с тремя одноклассниками?

  1. Строим граф: ученики — вершины, дружба — рёбра. Каждая степень равна 3.
  2. Сумма степеней: 5 · 3 = 15 — нечётное число.
  3. Но сумма степеней всегда чётная (равна удвоенному числу рёбер).

Ответ: не может.

Пример 3 (обратный ход). В графе 4 вершины, и степень каждой равна 2. Сколько в нём рёбер? Нарисуй такой граф.

  1. Сумма степеней 4 · 2 = 8, значит, рёбер 8 : 2 = 4.
  2. Подходит «квадрат»: вершины по кругу, каждая соединена с двумя соседними.

Ответ: 4 ребра, граф — замкнутая цепочка из 4 вершин (цикл).

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

  1. ✗ «Рёбер столько же, сколько сумма степеней». Каждое ребро посчитано дважды. Правильно: рёбер = сумма степеней : 2.
  2. ✗ Место, где на рисунке пересеклись два ребра, считают вершиной. Вершины — только отмеченные точки. Правильно: пересечение линий — не вершина, если там нет точки.
  3. ✗ Вершину без рёбер забыли в таблице степеней. Она тоже вершина графа. Правильно: её степень 0, и её учитывают.

Задача из жизни, история темы и «Проверь себя» с ответами — в кабинете ученика. Там же урок можно послушать.

Уроки: Вероятность и статистика 7 класс

Графы: вершины и рёбра: правило и примеры — Вероятность и статистика 7 класс | Занятия.Online