Графы и их свойства

Слайд 1. Графы и их свойства

Вероятность и статистика, 10 класс

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

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

Обозначение: $G=(V,E)$, где $V$ — вершины, $E$ — рёбра.

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

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

Сумма степеней всех вершин любого графа равна удвоенному количеству его рёбер: ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$. Отсюда следует, что в любом графе чётное число нечётных вершин.

Слайд 4. Пути, цепи и циклы

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

Цепь — путь, в котором все рёбра различны.

Простая цепь — путь, в котором все вершины (и, следовательно, рёбра) различны.

Цикл — замкнутая цепь (начальная и конечная вершины совпадают).

Простой цикл — цикл, в котором все вершины, кроме начальной и конечной, различны.

Слайд 5. Связность и деревья

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

Связный граф, не содержащий циклов. В дереве с $n$ вершинами всегда ровно $n-1$ ребро.

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

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

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

Каждое ребро соответствует элементарному событию.

Путь от корня до «листа» представляет собой один из полных исходов опыта.

Произведение вероятностей вдоль пути дает вероятность конкретного исхода.

Слайд 7. Планарные графы

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

Такое изображение графа называется плоским графом. Плоский граф делит плоскость на области, называемые гранями.

Слайд 8. Теорема Эйлера

Для любого связного плоского графа выполняется равенство:

$V-E+F=2$

Здесь $F$ включает в себя внешнюю (неограниченную) грань. Это фундаментальное свойство связывает топологию и комбинаторику.

Слайд 9. Применение графов

Поиск кратчайшего пути между городами (алгоритм Дейкстры).

Анализ связей между веб-страницами для ранжирования в поиске.

Моделирование социальных связей и распространения информации.

Описание структуры молекул, где атомы — вершины, а связи — рёбра.

Слайд 10. Подведем итоги

Граф — это мощный инструмент для моделирования связей между объектами.

Основные характеристики: вершины, рёбра и их степени.

Специальные виды: связные графы, деревья и планарные графы.

Формула Эйлера $V-E+F=2$ — ключ к пониманию плоских структур.

Графы окружают нас повсюду: от карт навигатора до нейронных сетей.