Основные виды графов в математике и информатике
Виды графов в математике и информатике классифицируют структуры из вершин и рёбер, моделирующие парные отношения. Они делятся по направленности, связности, полноте и весам, являясь основой алгоритмов.
Оглавление
Направленность и структура рёбер
Графы разделяются по наличию направления у рёбер и допустимости специфических элементов:
- Неориентированные графы: рёбра не имеют определённого направления, движение по ним возможно в обе стороны.
- Ориентированные графы (орграфы): каждому ребру (дуге) присвоено строгое направление, отражающее направленность связей между объектами.
- Смешанные графы: содержат одновременно как ориентированные, так и неориентированные рёбра.
- Простой (обыкновенный) граф: не содержит ни петель, ни кратных рёбер. Между любыми двумя вершинами может быть проведено не более одного ребра.
- Мультиграф: граф, в котором между двумя вершинами допускается наличие нескольких (кратных) рёбер, но при этом отсутствуют петли.
- Псевдограф: граф, который допускает наличие петель (рёбер, начинающихся и заканчивающихся в одной и той же вершине).
Связность и полнота графа
Классификация по возможности перемещения между вершинами и степени заполненности связей:
- Связный граф: из любой вершины графа существует путь в любую другую его вершину.
- Дерево: особый вид связного графа, в котором полностью отсутствуют циклы.
- Сеть: граф, в котором присутствует цикл (термин, часто используемый в школьной информатике).
- Полный граф: граф, в котором каждая пара различных вершин соединена ребром.
- Неполный граф: граф, в котором построены не все возможные рёбра между вершинами.
- Пустой граф: теоретическая модель графа, в котором полностью отсутствуют рёбра.
Весовые и специализированные виды графов
Некоторые графы наделяются дополнительными свойствами для решения конкретных задач:
- Взвешенный граф: рёбрам (или самим вершинам) присвоены числовые значения — веса, которые могут обозначать расстояние, стоимость или пропускную способность.
- Планарный граф: граф, который можно изобразить на плоскости так, чтобы его рёбра не пересекались друг с другом.
- Двудольный граф: вершины графа можно разбить на два непересекающихся множества так, что рёбра соединяют вершины только из разных множеств.
- Регулярный (однородный) граф: граф, у которого все вершины имеют одинаковую степень (одинаковое количество инцидентных рёбер).
- Гетерогенный граф: граф, содержащий разнотипные вершины или связи, часто применяемый в задачах машинного обучения.
- Изоморфные графы: графы, имеющие абсолютно одинаковую структуру связей, но отличающиеся лишь обозначениями вершин или внешним видом.
| Признак классификации | Вид графа | Ключевая особенность |
|---|---|---|
| Направленность | Ориентированный / Неориентированный | Наличие или отсутствие строгого направления у дуг |
| Структура рёбер | Мультиграф / Псевдограф | Допуск кратных рёбер или петель соответственно |
| Связность | Дерево / Сеть | Отсутствие циклов / Наличие циклов |
| Полнота | Полный / Пустой | Все возможные рёбра присутствуют / Рёбра отсутствуют полностью |
| Дополнительные свойства | Взвешенный / Планарный | Наличие числовых весов / Возможность изображения без пересечений |
Применение графов
- В информатике: графы лежат в основе баз данных, нейросетей, алгоритмов поиска кратчайшего пути и построения компьютерных сетей.
- В математике: они являются предметом изучения отдельного большого раздела дискретной математики — теории графов.
FAQ
Чем отличается мультиграф от псевдографа?
Мультиграф допускает наличие нескольких (кратных) рёбер между двумя вершинами, но не имеет петель. Псевдограф допускает наличие петель (рёбер, начинающихся и заканчивающихся в одной вершине).
Что такое изоморфные графы?
Это графы, имеющие абсолютно одинаковую структуру связей, но отличающиеся лишь обозначениями вершин или внешним видом при изображении.
Может ли дерево быть несвязным графом?
Нет. Дерево по определению является особым видом связного графа, в котором полностью отсутствуют циклы.