Типы графов

1. Ориентированный граф (орграф) состоит из конечного непустого множества v вершин и заданного набора х упорядоченных пар различных ребер. Элементы из х={u,v} называется ориентированными ребрами или дугами.

	V		U

U

Рис.1 Рис.2

2. Направленный граф - это орграф, не имеющий симметрических дуг типа (u,v) и (v,u).

На рис.1 изображен направленный орграф, на рис.2 - ненаправленный орграф.

Ненаправленный орграф на рис.2 имеет 3 вершины и 4 ребра. Ребра все ориентированны, но имеются симметричные дуги (ребра) с противоположными направлениями. Поэтому это ненаправленный орграф.

3. Граф называется помеченным (перенумерованным), если все его вершины отмечены пометками. На рис.3 имеются вершины v1, v2, v3, которые отмечены.

V1

V3

Рис.3

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

В мультиграфе также не допускаются петли, но пара вершин может соединяться более, чем одним ребром. Такие ребра называются кратными. Мультиграф представлен на рис.4

Рис.4. а) Рис.4. б)

5. Если допускаются петли и кратные ребра, то это псевдограф.

Рис.5 а) Рис.5 б)