Другие определения

Часто рассматриваются следующие родственные графам объекты.

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

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

3) Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мулътиграфом. На рис.2в приведена диаграмма мулътиграфа с четырьмя ребрами и тремя кратными ребрами.

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

5) Если задана функция и/или , то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.