Виды графов и операции над ними

Если элементами множества Е являются упорядоченные пары, то граф назы­вается ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.

Если бинарное отношение E является симметричным, то граф называется неориентированным (или неорграфом). В этом случае симметричные пары (a, b) и (b, a) обозначаются [ a, b ].

Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).

Граф, содержащий как ориентированные, так и неориентированные рёбра, называется смешанным.

Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф назы­вается мультиграфом.

Если элементами множества Е являются не обязательно двухэлементные, а
любые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом.

Если задана функция F: V→М и/или F: Е→М, то множество М называется множеством пометок, а граф называется помеченным.