Вероятность и статистика · урок 14

Решение задач с помощью графов

Используем графы для перебора вариантов и поиска маршрутов.

Объяснение темы

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

Примеры

Пример 1. В задаче о дорогах вершины — посёлки, рёбра — дороги.
Пример 2. В задаче о турнире вершины — игроки, рёбра — сыгранные партии.
Пример 3. Чтобы проверить возможность маршрута, ищут путь между нужными вершинами.

Проверка темы

Решите задания и отправьте ответы на проверку.

Чтобы платформа сохранила результат, войдите или зарегистрируйтесь.

Войти Зарегистрироваться