Графы и деревья случайных экспериментов

Слайд 1. Графы и деревья случайных экспериментов

Теория графов и её применение в вероятности. 10 класс

Слайд 2. Что такое граф?

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

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

Слайд 3. Степень (валентность) вершины

Степенью (или валентностью) вершины $v$ называется количество рёбер, которые ей инцидентны (выходят из неё). Обозначается как $\mathrm{deg}(v)$.

Если вершина соединена сама с собой (петля), то петля добавляет к её степени сразу 2, так как ребро выходит и входит в одну и ту же точку.

Слайд 4. Лемма о рукопожатиях

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

$$\sum _{v\in V}\mathrm{deg}(v)=2|E|$$

Из этой леммы следует важное свойство: в любом графе количество вершин с нечётной степенью всегда чётно. Невозможно нарисовать граф, в котором, например, ровно три вершины имеют степень 3, а остальные — чётную.

Слайд 5. Классификация вершин по их степени

Вершина со степенью $0$. К ней не ведёт ни одно ребро, она стоит отдельно.

Вершина со степенью $1$. Из неё выходит ровно одно ребро, ведущее в граф.

Вершина, степень которой является чётным числом ($2,4,6,\dots$).

Вершина, степень которой является нечётным числом ($1,3,5,\dots$).

Слайд 6. Путь в графе

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

Длина пути равна количеству рёбер в нём. Если начальная и конечная вершины пути совпадают, такой маршрут называется замкнутым.

Слайд 7. Цепи и циклы

Маршрут, в котором все рёбра различны. Если при этом все вершины также различны, цепь называется простой. Простая цепь соединяет две разные точки графа без самопересечений.

Замкнутая цепь, в которой начальная и конечная вершины совпадают. Простой цикл не проходит через одну и ту же вершину дважды (за исключением первой и последней).

Слайд 8. Связность графа

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

Если граф несвязный, он распадается на отдельные изолированные части — компоненты связности.

Внутри одной компоненты все вершины связаны путями, но между разными компонентами рёбер нет.

Дерево — это пример связного графа, в котором нет ни одного цикла.

Слайд 9. Графы на плоскости (планарные графы)

Граф называется планарным (плоским), если его можно изобразить на плоскости так, чтобы его рёбра пересекались только в вершинах.

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

Слайд 10. Формула Эйлера для плоских графов

Для любого связного плоского графа справедливо соотношение между числом вершин ($V$), рёбер ($E$) и граней ($F$, включая внешнюю бесконечную область):

$$V-E+F=2$$

Эта формула накладывает жёсткие ограничения на структуру плоских графов. Из неё математически доказывается, что в плоском графе без петель и кратных рёбер количество рёбер не может превышать удвоенное число вершин минус 6: $E\le 3V-6$.

Слайд 11. Классические непланарные графы

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

Известен как задача «о трёх домах и трёх колодцах». Попытка соединить каждый из 3 домов с каждым из 3 колодцев так, чтобы тропинки не пересекались на плоскости, не имеет решения.

Слайд 12. Дерево случайного эксперимента

Слайд 13. Что такое дерево эксперимента?

Дерево случайного эксперимента — это направленный связный граф без циклов, который наглядно моделирует многоэтапные случайные процессы.

Каждое разветвление (узел) соответствует моменту выбора или наступлению очередного этапа.

Ветви, выходящие из узла, обозначают возможные исходы этого этапа.

Листья дерева (конечные вершины) представляют собой элементарные исходы всего эксперимента.

Слайд 14. Правила работы с деревом

Каждому ребру (ветви) приписывается вероятность соответствующего исхода на данном этапе.

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

Вероятность конкретного сложного исхода (пути от корня к листу) равна произведению вероятностей на всех рёбрах этого пути.

Если событию удовлетворяют несколько листьев, их вероятности складываются.

Слайд 15. Пример: Два броска монеты

При бросании симметричной монеты дважды дерево имеет 4 финальные ветви:

1. Орёл $\to$ Орёл ($P=0.5\cdot 0.5=0.25$)

2. Орёл $\to$ Решка ($P=0.25$)

3. Решка $\to$ Орёл ($P=0.25$)

4. Решка $\to$ Решка ($P=0.25$)

Сумма всех исходов: $0.25+0.25+0.25+0.25=1$. Дерево помогает не потерять ни один вариант.

Слайд 16. Зависимые испытания: Выбор без возвращения

Пусть в урне 3 белых и 2 чёрных шара. Вероятность достать белый шар на первом шаге равна $\frac{3}{5}$, а чёрный — $\frac{2}{5}$.

Если первым достали белый, в урне осталось 2 белых и 2 чёрных шара. Вероятность снова вытянуть белый меняется и становится $\frac{2}{4}=\frac{1}{2}$. Дерево наглядно учитывает изменение условных вероятностей на каждом уровне.

Слайд 17. Алгоритм расчёта вероятностей

Последовательно нарисуйте дерево всех возможных исходов эксперимента от старта до финала.

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

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

Слайд 18. Задание для самопроверки

В кармане лежат 2 ключа от квартиры и 3 ключа от офиса. Студент наугад достаёт один ключ, кладёт его на стол, а затем достаёт второй.

Постройте дерево этого случайного эксперимента в тетради. Напишите вероятности на каждом ребре.

Найдите вероятность того, что оба вынутых ключа окажутся от офиса.

*Подсказка: обратите внимание, что количество ключей в кармане уменьшается на втором шаге.*

Слайд 19. Итоги занятия

Степень вершины — это количество рёбер, выходящих из неё. Сумма степеней всех вершин равна $2E$.

Путь — это последовательность соединённых рёбер. В цепи рёбра не повторяются, а цикл — это замкнутая цепь.

Планарные графы можно уложить на плоскости без пересечений рёбер. Для них выполняется формула Эйлера: $V-E+F=2$.

Дерево эксперимента — это инструмент для вычисления вероятностей последовательных событий путём умножения вдоль ветвей.

Слайд 20. Спасибо за внимание! Успехов в изучении теории графов и вероятностей!