Графом G называется пара G=(V, E), для которой выполнены следующие условия:

  • V – это непустое множество вершин, или узлов,
  • E – это множество пар вершин, называемых


Различают неориентированные и ориентированные графы.


Неориентированным называется граф G=(V, E), в котором пары из множества V являются неупорядоченными, или, более формально:

Для любой пары (vi, vj) если (vi, vj) ϵ E то и (vj, vi) ϵ E.

При этом вершины vi и vj называются концевыми вершинами дуги (vi, vj).


Граф G=(V, E) называется ориентированным (или орграфом), если каждая пара (vi, vj) из множества


Введем некоторые определения, касающиеся графов:


Дуга e=( vi, vj) инцидентнавершинам vi и vj.


Число вершин в графе называется порядком, число рёбер - размеромграфа.


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


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


Два ребра называются кратными, если множества их концевых вершин совпадают.


Ребро e называется петлёй, если его концы совпадают, то есть e=(v, v);


Степеньювершины v называют количество инцидентных ей рёбер (при этом петли считают дважды).


Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.


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


Цикломназывают путь, в котором первая и последняя вершины совпадают.


Путь (или цикл) называют простым, если ребра в нём не повторяются.


Граф называется:


  • связным, если для любых вершин v и u есть путь из v в u.
  • деревом, если он связный и не содержит простых циклов.
  • полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
  • двудольным, если его вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2.
  • планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
  • взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.