Основные виды графов и их примеры (Таблица)
Вид графа |
Примеры |
Граф связный, если каждые две его вершины связные. Граф полный,если каждые две его вершины соединены одним и только одним ребром Граф плоский (планарный),если его можно изобразить на плоскости так, что все пересечения его ребер являются вершинами графа |
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 |