Спецификация

Граф G – это упорядоченная пара (V, E), где V – непустое множество вершин, E – множество пар элементов множества V, называемое множеством ребер.

Упорядоченная пара элементов из V называется дугой. Если все пары в Е упорядочены, то граф называется ориентированным (орграфом).

Если дуга e ведет от вершины v₁ к вершине v₂, то говорят, что дуга e инцидентна вершине v₂, а вершина v₂ являются смежной вершине v₁. В случае неориентированного графа ребро e является инцидентной обеим вершинам v₁ и v₂, а сами вершины – взаимно смежными.

Путь – это любая последовательность вершин орграфа такая, что в этой последовательности вершина b может следовать за вершиной a, только если существует дуга, следующая из a в b. Аналогично можно определить путь, состоящий из дуг.

Путь, начинающийся и заканчивающийся в одной и той же вершине, называется циклом. Граф, в котором отсутствуют циклы, называется ациклическим.

Петля – дуга, соединяющая некоторую вершину сама с собой.

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