Виды графов

Пустой граф — граф, в котором есть только вершины (нет рёбер и дуг).

Неориентированный граф (не орграф) — граф, содержащий только рёбра.

Ориентированный граф (орграф) — граф, содержащий только дуги.

Смешанный граф — граф, содержащий рёбра и дуги.

Ориентированный и неориентированный графы являются частными случаями смешанного.

Гамильтонов граф — граф, в котором есть гамильтонов цикл. (Далее подробнее.)

Полугамильтонов граф — граф, в котором есть гамильтонов маршрут (Далее подробнее.)

Эйлеров граф — граф, в котором существует цикл без повторения рёбер (такой цикл называют эйлеровым), обходящий все вершины графа. (Далее подробнее.)

Полуэйлеров граф — граф, в котором существует маршрут (эйлеров путь), обходящий все рёбра графа ровно один раз. (Далее подробнее.)

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

Рисунок 4. а) — эйлеров граф, б) — полуэйлеров граф, в) — граф, не являющийся ни эйлеровым, ни полуэйлеровым.

Связный граф — граф, в котором для любых двух вершин есть путь из в .

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

Ациклический граф — граф без циклов.

Нормированный граф — ориентированный граф без циклов.

Простой граф — граф без петель и кратных рёбер (дуг).

Мультиграф — граф с кратными рёбрами и без петель.

Псевдограф — мультиграф с хотя бы одной петлёй.

Полный граф — граф, в котором любые две вершины соединены одним ребром.

Турнир — ориентированный граф, в котором каждая пара вершин соединена одной дугой.

Рисунок 5. Турнир

Направленный граф — ориентированный граф, в котором две вершины соединяются не более чем одной дугой.

Дерево — связный граф без циклов.

Лес — множество деревьев.

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

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

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

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

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

-регулярный граф — граф, в котором степени всех вершин равны .

ВНИМАНИЕ! К сожалению, некоторые из этих терминов не вполне устоялись, так как нет чётких стандартов. В большинстве случаев терминология определяется во вводной части большинства книг по теории графов.

Например, некоторые авторы разрешают мультиграфам иметь петли, а некоторые не разрешают; определения пути и маршрута разнятся…