Урок 16. Граф: вершины и рёбра

Вероятность и статистика, 7 класс · Введение в теорию графов · ~45 минут

🎯 Что ты узнаешь

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

📖 Разбираемся в теме

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

Вот ты и нарисовал граф.

📌 Запомни: Граф — это набор точек (их называют вершинами) и линий между некоторыми из них (их называют рёбрами). Ребро всегда соединяет ровно две вершины.

Слово «граф» тут вообще не про графики функций и не про дворянский титул. Это отдельное математическое понятие. Граф — это просто схема связей: что с чем соединено.

Рис. 1. Граф дружбы: А (Аня), Б (Боря), В (Витя), Г (Гена)

Посмотри: Аня (А) соединена с Борей (Б) и Витей (В), Боря — с Витей. А Гена (Г) стоит одиноко: к нему не ведёт ни одной линии. Так бывает — вершина может быть и без рёбер.

Где живут графы в реальной жизни

Графы повсюду, просто ты их не замечал:

Карта дорог. Города — вершины, дороги между ними — рёбра.
Друзья в соцсети. Люди — вершины, «дружба» — рёбра.
Схема метро. Станции — вершины, перегоны между ними — рёбра.
Турнирная таблица. Команды — вершины, сыгранные матчи — рёбра.

🤔 А знаешь ли ты? Первую задачу теории графов решил математик Леонард Эйлер в 1736 году. Жители города Кёнигсберга спорили: можно ли пройти по всем семи мостам города, ни по одному не пройдя дважды? Эйлер нарисовал граф — и доказал, что нельзя. С этого и началась целая наука.

Важно: как именно нарисовано — не важно

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

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

Петли и кратные рёбра (коротко)

Иногда встречаются два особых случая.

Петля — это ребро, которое выходит из вершины и в неё же возвращается. Например, в схеме «кто кому звонил» петля у вершины — это звонок самому себе (бывает в разных хитрых задачах).

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

Рис. 2. У вершины P — петля, а вершины P и Q соединены кратными (двойными) рёбрами

⚠️ Частая ошибка: Многие думают, что между двумя вершинами может быть только одна линия. Это не так — кратные рёбра вполне разрешены. А вот точку (вершину) рисовать дважды нельзя: каждый объект — это ровно одна вершина.

В большинстве школьных задач графы без петель и без кратных рёбер — их называют простыми. Но знать про петли и кратные рёбра полезно.

⏱ Попробуй сам: В классе четверо: Маша, Петя, Соня и Дима. Маша дружит с Петей и Соней. Петя — с Соней. Дима ни с кем. Сколько в этом графе вершин и сколько рёбер?

Как нарисовать граф по условию

Простой план из трёх шагов:

Выпиши все объекты (люди, города, станции) — это будут вершины. Поставь точки и подпиши буквами.
Прочитай, какие пары связаны, — проведи рёбра.
Проверь по условию каждую связь: ничего не забыл, ничего лишнего не добавил.

✍️ Разбор примеров

Пример 1. В графе 5 вершин: А, Б, В, Г, Д. Рёбра: А–Б, Б–В, В–Г, Г–Д, Д–А. Нарисуй граф. На что он похож?

Решение. Ставим 5 точек и соединяем по списку: А с Б, Б с В, В с Г, Г с Д, Д с А. Получается замкнутая фигура — каждая вершина соединена ровно с двумя соседями.

Рис. 3. Граф из примера 1 — пятиугольник

Ответ: Граф похож на пятиугольник (замкнутую «звезду» из пяти точек).

Пример 2. Запиши списком все рёбра графа с рисунка 1 (граф дружбы).

Решение. Смотрим на линии: А–Б, А–В, Б–В. К вершине Г линий нет.

Ответ: три ребра: А–Б, А–В, Б–В.

Пример 3. В компании четыре друга: Кир, Лёша, Маша, Ника. Каждый дружит с каждым. Сколько рёбер в графе дружбы?

Решение. Перечислим все пары: Кир–Лёша, Кир–Маша, Кир–Ника, Лёша–Маша, Лёша–Ника, Маша–Ника. Считаем — 6 пар.

Ответ: 6 рёбер.

Пример 4. Можно ли по графу понять, что объекты не связаны?

Решение. Да! Если между двумя вершинами нет ребра — значит, эти объекты не соединены. На рисунке 1 нет линии Г–А, и это говорит: Гена и Аня не дружат.

Ответ: Отсутствие ребра — это тоже информация: связи нет.

Пример 5. Три города: Орёл, Тула, Калуга. Из Орла в Тулу две разные дороги, из Тулы в Калугу — одна, из Орла в Калугу дорог нет. Нарисуй граф. Сколько в нём рёбер?

Решение. Орёл и Тулу соединяем двумя линиями (кратные рёбра!), Тулу и Калугу — одной. Орёл с Калугой не соединяем.

Рис. 4. Дороги: Орёл (Ор), Тула (Ту), Калуга (Ка)

Ответ: 3 ребра (два между Орлом и Тулой, одно между Тулой и Калугой).

💡 Запомни главное

Граф = вершины (точки) + рёбра (линии между ними).
Ребро соединяет ровно две вершины. Вершина может быть и вообще без рёбер.
Граф описывает связи: друзья, дороги, станции метро, матчи.
Как именно нарисован граф — не важно; важно только, что с чем соединено.
Петля — ребро из вершины в неё же. Кратные рёбра — несколько рёбер между одной парой вершин.

📝 Домашнее задание

Назови по три примера графов из жизни, где вершины — это: а) люди; б) места.
В графе вершины П, Р, С, Т. Рёбра: П–Р, Р–С, С–Т, Т–П. Нарисуй граф и скажи, на какую фигуру он похож.
Запиши списком все рёбра графа с рисунка 4.
Пять команд сыграли так: «Звёзды»–«Кометы», «Кометы»–«Луны», «Луны»–«Звёзды», «Орбита» ни с кем не играла. Нарисуй граф матчей. Сколько в нём вершин и рёбер?
В графе 4 вершины и каждая соединена с каждой. Нарисуй его и посчитай рёбра.
Объясни своими словами разницу между петлёй и кратными рёбрами. Нарисуй пример каждого.
Маша утверждает, что нарисовала два разных графа: на первом вершины стоят в ряд, на втором — по кругу, но связи одинаковые. Прав ли тот, кто говорит, что это один и тот же граф? Почему?
⭐ Шесть человек на встрече, и каждый пожал руку каждому ровно один раз. Нарисуй граф рукопожатий и сосчитай, сколько всего было рукопожатий. Подсказка: перечисляй пары аккуратно, чтобы не сосчитать одно рукопожатие дважды.