Магия графов

Слайд 1. Магия графов: от загадок до соцсетей

Вероятность и статистика, 7 класс. Погружение в теорию графов через игру и практику.

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

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

Основные элементы:

1. Вершины — это объекты (точки).

2. Ребра — это связи между ними (линии).

Граф помогает визуализировать сложные связи в одно касание!

Слайд 3. Словарь юного тополога

Вершина — точка, объект ($A,B,C$).
Ребро — линия, соединяющая две вершины.
Степень — сколько линий выходит из точки.
Петля — ребро, ведущее в ту же точку.
Кратные ребра — несколько связей между парой точек.

Слайд 4

Слайд 5. Где мы встречаем графы?

Схема метрополитена (станции — вершины, перегоны — ребра).

Социальные сети (люди — вершины, дружба — ребра).

Молекулы веществ (атомы и связи).

Интернет (серверы и кабели передачи данных).

Слайд 6. Задача о рукопожатиях

В комнате 5 человек. Каждый пожал руку каждому. Сколько всего было сделано рукопожатий?

Рисуем 5 вершин. Из каждой выходит 4 ребра. По формуле сумма степеней вершин в 2 раза больше числа ребер: $E=\frac{5\cdot 4}{2}=10$.

Слайд 7

Слайд 8. Связность: можно ли пройти везде?

Слайд 9. Типы связности

Между любыми двумя вершинами существует путь. Нет 'изолированных' островов.

Распадается на отдельные части — компоненты связности.

Особый вид связного графа, в котором нет циклов (замкнутых путей).

Слайд 10. История одной прогулки: Семь мостов Кёнигсберга

1736 год

Леонард Эйлер

Рождение теории

Жители города пытались обойти все 7 мостов, не проходя по одному дважды.

Великий математик доказал, что это невозможно, превратив карту в граф.

Это решение стало фундаментом современной теории графов.

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

— Леонард Эйлер, основоположник теории графов

Слайд 12. Правила Эйлерова пути

Граф должен быть связным (один кусок).

Все вершины имеют четную степень — можно вернуться в начало.

Ровно 2 вершины нечетные — путь начнется в одной, закончится в другой.

Если нечетных вершин > 2, 'эйлерова пути' не существует.

Слайд 13

Слайд 14. Ориентированные графы (Орграфы)

В ориентированных графах порядок вершин в ребре $(A,B)$ имеет значение. Путь возможен только по направлению стрелки.

Слайд 15. Где чаще всего используют графы сегодня?

Алгоритмы на графах лежат в основе поиска кратчайшего пути в навигаторах и ранжирования страниц в интернете.

Слайд 16. Интерактив: Проверь себя!

Вопрос: Можно ли нарисовать конверт (домик), не отрывая руки?

Подсказка: Посчитай степени вершин! Если нечетных вершин 0 или 2 — ответ 'Да'.

Слайд 17. Главные выводы урока

Граф состоит из вершин (точек) и ребер (линий).

Степень вершины — это количество выходящих из нее ребер.

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

Эйлеров путь существует только при 0 или 2 нечетных вершинах.

Ориентированные графы используют стрелки для указания направления.

Слайд 18

Слайд 19. Спасибо за внимание! Готовы строить свои связи?

Слайд 20

Слайд 21

Слайд 22

Слайд 23