Решение задач с помощью графов
Как применить графы к реальным задачам: транспорт, социальные сети, расписания и планирование маршрутов.
Решение задач с помощью графов
Определение. Моделирование с помощью графа
Моделирование с помощью графа — представление реальной ситуации в виде графа: объекты становятся вершинами, а связи между ними — рёбрами. После такого представления задачу можно решать, изучая свойства графа: связность, степени вершин, наличие путей и циклов.
Транспортная сеть
Транспортную сеть удобно изображать графом: города — вершины, дороги — рёбра. По такому графу можно находить маршруты, проверять, все ли города связаны, и планировать перевозки.
Социальная сеть
Социальную сеть тоже изображают графом: люди — вершины, дружеские связи — рёбра. Степень вершины показывает число друзей, а связность — можно ли через цепочку знакомств добраться от одного человека до другого.
Расписания и планирование
Графы помогают решать задачи о расписаниях. Например, если два предмета нельзя проводить одновременно (один учитель), между их вершинами рисуют ребро. Тогда задача сводится к раскраске графа — распределению вершин по дням так, чтобы соединённые ребром вершины попали в разные дни.
Пример 1. Маршрут между городами
Дана транспортная сеть: города A, B, C, D и дороги A–B, B–C, C–D. Найти маршрут из A в D.
Дано: дороги: A–B, B–C, C–D.
Анализ: города — вершины, дороги — рёбра. Ищем путь из A в D.
Подстановка: из A в B (A–B), затем в C (B–C), затем в D (C–D).
Ответ: маршрут из A в D: A–B–C–D.
Пример 2. Число друзей в соцсети
В социальной сети Аня дружит с Борей и Витей, Боря — с Аней и Димой, Витя — с Аней, Дима — с Борей. Сколько друзей у Ани?
Дано: связи: Аня–Боря, Аня–Витя, Боря–Дима.
Формула: число друзей человека — степень его вершины.
Подстановка: из вершины Аня выходят два ребра (к Боре и Вите). .
Ответ: у Ани 2 друга.
Пример 3. Проверка связности сети
Дана сеть дорог: A–B, B–C и изолированный город D. Можно ли из A добраться до D?
Дано: дороги: A–B, B–C; город D изолирован.
Анализ: из A можно добраться до B и C, но до D дороги нет.
Ответ: из A до D добраться нельзя — сеть несвязная, город D отрезан.
Важно!
⚠️ Типичная ошибка — рисовать граф, но не проверять, что он правильно отражает условие. Прежде чем решать задачу, убедись: каждая ли связь из условия стала ребром, каждый ли объект — вершиной. Ошибка в построении графа ведёт к неверному ответу, даже если дальше всё посчитано верно.
Примеры вопросов из тренажёра
-
Q: Как перевести задачу о городах и дорогах на язык графа?
A: верный ответ — Города — вершины, дороги — рёбра
Объяснение: В транспортной задаче города становятся вершинами, а дороги между ними — рёбрами. Дальше задачу решают, изучая граф.
-
Q: В социальной сети Аня дружит с Борей и Витей. Сколько друзей у Ани?
A: верный ответ — 2
Объяснение: Число друзей человека — степень его вершины. Из вершины Аня выходят два ребра (к Боре и Вите), значит, у Ани 2 друга.
-
Q: Дана сеть дорог: A–B, B–C и изолированный город D. Можно ли из A добраться до D?
A: верный ответ — Нет, до D нет дороги
Объяснение: Город D изолирован — из него не выходит ни одной дороги. Поэтому из A до D добраться нельзя, сеть несвязная.
-
Q: Дана сеть дорог: A–B, B–C, C–D. Какой маршрут ведёт из A в D?
A: верный ответ — A–B–C–D
Объяснение: Из A идём в B (A–B), затем в C (B–C), затем в D (C–D). Маршрут A–B–C–D связывает A и D.
-
Q: Что показывает степень вершины в графе социальной сети?
A: верный ответ — Число друзей человека
Объяснение: В графе соцсети степень вершины равна числу рёбер, выходящих из неё, то есть числу друзей этого человека.