Основные определения теории графов

Графическое изображение графа.

Смежность.

Пусть v₁, v₂ — вершины, е = (v₁, v₂) — соединяющее их ребро. Тогда вершина v₁ и ребро е инцидентны, вершина v₂ и ребро е также инцидентны.

Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается :

Обычно граф изображают диаграммой: вершины — точками (или кружками), ребра — линиями.

Пример.

На рис. 3 приведен пример диаграммы графа, имеющего четыре вершины и пять ребер. В этом графе вершины v₁ и v₂, v₂ и v₃, v₃ и v₄, v₄ и v₁, v₂ и v₄ смежны, а вершины v₁ и v₃ не смежны. Смежные ребра: е₁ и е₂, е₂ и е₃, е₃ и е₄, е₄ и е₁, е₁ и е₅, е₂ и е₅, е₃ и е₅, е₄ и е₅. Несмежные ребра е₁ и е₃, е₂ и е₄.

Рис. 3. Диаграмма графа

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

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

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

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

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

Дата добавления: 2015-05-26