| Вид графа | Примеры |
|---|---|
|
Граф связный, если каждые две его вершины связные.
Граф полный,если каждые две его вершины соединены одним и только одним ребром Граф плоский (планарный),если его можно изобразить на плоскости так, что все пересечения его ребер являются вершинами графа |
G1(X,V) — полный, связный и планарный G2(X,V) — плоское изображение графа G1(X,V) |
|
Граф G называется деревом, если он является связным и не имеет циклов.
Граф G, все компоненты связности которого являются деревьями, называется лесом |
G3(X,V) — лес |
| Если элементы множества X упорядоченные пары, то граф называется ориентированным, или орграфом. Если х = (v1,v2) — дуга орграфа, то вершина v1 — начало, а вершина v2 — конец дуги х. Дуга х = (v1,v1) — петля.
Степень входа вершины орграфа — число входящих в вершину ребер, степень выхода — число выходящих из вершины ребер. Источником называется вершина, степень входа которой равна нулю, а степень выхода положительна. Стоком называется вершина, степень входа которой положительна, а степень выхода равна нулю. Путь в орграфе — последовательность ориентированных ребер. Цикл — замкнутый путь |
Вершина v2 -источник, вершина v4 — сток. Путь: v2→v3→v4 |
