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

0
6
Математика таблица
Вид графа Примеры
Граф связный, если каждые две его вершины связные.

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

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

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

ОСТАВЬТЕ ОТВЕТ

Please enter your comment!
Please enter your name here