Графы и их применение

Слайд 1. Графы и их применение

Основы теории графов, связность и моделирование задач. 10 класс

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

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

Графы используются для описания систем, где важны связи между объектами: от социальных сетей до схем авиаперелётов. В математике граф обозначается как $G=(V,E)$, где $V$ — вершины, а $E$ — рёбра.

Слайд 3. Основные элементы

Вершины — основные объекты системы.

Рёбра — связи между объектами.

Петля — ребро, которое начинается и заканчивается в одной вершине.

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

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

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

Сумма степеней всех вершин графа всегда равна удвоенному количеству его рёбер. Из этого следует, что в любом графе количество нечётных вершин чётно.

Слайд 5. Связный граф

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

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

Слайд 6. Визуализация связности

Слайд 7. Представление задач через графы

Логистика: города — вершины, дороги — рёбра. Поиск кратчайшего пути.

Социология: люди — вершины, знакомства — рёбра. Анализ «тесноты» мира.

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

Интернет: веб-страницы — вершины, гиперссылки — рёбра (ориентированный граф).

Слайд 8. Матрица смежности

Матрица смежности — это способ представления графа в виде таблицы.

Если между вершиной $i$ и вершиной $j$ есть ребро, в ячейке ставится $1$, если нет — $0$. Для неориентированного графа без петель матрица всегда симметрична относительно главной диагонали, а на самой диагонали стоят нули.

Слайд 9. Проверь себя

Существует ли граф с 5 вершинами, степени которых равны 1, 2, 2, 3, 3? Проверь по сумме степеней.

Может ли дерево (связный граф без циклов) быть несвязным по определению?

Какое минимальное количество рёбер нужно, чтобы сделать граф из 4 вершин связным?

Слайд 10. Итоги

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

Связность — ключевое свойство, определяющее целостность системы.

Любую задачу о связях можно переложить на язык вершин и рёбер.

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