Графы. Основные понятия

Графы. Основные понятия

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

по Жанна Темиргалиева

ЖТ

Вершины и ребра графа

1

Вершины

Вершины в графе представляют собой базовые элементы, которые могут быть объектами, событиями, людьми или любыми другими сущностями.

2

Ребра

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

Степень вершины

1

2

Входящая степень

Исходящая степень

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

Степень вершины также определяется количеством ребер, выходящих из данной вершины.

Связность графа

Связный граф

Несвязный граф

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

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

Виды графов

Ориентированные графы

Неориентированные графы

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

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

Взвешенные графы

Двудольные графы

Взвешенные графы имеют ребра, которым присвоены численные значения, отражающие важность или стоимость связи.

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

Деревья

1

Корень

Дерево имеет одну уникальную вершину, называемую корневой вершиной или корнем.

2

Листья

Вершины, не имеющие дочерних вершин, называются листьями.

3

Ветви

Ребра, соединяющие вершины, образуют ветви дерева.

Алгоритмы на графах

Обход в глубину

Алгоритм обхода в глубину (DFS) исследует граф, углубляясь по одному пути как можно дальше.

Поиск кратчайшего пути

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

Связность графа

Алгоритмы проверки связности графа определяют, существуют ли пути между всеми вершинами.

Применение графов

Социальные сети

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

Транспортные системы

Графы применяются для оптимизации маршрутов и расписаний

Компьютерные алгоритмы

Графы лежат в основе алгоритмов поиска, маршрутизации и планирования