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

Вид графа

Примеры

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

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

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

mat 12 41

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

mat 12 42

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

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

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

mat 12 43

G3(X,V) - лес

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

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

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

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

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

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

mat 12 44

Вершина v2 -источник, вершина v4 - сток.

Путь: v2→v3→v4



1 1 1 1 1 1 1 1 1 1 Рейтинг 5.00 [2 Голоса (ов)]

Поделитесь ссылкой с друзьями:


Подписываемся !!!

Комментарии:

comments powered by HyperComments

библиотеки Яндекс.Метрика