Смежность

Определение 9.3. Множество вершин, смежных с вершиной ν, называется множеством смежности вершины ν и обозначается Г⁺(ν): Г⁺(ν):={ u Î V | (u, v) Î E }, Г(ν):=Г.

Часто рассматриваются следующие родственные графам объекты: 1) Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е-дугами. 2) Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом). 3) Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом. 4) Если элементами множества Е являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом. 5) Если задана функция Р: V Þ М и/или Р: Е Þ М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.