Основные виды графов и их примеры (Таблица)

Граф связный, если каждые две его вершины связные.

Граф полный,если каждые две его вершины соединены одним и только одним ребром

Граф плоский (планарный),если его можно изобразить на плоскости так, что все пересечения его ребер являются вершинами графа

G₁(X,V) - полный, связный и планарный

G₂(X,V) - плоское изображение графа G₁(X,V)

Граф G называется деревом, если он является связным и не имеет циклов.

Граф G, все компоненты связности которого являются деревьями, называется лесом

G₃(X,V) - лес

Если элементы множества X упорядоченные пары, то граф называется ориентированным, или орграфом. Если х = (v₁,v₂) - дуга орграфа, то вершина v₁ - начало, а вершина v₂ - конец дуги х. Дуга х = (v₁,v₁) - петля.

Степень входа вершины орграфа - число входящих в вершину ребер, степень выхода - число выходящих из вершины ребер.

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

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

Путь в орграфе - последовательность ориентированных ребер.

Цикл - замкнутый путь

Вершина v₂ -источник, вершина v₄ - сток.

Путь: v₂→v₃→v₄