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

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

Глава 2. Алгоритмы на графах

Во многих прикладных задачах возникает необходимость наглядного представления отношений между объектами. Графы являются моделью таких отношений.

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

Определение 1. Неориентированным графом называется совокупность непустого множества – множества вершин и множества - множества ребер, т.е.неупорядоченных пар различных элементов множества .

Число вершин графа обозначается .

Число ребер графа обозначается .

Если - вершины , т. е. и – соединяющее их ребро, то есть , тогда вершина и ребро называются инцидентными. Два ребра, инцидентных одной вершине, называются смежными ребрами. Две вершины, инцидентные одному ребру, называются смежными вершинами.

Количество ребер, инцидентных вершине , называется степенью (валентностью) вершины и обозначается .

Определение 2.Ориентированным графом (орграфом) называется совокупность непустого множества – множества узлов и множества E – множества дуг, т.е. упорядоченных пар различных элементов множества .

В орграфе число дуг, исходящих из вершины v называется полустепенью исхода и обозначается . Число дуг, входящих в v – полустепенью захода и обозначается .

Граф наглядно изображают диаграммой: вершины – точками, ребро – отрезком . Для орграфа узлы изображают точками, дуга - стрелкой от к .

Рис 1. а) граф , б) орграф

Определение 3. Псевдографом (псевдоорграфом) называется совокупность непустого множества и множества неупорядоченных (упорядоченных) пар элементов из необязательно различных.

Ребро (дуга )псевдографа (псевдоорграфа) назывется петлей.

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

Рис 2. а) псевдограф, – петля, б) мультиграф, - кратное ребро.

Рис 3. Помеченный орграф. Функция , ,

Далее, по умолчанию, термин «граф », означает неориентированный непомеченный граф без петель и кратных ребер.

Определение 6. Граф (орграф) называется подграфом графа (орграфа) и обозначается и , то может быть получен из графа удалением некоторых ребер, множества же вершин