Представление об ориентированных графах

Слайд 1. Представление об ориентированных графах

Урок вероятности и статистики • 7 класс

От простых связей к сложным маршрутам: учимся моделировать направленные процессы на практике

Слайд 2. Почему направление имеет значение?

В жизни часто встречаются связи, которые работают только в одну сторону.

• Одностороннее движение: вы можете доехать от перекрестка $A$ до $B$, но путь обратно по той же полосе запрещен.

• Авиаперелеты: наличие рейса «город $A$ — город $B$» не означает автоматического существования обратного рейса в то же время.

В обычном графе ребро — это просто связь. В ориентированном графе связь превращается в дугу (стрелку). Здесь порядок вершин $(A,B)$ критически важен: это направление «откуда — куда». Если есть дуга из $A$ в $B$, то проезд в обратную сторону не предусмотрен, пока мы не нарисуем вторую стрелку.

Слайд 3. Из чего состоит граф? Основные термины

Вершина — это «узел» или объект системы: город на карте, страница в интернете или человек в социальной сети.

Дуга — направленная связь между объектами. На схеме всегда рисуется в виде стрелки, указывающей путь от одного объекта к другому.

Исток — вершина-отправитель: из неё выходят стрелки, но ни одна не входит (начальная точка пути).

Сток — вершина-приёмник: в неё входят стрелки, но ни одна не выходит (конечная точка пути).

Слайд 4. Проблема: Городская навигация

Представьте центр мегаполиса: вы доставили заказ из точки $A$ в точку $B$, проехав по улице с односторонним движением. Теперь вам нужно вернуться обратно, но прямой путь закрыт знаком «Кирпич». Вам приходится делать крюк через несколько кварталов, потому что движение разрешено только в одном направлении.

Обычная карта с линиями-дорогами здесь не поможет, ведь пути неравноценны. Чтобы не заблудиться и найти кратчайший путь, мы будем использовать ориентированные графы (орграфы). В них дороги — это не просто линии, а стрелки, указывающие, куда можно ехать, а куда — нет.

Слайд 5. Практикум: Визуализация иерархий

Переведите описание лесной экосистемы в модель пищевой цепочки. Помните: в орграфе стрелка направлена от того, кого едят, к тому, кто ест (поток энергии: Трава $\to$ Заяц $\to$ Лиса).

Постройте структуру школьного самоуправления. Определите уровни власти и направления команд от «источников» к «исполнителям»: Директор $\to$ Завуч $\to$ Учитель $\to$ Ученик.

Используйте онлайн-редакторы диаграмм для финализации схем. Цифровой инструмент позволяет легко перемещать узлы, чтобы избежать пересечения стрелок и сделать граф читаемым.

Слайд 6. Пути и достижимость в графах

Это «маршрут» по стрелкам от одной вершины к другой. Путь — это последовательность дуг, где конец предыдущей совпадает с началом следующей. Длина пути в обычном графе — это количество «шагов» (дуг) в нём.

Вершина $B$ достижима из $A$, если между ними можно проложить хотя бы один маршрут, не нарушая направления стрелок. В ориентированных графах это работает только в одну сторону: из $A$ в $B$ попасть можно, а обратно — не всегда.

Чтобы найти самый выгодный маршрут в сети, нужно сравнить суммы весов (длину, время или стоимость) всех возможных путей. Например, путь $A\to B\to C$ со стоимостью $2+3=5$ лучше, чем прямой путь $A\to C$ со стоимостью $7$.

Слайд 7. Матрица смежности орграфа: как это работает?

Каждая строка таблицы соответствует вершине, из которой выходит стрелка. Читая строку $A$ слева направо, мы видим все пути, начинающиеся в точке $A$.

Каждый столбец соответствует вершине, в которую стрелка входит. Смотря на столбец $B$ сверху вниз, мы узнаем, из каких точек можно попасть в $B$.

Ставим $1$ только на пересечении строки-старта и столбца-финиша. Если стрелки $A\to B$ нет или она направлена в обратную сторону, записываем в ячейку $0$.

Слайд 8. Практика: Построение и анализ орграфа

Задание 1: Постройте орграф по матрице смежности $A=\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 0\end{array}\right)$.

Задание 2: Определите достижимость — выпишите все вершины, в которые можно попасть из вершины №1.

Задание 3: Найдите в получившемся графе циклы (пути, возвращающиеся в ту же точку).

Контроль: Сверьте количество рёбер и направления стрелок с эталоном, который появится на доске.

Слайд 9. Практическое применение ориентированных графов

Транспорт

Интернет

Соцсети

Спорт

Навигаторы строят маршруты, учитывая улицы с односторонним движением и запрещенные повороты — это типичные дуги орграфа.

Всемирная паутина состоит из страниц и ссылок. Переход по ссылке возможен только в одну сторону, что создает гигантский цифровой орграф.

В большинстве соцсетей подписка работает как дуга: вы подписаны на кумира, но он не обязательно подписан на вас в ответ.

В турнирных таблицах стрелка от игрока $A$ к игроку $B$ наглядно фиксирует факт победы в личной встрече или переход в следующий тур.

Слайд 10. Итоги урока и домашнее задание

Сегодня мы узнали, что стрелки в графах (дуги) определяют порядок и направление отношений.

Мы научились превращать сухие таблицы и описания в наглядные и понятные схемы.

ДЗ №1: Постройте ориентированный граф вашего пути в школу, отметив ключевые точки как вершины.

ДЗ №2: Выберите 4 команды из любой спортивной таблицы и изобразите их встречи в виде графа «кто кого победил».

Спасибо за внимание! Вы отлично справились с основами теории графов $G=(V,A)$.