Графы: определение, типы, пути и представление

Определение графа

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

• Вершины (или узлы) графа обозначаются как точки, представляющие объекты.
• Рёбра (или дуги) соединяют вершины и представляют связи между ними.

Типы графов

Графы классифицируются по типу рёбер и наличию весов:

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

• Ориентированный граф (орграф): рёбра имеют направление. Каждое ребро соединяет пару вершин, но в определённом направлении. Обозначается как (u → v), где u и v — вершины.
• Неориентированный граф: рёбра не имеют направления. Ребро обозначается как {u, v}, где u и v — соединённые вершины. Связь между вершинами симметрична.

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

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

• В неориентированном взвешенном графе вес ассоциируется с обоими направлениями.
• В ориентированном взвешенном графе вес указывается для конкретного направления рёбер.

Понятие пути в графе

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

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

Длина пути

Длина пути — это количество рёбер на пути между начальной и конечной вершинами. В случае взвешенного графа длина пути может быть определена как сумма весов рёбер, через которые проходит путь.

Способы представления графов

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

• Матрица смежности: квадратная матрица, где элемент matrix[i][j] указывает наличие или вес ребра между вершинами i и j. Применяется для плотных графов.
• Список смежности: для каждой вершины хранится список её соседей (вершин, с которыми она соединена рёбрами). Подходит для разреженных графов, экономит память.
• Список рёбер: хранится список всех рёбер в виде пар вершин или троек (в случае взвешенных графов). Удобен для работы с графами, где требуется рассматривать отдельные рёбра.

Заключение

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